複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/圍長/55580660
複製
複製成功

圍長

鎖定
圍長(girth)是圖論中的一個概念，指在一個無向圖中，最短的環的長度 [1]  。如果圖中不含任何環，則定義其圍長為無限大 [2]  。例如，一個正方形的圍長為4，而一個三角網格的圍長為3。顯而易見的，一個圍長為4的圖不含三角形。
中文名
圍長，圖的圍長
外文名
Girth
適用領域
圖論
所屬學科
數學
圖論

目錄

  1. 1 定義
  2. 2 籠
  3. 3 關係
  4. 4 定理

圍長定義

圍長(girth)是圖論中的一個概念，指在一個無向圖中，最短的環的長度。

圍長籠

彼德森圖(Peterson Graph) 彼德森圖(Peterson Graph)
圍長為g的最小的三次圖（度為三的正則圖）被稱為g-籠（g-cage），又被稱為(3,g)-籠（(3,g)-cage）。著名的彼得森圖（Peterson Graph）就是最小的5-籠。一個圍長對應籠的個數不一定為1，例如圍長為10時，存在三種不同構的籠。

圍長關係

直觀上，圍長越長，意味着圖較為稀疏，染色數可能會偏多。但Erdős在1959年的論文中提出了，對於任意的k和l，存在一個圖，滿足其圍長大於l，且其染色數大於k。後來又有人提出了更緊的界。

圍長定理

命題1.3.2：任意包含至少一個圈的圖滿足g(G)≤2diam(G)+1。
證明：設C為G的一個最短圈．如果g(G)≥2diam(G)+2,則C包含兩個頂點使得它們在C 中的距離至少是diam(G)+1. 在G中，這兩個頂點之間的距離更短，而連接它們之間的最短路P不是C的子圖，所以P包含一條C-路xPy。將C中兩條x-y路中短的一條與路xPy連接在一起，將形成一個比C更短的圈，矛盾.
圖G的中心點是指能使得它到任何其他頂點的距離儘可能小的頂點，這個最短距離稱為半徑並記為radG.所以，嚴格地説，
. [3] 
命題1.3.3：設G是一個半徑至多為k且最大都至多為d＞=3的圖，則G的頂點個數小於
.
證明： 設z是G的一箇中心點而
是G中到z距離為i的頂點集，則
.顯然
=1且
<=d.對每個i>=1，因為
中的每個頂點均為
中的某個頂點的鄰點，且
的每個頂點在
中至多有d-1個鄰點（由於它還有一個鄰點在
中），所以
。對所有i＜k用歸納假設，有
，這藴含着
.
類似地，假設G的最小度和圍長均較大，可找到G的階的下界。
定理1.3.4(Alon,Hoory and Linial,2002)：
設G是一個圖。如果
且
,則
。
定理1.3.4保證了一個相對於|G|的較短圈的存在性。可以得到以下更一般的界：
推論1.3.5：若
，則
.
證明：如果g:=g(G)是偶數，則
當g是奇數時，
因為
，故結論成立。 [3] 
參考資料
  • 1.    R. Diestel．Graph Theory：Springer-Verlag，2005
  • 2.    Girth  ．Wolfram MathWorld[引用日期2020-12-23]
  • 3.    Reinhard Diestel 著 於青林 譯．圖論．北京：科學出版社，2020.4：第8頁，第9頁，第10頁