第10章 特殊圖last

《第10章 特殊圖last》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、《離散數(shù)學(xué)教程》教案與習(xí)題解析理工學(xué)院段景輝第10章特殊圖10.1歐拉圖與哈密頓圖10.1.1歐拉圖及歐拉路徑定義10.1圖G稱為歐拉圖(Eulergraph)，如果圖G上有一條經(jīng)過G的所有頂點(diǎn)、所有邊的閉路徑，或圖G為一個(gè)孤立頂點(diǎn)。圖G稱為歐拉路徑(Eulerwalk)，如果圖G上有一條起始于一個(gè)頂點(diǎn)，經(jīng)過G所有頂點(diǎn)、所有邊而終止于另一頂點(diǎn)的路徑。定理10.1無向圖G為歐拉圖當(dāng)且僅當(dāng)G連通，并且所有頂點(diǎn)的度都是偶數(shù)。有向圖G為歐拉圖，當(dāng)且僅當(dāng)G是弱連通的，并且每個(gè)頂點(diǎn)的出度與入度相等。定理10.2無向圖G

2、為歐拉路徑，當(dāng)且僅當(dāng)G連通，并且恰有兩個(gè)頂點(diǎn)的度是奇數(shù)。有向圖G為歐拉路徑，當(dāng)且僅當(dāng)G連通，并且恰有兩個(gè)頂點(diǎn)的入度與出度不等，它們中一個(gè)的出度比入度多1，另一個(gè)入度比出度多l(xiāng)。10.1.2哈密頓圖及哈密頓通路定義10.2如果無向圖G上有一條經(jīng)過所有頂點(diǎn)的回路，或圖G為一個(gè)孤立頂點(diǎn)，那么，稱圖G為哈密頓圖(Hamiltongraph)，（也稱這一回路為哈密頓回路）。如果無向圖G上有一條起始于一個(gè)頂點(diǎn)，經(jīng)過G所有頂點(diǎn)而終止于另一頂點(diǎn)的通路，那么，稱圖G上有哈密頓通路(Hamiltonpath)。定理10.3設(shè)圖

3、G為具有n（n≥3）個(gè)頂點(diǎn)的簡(jiǎn)單無向圖，如果G的每一對(duì)頂點(diǎn)的度數(shù)之和都不小于n–1，那么G中有一條哈密頓通路；如果G的每一對(duì)頂點(diǎn)的度數(shù)之和不小于n，那么G為一哈密頓圖。定理10.4當(dāng)n為不小于3的奇數(shù)時(shí)，Kn上恰有條互不相同的哈密頓回路；恰有條互相均無公共邊的哈密頓回路。定義10.3如果可以用兩種顏色對(duì)圖G的所有頂點(diǎn)著色，每個(gè)頂點(diǎn)著一種顏色，并且使得相鄰的頂點(diǎn)著不同的顏色，那么，稱圖G是可2-著色的。定理10.5設(shè)圖G是可2-著色的。如果G是哈密頓圖，那么著兩種顏色的頂點(diǎn)數(shù)目相等；如果G有哈密頓通路，那么著

4、兩種顏色的頂點(diǎn)數(shù)目之差至多為一。定理10.5只指出了哈密頓圖和哈密頓通路存在的必要條件，它并不充分，很容易作出可2-著色且兩種顏色頂點(diǎn)數(shù)目相等的圖，它卻不是哈密頓圖。定理10.5用來判定某些圖不是哈密頓圖或沒有哈密頓通路是方便的，但是，它要求圖是可2-著色的，這并不是任何圖都能滿足的。當(dāng)一個(gè)圖不可2-著色時(shí)，可以在二度頂點(diǎn)所關(guān)聯(lián)的邊上添加頂點(diǎn)，28《離散數(shù)學(xué)教程》教案與習(xí)題解析理工學(xué)院段景輝使圖可以二著色。練習(xí)10.11、選擇題（1）歐拉圖是（　　）A、路徑　　B、閉路徑C、回路D、通路【答案】：B（2）哈

5、密爾頓圖是（　　）A、路徑B、閉路徑C、回路D、三者都不是【答案】：C（3）設(shè)G=(n,m)是歐拉圖，則n,m有關(guān)系（　?。〢、n=mB、n,m的奇偶性必相同C、n,m的奇偶性必相反D、n,m的奇偶性既可相同也可相反【答案】：D2、填空題（1）無向圖G有一條歐拉路徑，當(dāng)且僅當(dāng)?！敬鸢浮浚篏連通且恰有零個(gè)或兩個(gè)奇數(shù)度節(jié)點(diǎn)。（2）當(dāng)n為時(shí)，Kn必為歐拉圖。【答案】：奇數(shù)（3）當(dāng)n為時(shí)，Kn必為哈密爾頓圖?！敬鸢浮浚捍笥?的整數(shù)（4）當(dāng)n為時(shí)，n個(gè)頂點(diǎn)的樹必非歐拉圖和哈密爾頓圖。【答案】：大于1的整數(shù)3、“螞蟻賽

6、跑問題”：圖10.1中，在結(jié)點(diǎn)v2，v3上的兩只螞蟻跑過圖的所有邊（至少一次）到達(dá)目標(biāo)v4，誰花費(fèi)的時(shí)間多？（假設(shè)螞蟻通過每一條邊所花費(fèi)時(shí)間相同）。28《離散數(shù)學(xué)教程》教案與習(xí)題解析理工學(xué)院段景輝v1v4v5v2v3圖10.1【答案】：解.結(jié)點(diǎn)v2上的螞蟻花費(fèi)的時(shí)間多。根據(jù)定理10.2，圖10.13有一條v3到v4的歐拉路徑，即由v3到v4有一條經(jīng)過圖中的每條邊一次且僅一次的路徑；而要想找一條從v2到v4且經(jīng)過每條邊的擬路徑，必有邊重復(fù)。所以由v3到v4只需經(jīng)過9條邊，從v2到v4所經(jīng)過的邊數(shù)必多于9條。4

7、、試作出四個(gè)圖的圖示，使第一個(gè)既為歐拉圖又為哈密頓圖；第二個(gè)是歐拉圖而非哈密頓圖；第三個(gè)是哈密頓圖卻非歐拉圖；第四個(gè)既非歐拉圖也非哈密頓圖?！敬鸢浮浚航?圖10.2(a)既為歐拉圖又為哈密頓圖；(b)是歐拉圖而非哈密頓圖；(c)是哈密頓圖卻非歐拉圖；(d)既非歐拉圖也非哈密頓圖。(a)(b)(c)(d)圖10.25、像第4題要求的那樣對(duì)歐拉路徑和哈密頓通路作出四個(gè)圖?！敬鸢浮浚航?圖10.3(a)既有歐拉路徑又有哈密頓通路；(b)有歐拉路徑而無哈密頓通路；(c)有哈密頓通路卻無歐拉路徑；(d)既無歐拉路徑也

8、無哈密頓通路。（a）(b)(c)(d)圖10.328《離散數(shù)學(xué)教程》教案與習(xí)題解析理工學(xué)院段景輝6、問n為何種數(shù)值時(shí)，Kn既是歐拉圖又是哈密頓圖。問k為何值時(shí)，k-正則圖既是歐拉圖又是哈密頓圖?！敬鸢浮浚航?n為奇數(shù)時(shí)，Kn既是歐拉圖又是哈密頓圖。k為大于或等于n/2的偶數(shù)時(shí)，k-正則圖既是歐拉圖又是哈密頓圖。7、證明：恰有兩個(gè)奇數(shù)度頂點(diǎn)u,v的無向圖G是連通的,當(dāng)且僅當(dāng)在G上添加邊(u,v)后所得的圖G*是連通