主題
Search

Halin 圖


HalinGraphs

Halin 圖,有時被稱為無頂多面體,是由具有四個或更多頂點、沒有度數為 2 的頂點,並且透過將樹的所有葉子與繞樹邊界傳遞的迴圈連線而構造的平面嵌入構造的多面體圖。 Halin 圖的例子包括輪圖 W_n、三角形稜柱圖 Y_3Frucht 圖。 上面說明了這些以及 Halin 圖的其他一些示例。

頂點數為 n=1、2、... 的 Halin 圖的數量為 0、0、0、1、1、2、2、4、6、13、22、50、106、252、... (OEIS A346779) (E. Weisstein, 8 月 3 日 - 9 月 29 日,2021 年)。

具有 n 個頂點和 m 條邊的圖是 Halin 圖 當且僅當 它是多面體的(即,平面且 3-連通的),並且具有一個面,該面的頂點數等於圖的環秩 m-n+1

Halin 圖是哈密頓圖,並且在刪除任何單個頂點後仍然是哈密頓圖(Cornuéjols等人,1983 年)。 Halin 圖的樹寬為 3(Bodlaender,1988 年),是非二分圖,並且包含三角形(三階迴圈)。

HalinMatchstickGraphs

kn 節點 Halin 圖對於(至少)以下 (n,k) 值是火柴棍圖:(7, 1)(輪圖 W_7)、(10, 3)、(10, 8)、(10, 10)、(11, 18)、(12, 6)、(12, 8)、(12, 10)、(12, 12)、(12, 16)、(12, 17)、(12, 21)、(12, 23)、(12, 30)、(12, 33)和(12, 34)。


另請參閱

哈密頓圖, 平面嵌入,

使用 探索

參考文獻

Bodlaender, H. "Planar Graphs with Bounded Treewidth." Technical Report RUU-CS-88-14. Utrecht, Netherlands: Department of Computer Science, Utrecht University, 1988.Cornuéjols, G.; Naddef, D.; and Pulleyblank, W. R. "Halin Graphs and the Travelling Salesman Problem." Math. Prog. 26, 287-294, 1983.Halin, R. "Über simpliziale Zerfällungen beliebiger (endlicher oder unendlicher) Graphen." Math. Ann. 156, 216-225, 1964.Sloane, N. J. A. Sequence A346779 in "The On-Line Encyclopedia of Integer Sequences."

請引用為

Weisstein, Eric W. "Halin 圖。" 來自 Web 資源。 https://mathworld.tw/HalinGraph.html

主題分類