《集合論與圖論課件10.4-平面圖與哈密頓圖pdf.pdf》由會員分享，可在線閱讀，更多相關(guān)《集合論與圖論課件10.4-平面圖與哈密頓圖pdf.pdf（14頁珍藏版）》請在匯文網(wǎng)上搜索。

1、單元單元10.4 平面哈密頓圖平面哈密頓圖 第二編 圖論 第十一章 平面圖 11.6 平面哈密頓圖 1 內(nèi)容提要內(nèi)容提要 平面圖與哈密頓圖平面圖與哈密頓圖 Tait猜想的反例猜想的反例 平面哈密頓圖的充分條件平面哈密頓圖的充分條件 平面哈密頓圖的必要條件平面哈密頓圖的必要條件 2 3 Tait猜想猜想 Tait猜想猜想(1880):3連通連通3正則平面圖都是哈密頓圖正則平面圖都是哈密頓圖 4,6,12面體圖驗證面體圖驗證;解決四色猜想解決四色猜想 4 Tait猜想的反例猜想的反例 Tutte圖圖(1946):46階反例階反例(左圖左圖)Lederberg圖圖(1967):38階反例階反例(右圖

2、右圖)5 平面哈密頓圖充分條件平面哈密頓圖充分條件 定理定理(Tutte,1956):4連通平面圖是哈密頓圖連通平面圖是哈密頓圖.#6 平面哈密頓圖必要條件平面哈密頓圖必要條件 定理定理11.23(Grinberg,1968):n階階簡單簡單平面哈密頓圖平面哈密頓圖,哈密頓回路內(nèi)哈密頓回路內(nèi)(外外)部部次數(shù)為次數(shù)為i的面數(shù)為的面數(shù)為ri(ri”)ni=3(i-2)(ri-ri”)=0.7 定理定理11.23證明證明 ni=3(i-2)(ri-ri”)=0.證證:設(shè)哈密頓回路設(shè)哈密頓回路C內(nèi)有內(nèi)有m1條邊條邊,則則 ni=3ri=m1+1.內(nèi)部面內(nèi)部面deg(Rj)=ni=3iri=2m1+n,

3、所以所以,ni=3(i-2)ri=n-2.同理同理 ni=3(i-2)ri”=n-2.#8 例例11.5 下圖中不存在過邊下圖中不存在過邊(a,b)的哈密頓回路的哈密頓回路.(由由此可證此可證Tutte圖圖和和Lederberg圖圖不是哈密頓圖不是哈密頓圖.)#3 8 5 5 5 5 5 4 4 a b c 9 例例11.5 ni=3(i-2)(ri-ri”)=0 (定理定理11.23)(r3-r3”)+2(r4-r4”)+3(r5-r5”)+6(r8-r8”)=0 3 8 5 5 5 5 5 4 4 a b 10 例例11.5 (r3-r3”)+2(r4-r4”)+3(r5-r5”)+6(r

4、8-r8”)=0 (1-0 )+2(r4-r4”)+3(r5-r5”)+6(0-1)=0 2(r4-r4”)+3(r5-r5”)=5 3 8 5 5 5 5 5 4 4 a b 11 例例11.5 2(r4-r4”)+3(r5-r5”)=5 2(1-1)+3(r5-r5”)=5,即即 3(r5-r5”)=5 2(2-0)+3(r5-r5”)=5,即即 3(r5-r5”)=1 3 8 5 5 5 5 5 4 4 a b 12 例例11.5 3(r5-r5”)=5 或或 1 上式不可能成立上式不可能成立,因為因為(r5-r5)是整數(shù)是整數(shù).#3 8 5 5 5 5 5 4 4 a b 13 Gadget 設(shè)計設(shè)計 有沒有更小的有沒有更小的gadget(小配件小配件)?注意是注意是3-正則平面圖正則平面圖 3 8 5 5 5 5 5 4 4 a b 14 總結(jié)總結(jié) 平面哈密頓圖平面哈密頓圖 Tait猜想的反例 平面哈密頓圖的充分條件 平面哈密頓圖的必要條件