查看“︁圍長 (圖論)”︁的源代码

在[[图论]]中，一個圖的'''圍長'''定義為這個圖所包含的最短[[環 (圖論)|環]]長。<ref>R. Diestel, ''Graph Theory'', p.8.  3rd Edition, Springer-Verlag, 2005</ref> 若這個圖是[[無環圖]]，它的圍長則定義做[[無窮|無窮大]]。<ref>{{cite mathworld|title=Girth|urlname=Girth|accessdate=2017-06-16|archive-date=2020-08-04|archive-url=https://web.archive.org/web/20200804081150/https://mathworld.wolfram.com/Girth.html|dead-url=no}}</ref> 舉例來說，4-環（[[正方形]]）的圍長是 4。

== 籠 (Cage) ==
最小的圍長為 ''g'' 的[[三次圖]]（3-[[正則圖]]）稱做 ''g''-籠（或是 (3,''g'')-籠）。[[佩特森圖]]是唯一的 5-籠，Heawood graph 則是唯一的 6-籠，McGee graph 是唯一的 7-籠，Tutte eight cage 是唯一的 8-籠。<ref>{{citation|last=Brouwer|first=Andries E.|title=Cages|url=http://www.win.tue.nl/~aeb/drg/graphs/|authorlink=Andries Brouwer|accessdate=2017-06-16|archive-date=2020-08-04|archive-url=https://web.archive.org/web/20200804081315/https://www.win.tue.nl/~aeb/drg/graphs/|dead-url=no}}.</ref> 對特定的圍長來說，可能會存在不只一個籠。比如，存在三個不同構的 10-籠，分別都有 70 條邊：Balaban 10-cage、Harries graph、Harries–Wong graph。<gallery>
File:Petersen1 tiny.svg|The Petersen graph has a girth of 5
File:Heawood_Graph.svg|The Heawood graph has a girth of 6
File:McGee graph.svg|The McGee graph has a girth of 7
File:Tutte eight cage.svg|The Tutte–Coxeter graph (Tutte eight cage) has a girth of 8
</gallery>

== 圍長與圖染色 ==
給定任意正整數<math>g</math>和<math>\chi</math>，存在一幅圖，其圍長不小於<math>g</math>，同時[[图着色问题|色數]]不小於<math>\chi</math>。例如，{{link-en|格勒奇圖|Grötzsch graph}}無三角形，且色數為<math>4</math>，然後重複採用{{link-en|梅切爾斯基圖|Mycielskian|梅切爾斯基}}<!--數學家{{le|Jan Mycielski}}，按[[WP:外語譯音表/波蘭語]]-->構造法（格勒奇圖亦是以此法可得），即得任意大色數而無三角形的圖。[[埃尔德什·帕尔]]最先用{{link-en|概率方法|probabilistic method}}證明一般的結論：<ref>{{cite journal | last = Erdős | first = Paul | author-link = Paul Erdős | journal = Canadian Journal of Mathematics | pages = 34–38 | title = Graph theory and probability| url = https://archive.org/details/sim_canadian-journal-of-mathematics_1959_11_1/page/34 |trans-title = 圖論與概率 | volume = 11 | year = 1959 | doi = 10.4153/CJM-1959-003-9|language = en}}</ref>

取<math>n</math>個頂點的[[随机图]]，每兩點之間各自獨立地以<math>n^{(1-g)/g}</math>概率連邊，則當<math>n</math>趨向無窮時，大概率（趨向於<math>1</math>）該圖中
長度不逾<math>g</math>的環總數不超過<math>n/2</math>，同時沒有<math>n/(2k)</math>大小的[[獨立集]]。所以，在每個短環中移除一點，餘下的子圖至少有<math>n/2</math>點，圍長大於<math>g</math>，但染色時，每種顏色的點數不能超過<math>n/(2k)</math>，即需要至少<math>k</math>種色。

若不用概率論證，亦可明確構造圍長和色數皆大的圖，例如[[有限域]]上某些[[矩陣群|線性群]]的[[凱萊圖]]。<ref>{{citation | last1 = Davidoff | first1 = Giuliana  | last2 = Sarnak | first2 = Peter  | last3 = Valette | first3 = Alain | doi = 10.1017/CBO9780511615825 | isbn = 0-521-82426-5 | mr = 1989434 | publisher = Cambridge University Press, Cambridge | series = London Mathematical Society Student Texts | title = Elementary number theory, group theory, and Ramanujan graphs | volume = 55 | year = 2003}}</ref>此類例子同時屬{{link-en|拉馬努金圖|Ramanujan graphs}}，[[扩展图|擴展系數]]大。

==參考文獻==
{{reflist}}

{{圖論}}