圍長 (圖論)
在图论中，一個圖的圍長定義為這個圖所包含的最短環長。[1] 若這個圖是無環圖，它的圍長則定義做無窮大。[2] 舉例來說，4-環（正方形）的圍長是 4。
籠 (Cage)
最小的圍長為 g 的三次圖（3-正則圖）稱做 g-籠（或是 (3,g)-籠）。彼得森你圖是唯一的 5-籠，Heawood graph 則是唯一的 6-籠，McGee graph 是唯一的 7-籠，Tutte eight cage 是唯一的 8-籠。[3] 對特定的圍長來說，可能會存在不只一個籠。比如，存在三個不同構的 10-籠，分別都有 70 條邊：Balaban 10-cage、Harries graph、Harries–Wong graph。
-
The Petersen graph has a girth of 5 -
The Heawood graph has a girth of 6 -
The McGee graph has a girth of 7 -
The Tutte–Coxeter graph (Tutte eight cage) has a girth of 8
參考文獻
- ^ R. Diestel, Graph Theory, p.8. 3rd Edition, Springer-Verlag, 2005
- ^ Girth – Wolfram MathWorld, [2017-06-16], （原始内容存档于2020-08-04）
- ^ Brouwer, Andries E., Cages, [2017-06-16], （原始内容存档于2020-08-04）.
| ||||||||||||||||||||||||||||||||||||||||||||||