在图论中，一個圖的圍長定義為這個圖所包含的最短環長。 若這個圖是無環圖，它的圍長則定義做無窮大。 舉例來說，4-環（正方形）的圍長是 4。
籠 (Cage)
最小的圍長為 g 的三次圖（3-正則圖）稱做 g-籠（或是 (3,g)-籠）。佩特森圖是唯一的 5-籠，Heawood graph 則是唯一的 6-籠，McGee graph 是唯一的 7-籠，Tutte eight cage 是唯一的 8-籠。 對特定的圍長來說，可能會存在不只一個籠。比如，存在三個不同構的 10-籠，分別都有 70 條邊：Balaban 10-cage、Harries graph、Harries–Wong graph。
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
圍長與圖染色
給定任意正整數g和\chi，存在一幅圖，其圍長不小於g，同時色數不小於\chi。例如，無三角形，且色數為4，然後重複採用構造法（格勒奇圖亦是以此法可得），即得任意大色數而無三角形的圖。埃尔德什·帕尔最先用證明一般的結論：
取n個頂點的随机图，每兩點之間各自獨立地以n^{(1-g)/g}概率連邊，則當n趨向無窮時，大概率（趨向於1）該圖中
長度不逾g的環總數不超過n/2，同時沒有n/(2k)大小的獨立集。所以，在每個短環中移除一點，餘下的子圖至少有n/2點，圍長大於g，但染色時，每種顏色的點數不能超過n/(2k)，即需要至少k種色。
若不用概率論證，亦可明確構造圍長和色數皆大的圖，例如有限域上某些線性群的凱萊圖。此類例子同時屬，擴展系數大。
參考文獻
评论 (0)