主題
Search

圖的周長

圖的周長是圖中任何最長圈的長度。哈密頓圖在 n>1 個頂點上的周長為 n。

對於迴圈圖，所有相鄰頂點 (i,j) 上繞道矩陣的最大元素 a_(ij) 比周長小 1。

自補圖的圖周長為 n（即，該圖是哈密頓圖）、n-1 或 n-2 (Furrigia 1999, p. 51)。

下表總結了各種非哈密頓圖的圖周長。

類別周長
啞鈴圖n
(n,n)-主教圖{n^2/2 for n even; (n^2+1)/2 for n odd
書圖 S_(n+1) square P_26
完全二分圖 K_(m,n)，對於 min(m,n)>12min(m,n)
(m,n)-錐圖{2m for m<=n; m+n otherwise
齒輪圖2n
網格圖 P_m square P_n{mn-1 for m,n odd; mn otherwise
網格圖 P_l square P_m square P_n{lmn-1 for l,m,n odd; lmn otherwise
舵圖n+1
(n,n)-騎士圖{14 for n=4; n^2 for even n>4; n^2-1 for odd n>2
平底鍋圖n
日曬圖 C_n circledot K_1n
網狀圖2n
輪圖 W_nn
(m,n)-風車圖n

另請參閱

近哈密頓圖, 繞道矩陣, 圍長, 圖的圈, 圖的直徑, 圖的離心率, 圖的半徑, 哈密頓數, 最長路徑

使用 探索

參考文獻

Dirac, G. "Some Theorems on Abstract Graphs." Proc. London Math. Soc. 2, 69-81, 1952.Farrugia, A. "Self-Complementary Graphs and Generalisations: a Comprehensive Reference Manual." Aug. 1999. http://www.alastairfarrugia.net/sc-graph/sc-graph-survey.pdf.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, p. 13, 1994.Li, H. "Generalizations of Dirac's Theorem in Hamiltonian Graph Theory--A Survey." Disc. Math. 313, 2034-2053, 2013.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 192, 1990.Yuan, L-.T. "Circumference, Minimum Degree and Clique Number." Elec. J. Combin. 31, No. 4, Article P4.64, 2024.Zamfirescu, T. "On Longest Paths and Circuits in Graphs." Math. Scand. 38, 211-239, 1976.

在 中引用

圖的周長

請這樣引用

韋斯坦因，埃裡克·W. "圖的周長。" 來自 網路資源。 https://mathworld.tw/GraphCircumference.html

主題分類