Loading AI tools
来自维基百科,自由的百科全书
在图论中,一個圖的圍長定義為這個圖所包含的最短環長。[1] 若這個圖是無環圖,它的圍長則定義做無窮大。[2] 舉例來說,4-環(正方形)的圍長是 4。
最小的圍長為 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。
給定任意正整數和,存在一幅圖,其圍長不小於,同時色數不小於。例如,格勒奇圖無三角形,且色數為,然後重複採用梅切爾斯基構造法(格勒奇圖亦是以此法可得),即得任意大色數而無三角形的圖。埃尔德什·帕尔最先用概率方法證明一般的結論:[4]
取個頂點的随机图,每兩點之間各自獨立地以概率連邊,則當趨向無窮時,大概率(趨向於)該圖中 長度不逾的環總數不超過,同時沒有大小的獨立集。所以,在每個短環中移除一點,餘下的子圖至少有點,圍長大於,但染色時,每種顏色的點數不能超過,即需要至少種色。
若不用概率論證,亦可明確構造圍長和色數皆大的圖,例如有限域上某些線性群的凱萊圖。[5]此類例子同時屬拉馬努金圖,擴展系數大。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.