圍長 (圖論)

维基百科,自由的百科全书
跳转至: 导航搜索

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

参考文献[编辑]

  1. ^ R. Diestel, Graph Theory, p.8. 3rd Edition, Springer-Verlag, 2005
  2. ^ Girth – Wolfram MathWorld 
  3. ^ Brouwer, Andries E., Cages .