圍長 (圖論)

在图论中，一個圖的圍長定義為這個圖所包含的最短環長。[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

參考文獻
  1. R. Diestel, Graph Theory, p.8. 3rd Edition, Springer-Verlag, 2005
  2. , [2017-06-16], （原始内容存档于2020-08-04）
  3. Brouwer, Andries E., , [2017-06-16], （原始内容存档于2020-08-04）.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.