主題
Search

圖的圈

圖圖 G的圈，如果未指定第一個頂點，也稱為環路，是邊集 G的子集，它形成一個路徑，使得路徑的第一個節點對應於最後一個節點。 可以使用以下方法獲得給定圖g的邊不相交圈的最大集合ExtractCycles[g] 在 Wolfram 語言 包中Combinatorica` .

精確使用圖頂點一次的圈稱為哈密頓圈。

不包含長度為 3 的圈的圖稱為無三角形圖，不包含長度為 4 的圈的圖稱為無方形圖。

不包含任何長度的圈的圖稱為無環圖，而包含至少一個圈的圖稱為有環圖。 恰好擁有一個（無向，簡單）圈的圖稱為單圈圖。 連通的無環圖稱為樹，而可能不連通的無環圖稱為森林。

給定圖中最短圖圈的長度（如果有）稱為圍長，最長圈的長度稱為圖周長。

圖的任何圈都可以表示為圖的基本圈集的模 2 和（Gould 1959，Paton 1969）。

Björner 和 Wachs (1982) 以及 (Stanley 1999) 考慮了在迴圈的隨機圓形嵌入中，將頂點置於其標準配置所需的最小交換次數。

無環圖是二分圖，並且有環圖是二分圖 當且僅當 其所有圈的長度均為偶數（Skiena 1990，第 213 頁）。

具有鄰接矩陣 A 的圖中，長度為 k 的（無向）閉合路徑的數量由 Tr(A^k) 給出，其中 Tr(A) 表示矩陣跡。 為了計算 k-圈的數量 c_k，必須減去所有不是圈的閉合 k-路徑。 人們會認為，與匹配生成多項式、獨立多項式等類似，應該定義一個圈多項式，其係數是長度為 k 的圈的數量。 雖然在文獻中似乎沒有定義這樣的多項式（相反，“圈多項式”通常指的是對應於迴圈指標的置換群的多項式），但在這項工作中定義了它們。

k-圈的數量 c_k 與路徑計數矩陣 P_k 相關，關係如下

c_k=1/(2k)Tr(P_(k-1)A),
(1)

其中 Tr 表示矩陣跡，A 是鄰接矩陣 (Perepechko 和 Voropaev)。

對應於長度為 k 的閉合路徑的圖被稱為 k-圈圖，或簡稱為 “C_k-圖”。 C_k-圖的數量，對於 k=3, 4, ... 分別是 1, 3, 3, 10, 12, 35, 58, 160, 341, 958, 2444, 7242, 21190, 67217, 217335, ... (OEIS A081809; FlowProblems)。

Harary 和 Manvel (1972) 給出了小 k 的以下閉合形式

6c_3=Tr(A^3)
(2)
8c_4=Tr(A^4)-2m-2sum_(i!=j)a_(ij)^((2))
(3)
=sum_(i)a_(ii)^((4))+sum_(i)a_(ii)^((2))-2sum_(i)sum_(j)a_(ij)^((2))
(4)
=Tr(A^4)+Tr(A^2)-2Tr(diag(A^2)^2)
(5)
=Tr(A^4)-2m-2sum_(i)d_i(d_i-1)
(6)
=Tr(A^4)+Tr(A^2)-2sum_(i)d_i^2
(7)
10c_5=Tr(A^5)-5Tr(A^3)-5sum_(i=1)(sum_(j)a_(ij)-2)a_(ii)^((3))
(8)

（c_4 變體來自 Perepechko 和 Voropaev），其中 m 是圖的邊數，a_(ij)^((k)) 表示 i,j 元素 A^k，diag(A) 是由 A 的對角線元素形成的矩陣，並且 d_i=a_(ii)^((2)) 是第 i 個頂點度。 Alon et al. (1997) 將這些結果擴充套件到 k=7，儘管只給出了直到 k=5 的顯式公式。 c_6 和 c_7 的精確公式由下式給出

12c_6=sum_(i)a_(ii)^((6))-3sum_(n=1)^n(a_(ii)^((3)))^2+9sum_(i)sum_(j)(a_(ij)^((2)))^2a_(ij)-6sum_(i)a_(ii)^((4))d_i+6sum_(i)a_(ii)^((4))-4sum_(i)a_(ii)^((3))+4sum_(i)d_i^3+3sum_(i)sum_(j)a_(ij)^((3))-12sum_(i)d_i^2+4sum_(i)d_i 14c_7=Tr(A^7)-7sum_(i)a_(ii)^((4))a_(ii)^((3))+7sum_(i)sum_(j)(a_(ij)^((2)))^3a_(ij)-7sum_(i)a_(ii)^((5))d_i+21sum_(i)sum_(j)a_(ij)^((3))a_(ij)^((2))a_(ij)+7Tr(A^5)-28sum_(i)sum_(j)(a_(ij)^((2)))^2a_(ij)+7sum_(i)sum_(j)a_(ij)^((2))a_(ij)d_id_j+14sum_(i)a_(ii)^((3))d_i^2+7sum_(i)sum_(j)a_(ii)^((3))a_(ij)^((2))-77sum_(i)a_(ii)^((3))d_i+56Tr(A^3),
(9)

其中 d_i=a_(ii)^((2)) 是第 i 個頂點度（Perepechko 和 Voropaev；S. Perepechko，私人通訊，2014 年 1 月 4 日）。

Khomenko 和 Golovko (1972) 給出了一個公式，可以給出任何長度的圈的數量，但其計算需要計算和執行涉及大小不超過 n-2 的所有子集的矩陣運算，這使得計算成本很高。 Khomenko 和 Golovko 公式的一個簡化和改進版本由下式給出

c_k=1/(2k)sum_(i=2)^k(-1)^(k-i)(n-i; n-k)sum_(|S|=n-i)Tr(A_S^k)
(10)

對於 k=3, 4, ..., n，其中 A_S^k 是鄰接矩陣 A 的子矩陣的第 k 次矩陣冪，其中刪除了行和列的子集 S（Perepechko 和 Voropaev）。 因此，k=n 的情況給出了哈密頓圈的數量。

Giscard et al. (2016) 給出了圖 G 中無向 k-圈數量的公式為

c_k=((-1)^k)/(2k)sum_(H≺_(conn)G)(|N(H)|; k-|H|)(-1)^(|H|)Tr(A_H^k),
(11)

其中總和是對 G 的連通匯出子圖 H 求和，N(H) 表示 H 在 G 中的鄰居數（即 v 的頂點 G，它們不在 H 中，並且存在至少一條從 v 到 H 的頂點的邊），Tr(A) 表示矩陣跡，而 A_H^k 是圖 H 的鄰接矩陣的第 k 次矩陣冪。

設 nu 表示圖中無向圈的總數，mu 表示環秩。 那麼

mu<=nu<=2^mu-1
(12)

（Kirchhoff 1847, Ahrens 1897, König 1936, Volkmann 1996）。 所有階數為 n=1, 2, ... 的簡單圖的無向圈總數分別為 0, 0, 1, 13, 143, 1994, 39688, ... (OEIS A234601)。

mu(G)=nu(G)
(13)

當且僅當任何兩個圈沒有公共邊時（Volkmann 1996）。 因此，在連通圖中，等式對於（且僅對於）仙人掌圖成立。 Mateti 和 Deo (1976) 證明，只有“本質上”四個圖滿足 nu=2^mu-1：完全圖 K_3 和 K_4，完全二分圖 K_(3,3)，以及 K_4-e (Volkmann 1996)。

無向圈的總數也滿足

nu>=n(1/2delta-1)+1
(14)

和

nu>=1/2delta(delta-1),
(15)

其中 n 是頂點數，delta 是最小頂點度 (Volkmann 1996)。

下表給出了各種圖類的無向圖圈數。

圖OEIS序列
Andrásfai 圖A2346020, 1, 29, 1014, 72273, 9842527, ...
反稜柱圖A077263X, X, 63, 179, 523, 1619, 5239, 17379, ...
主教圖A234636X, 0, 3, 106, 17367, 24601058, 638520866656, ...
(n,n)-黑色主教圖A234603X, X, X, 53, 12424, 12300529, ...
雞尾酒會圖 K_(n×2)A1679870, 1, 63, 2766, 194650, 21086055, 3257119761, ...
完全二分圖 K_(n,n)A0709680, 1, 15, 204, 3940, 113865, 4662231, ...
完全三部圖 K_(n,n,n)A2346161, 63, 6705, 1960804, 1271288295, 1541975757831, ...
完全圖 K_nA0028071, 7, 37, 197, 1172, 8018, ...
2n-交叉稜柱圖A23461728, 107, 380, 1345, 4878, 18219, ...
皇冠圖A2346181, 28, 586, 16676, 674171, 36729512, ...
立方體連線圈圖A000000X, X, 2664, ...
圈圖 C_nA0000121, 1, 1, 1, 1, 1, 1, 1, ...
摺疊立方體圖A2346190, 0, 7, 204, 322248, ...
網格圖 P_n square P_nA140517X, 1, 13, 213, 9349, 122236, 487150371, ...
網格圖 P_n square P_n square P_nA234620X, 28, 3426491, ...
半立方體圖A2346210, 0, 7, 2766, 4678134804, ...
河內圖A0000001, 11, 1761, ...
超立方體圖 Q_nA0854080, 1, 28, 14704, 51109385408, ...
(n,n)-國王圖A234622X, 7, 348, 136597, 545217435, 21964731190911, ...
(n,n)-騎士圖A234623X, 0, 1, 222, 128769, 959427728, ...
n-梯形圖A0002170, 1, 3, 6, 10, 15, 21, 28, 36, 45, ...
莫比烏斯梯形圖 M_nA020873X, X, 15, 29, 53, 95, 171, 313, 585, ...
Mycielski 圖A2346250, 0, 1, 337, 445228418, ...
奇圖A3015580, 1, 57, 872137842, ...
置換星圖A0000000, 0, 1, 5442, ...
稜柱圖 Y_nA07726514, 28, 52, 94, 170, ...
(n,n)-皇后圖A2346260, 7, 8215, 2080941496, 269529670654115055, ...
車圖 K_n square K_nA2346240, 1, 312, 3228524, 6198979538330, ...
謝爾賓斯基墊片圖A2346341, 11, 1033, ...
太陽圖A234627X, X, 11, 44, 198, 1036, 6346, 45019, 364039, ...
太陽花圖 C_n circledot K_1A000000X, X, 1, 1, 1, 1, 1, 1, 1, 1, ...
三角形圖A2346290, 1, 63, 15703, 58520309, ...
網狀圖A07726514, 28, 52, 94, 170, 312, 584, 1114, ...
輪圖 W_nA0020617, 13, 21, 31, 43, 57, ...
(n,n)-白色主教圖A234630X, X, X, 53, 4943, 12300529, ...

下表總結了其中一些圖類的閉合形式。

圖公式
反稜柱圖a_n=6a_(n-1)-11a_(n-2)+8a_(n-3)-3a_(n-4)+2a_(n-5)-a_(n-6)
完全二分圖 K_(n,n)1/2sum_(k=2)^(n)k!(k-1)!(n; k)^2
完全圖 K_n1/2sum_(k=3)^(n)(k-1)!(n; k)=1/4n[2_3F_1(1,1,1-n;2;-1)-n-1]
圈圖 C_n1
梯形圖(n; 2)
莫比烏斯梯形圖1+2^n+n(n-1)
稜柱圖 Y_n2^n+n(n-1)
太陽花圖 C_n circledot K_11
網狀圖 f2^n+n(n-1)
輪圖 W_n2(n-1)

參見

無環有向圖, 無弦圈, 環路, 圈弦, 圈圖, 圈多項式, 有環圖, 尤拉圈, 尤拉圖, 尤拉路徑, 森林, 基本圈, 圍長, 圖周長, 圖路徑, 哈密頓圈, 哈密頓圖, k-圈圖, Markström 圖, 無方形圖, 跡, 無三角形圖, 單圈圖, 路徑 在 課堂中探索此主題

使用 探索

WolframAlpha

更多嘗試

參考文獻

Ahrens, W. "Über das Gleichungssystem einer Kirchhoffschen galvanischen Stromverzweigung." Math. Ann. 49, 311-324, 1897.Alon, N.; Yuster, R.; and Zwick, U. "Finding and Counting Given Length Cycles." Algorithmica 17, 209-223, 1997.Björner, A. and Wachs, M. "Bruhat Order of Coxeter Groups and Shellability." Adv. Math. 43, 87-100, 1982.FlowProblem. "C_k-Graphs." http://flowproblem.ru/cycles/explicit-formulae/ck-graphs.Giscard, P.-L.; Kriege, N.; and Wilson, R. C. "A General Purpose Algorithm for Counting Simple Cycles and Simple Paths of Any Length." 16 Dec 2016. https://arxiv.org/pdf/1612.05531.pdf.Gould, R. "The Application of Graph Theory to the Synthesis of Contact Networks." Proc. International Symp. on the Theory of Switching, Pt. I, Apr. 2-5, 1957. In The Annals of the Computation Laboratory of Harvard University, Annals No. 29. Cambridge, MA: Harvard University Press, pp. 244-292, 1959.Harary, F. and Manvel, B. "On the Number of Cycles in a Graph." Mat. Časopis Sloven. Akad. Vied 21, 55-63, 1971.Karavaev, A. M. "FlowProblem: Statistics of Simple Cycles." http://flowproblem.ru/paths/statistics-of-simple-cycles.Khomenko, N. P. and Golovko, L. D. "Identifying Certain Types of Parts of a Graph and Computing Their Number." Ukr. Math. J. 24, 313-321, 1972.Kirchhoff, G. "Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird." Ann. d. Phys. Chem. 72, 497-508, 1847.König, D. Theorie der endlichen und unendlichen Graphen. Leipzig, Germany: Akademische Verlagsgesellschaft, 1936.Mateti, P. and Deo, N. "On Algorithms for Enumerating All Circuits of a Graph." SIAM J. Comput. 5, 90-99, 1976.Paton, K. "An Algorithm for Finding Fundamental Cycles of a Graph." Comm. ACM 12, 514-518, 1969.Perepechko, S. N. and Voropaev, A. N. "The Number of Fixed Length Cycles in an Undirected Graph. Explicit Formulae in Case of Small Lengths."Skiena, S. "Cycles in Graphs." §5.3 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 188-202, 1990.Sloane, N. J. A. Sequences A000012/M0003, A002061/M2638, A002807/M4420, A077263, A077265, A081809, and A234601 in "The On-Line Encyclopedia of Integer Sequences."Stanley, R. P. Enumerative Combinatorics, Vol. 1. Cambridge, England: Cambridge University Press, 1999.Volkmann, L. "Estimations for the Number of Cycles in a Graph." Per. Math. Hungar. 33, 153-161, 1996.West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, pp. 5 and 20, 2000.

在 上引用

圖的圈

請引用為

Weisstein, Eric W. "圖的圈." 來自 Web 資源. https://mathworld.tw/GraphCycle.html

主題分類