7.3-圖-論(2)(部編)課件

幾種特殊的圖

歐拉圖哈密頓圖平面圖樹17.3.4歐拉圖一筆畫問題：歐拉通路或歐拉回路。定義7.1.5

在無向連通簡(jiǎn)單圖中，通過圖中每邊一次且僅一次并行遍每個(gè)結(jié)點(diǎn)的一條通路(回路)，稱為該圖的一條歐拉通路(回路)。存在歐拉回路的圖稱為歐拉圖。無歐拉通路或歐拉回路歐拉通路歐拉回路2定理7.3

無向連通圖G是歐拉圖的充分必要條件是G不含奇數(shù)度結(jié)點(diǎn)。推論非平凡連通圖G含有歐拉通路的充分必要條件是G最多有兩個(gè)奇數(shù)度結(jié)點(diǎn)。例下列圖是否可以一筆畫出來.AB×√√3例1驗(yàn)證哥尼斯堡七橋問題無解.解七橋問題圖7-7可簡(jiǎn)化為圖7-20.從圖7-20知，此圖為無向連通圖，并且每個(gè)結(jié)點(diǎn)度數(shù)為奇數(shù)，由定理7.3，此圖不是歐拉圖，即知哥尼斯堡七橋問題無解.4定理連通有向圖G含有歐拉回路的充分必要條件是G中每個(gè)結(jié)點(diǎn)的入度等于出度；連通有向圖G含有歐拉通路的充分必要條件是除兩個(gè)結(jié)點(diǎn)外，其余每個(gè)結(jié)點(diǎn)的入度等于出度，這兩個(gè)結(jié)點(diǎn)中一個(gè)結(jié)點(diǎn)的入度比其出度多1，另一個(gè)結(jié)點(diǎn)的入度比其出度少1。57.3.5哈密頓圖定義7.1.6經(jīng)過圖中每個(gè)結(jié)點(diǎn)一次且僅一次的通路(回路)，稱為哈密頓通路(回路)。存在哈密頓回路的圖稱為哈密頓圖。哈密頓圖哈密頓圖無哈密頓通路存在哈密頓通路6例舉出滿足下列條件具有6個(gè)點(diǎn)的圖。⑴無哈密頓回路，無歐拉路。⑵有哈密頓回路，無歐拉路。⑶無哈密頓回路，有歐拉路。⑷有哈密頓回路，有歐拉路。⑴⑵⑶⑷7討論題判斷各圖是否為哈密頓圖，并說明原因，若是哈密頓圖，請(qǐng)畫出哈密頓回路?！痢痢痢獭?√√××9(補(bǔ)充)平面圖在印刷電路版等方面有應(yīng)用.定義3

設(shè)無向圖G=<V,E>，如果能夠把G的所有結(jié)點(diǎn)和邊畫在平面上，使得任何兩邊除公共結(jié)點(diǎn)外沒有其它交叉點(diǎn)，則稱G為可嵌入平面圖，或稱G是可平面圖，可平面圖在平面上的一個(gè)嵌入稱為平面圖。否則稱G為非平面圖。有些圖雖然有相交的邊，如果經(jīng)改畫后可以不相交，這樣的圖仍是平面圖。10例G可改畫為所以G是平面圖。二個(gè)典型的非平面圖.K5K3,311定理

平面圖中，所有面的次數(shù)之和是其邊數(shù)的兩倍。定理(歐拉公式)設(shè)連通平面圖G=<V,E>，共有v個(gè)結(jié)點(diǎn)，e條邊和r個(gè)面，則有

v－e+r=2.127.3.6樹

在計(jì)算機(jī)科學(xué)中樹是一種經(jīng)常使用的數(shù)據(jù)結(jié)構(gòu).定義7.1.7

連通且無回路的無向圖稱為樹，用T表示。T中d(v)=1的結(jié)點(diǎn)v稱為樹葉。T中d(v)>1的結(jié)點(diǎn)稱為分支點(diǎn)或內(nèi)點(diǎn)。每個(gè)連通分圖是樹的無向圖稱為森林。一個(gè)孤立結(jié)點(diǎn)稱為平凡樹。13樹樹葉分枝點(diǎn)非樹森林非樹樹樹14定理

給定圖T=<V,E>，以下關(guān)于樹的定義是等價(jià)的(|V|=n,|E|=m):⑴無回路的連通圖；⑵無回路且m=n－1；⑶連通且m=n－1；⑷無回路，但增加一條新邊，得到一個(gè)且僅一個(gè)回路；⑸連通但刪去任一邊后，就不連通了；⑹每一對(duì)結(jié)點(diǎn)有一條且僅一條通路。15定理7.4

任何非平凡樹至少有兩片樹葉。證：2m=deg(vi)≥k+2(n－k)=2n－k

i設(shè)有k個(gè)一度結(jié)點(diǎn)其余n－k個(gè)結(jié)點(diǎn)的度≥2∵m=n－1,∴2(n－1)≥2n－k ∴k≥2 ■16生成樹及其應(yīng)用定義若圖G的生成子圖(含圖G所有結(jié)點(diǎn)的子圖)是樹，則稱這棵樹為G的生成樹。圖G的一棵生成樹為T。e1e2e3e4e5e6e7e8e9e10Ge1e2e3e6e8e9T17定理7.5

連通圖G至少有一棵生成樹。G只要?jiǎng)h邊去回路→連通無回路。GT1T2T318

若連通圖G有n個(gè)結(jié)點(diǎn)，m條邊，要確定G的一棵生成樹，必須刪去G的m－(n－1)條邊。定義

在圖G的所有生成樹中，帶權(quán)最小的那棵樹稱為最小生成樹。19求最小生成樹的克魯斯克爾算法：

1.在G中選取最小權(quán)的邊ei，置i=1；

2.當(dāng)i=n－1時(shí)結(jié)束，否則轉(zhuǎn)3；

3.設(shè)已選擇邊為T={e1,e2,...,ei},在E－T中選取ei+1,使T

ei+1無回路，且ei+1具有最小的權(quán)；

4.置i=i+1，轉(zhuǎn)2。22223311紅線組成最小生成樹T，w(T)=6.20根樹定義

一個(gè)有向圖，如果刪去每條邊的方向所得到的無向圖是一棵樹，則稱這個(gè)有向圖為有向樹。定義

一棵非平凡的有向樹，如果恰有一個(gè)結(jié)點(diǎn)的入度為有向樹0，其余所有結(jié)點(diǎn)的入度均為1，則稱這棵有向樹為根樹。入度為0的結(jié)點(diǎn)稱為樹根，出度為0的結(jié)點(diǎn)稱為樹葉，出度不為0的結(jié)點(diǎn)稱為內(nèi)點(diǎn)，內(nèi)點(diǎn)同樹根統(tǒng)稱為分支點(diǎn)。v1v2v3v4v5v6v7v8v9v10v11v12v1321習(xí)慣上有向邊方向均指向下方，一般可省去全部箭頭，上圖可畫成：在根樹中從樹根到任意結(jié)點(diǎn)的長(zhǎng)度，稱為該結(jié)點(diǎn)的層數(shù)，所有結(jié)點(diǎn)中最大的層數(shù)稱為根樹的樹高。定義

在根樹中若vi可達(dá)vj

且通路長(zhǎng)度≥2，則稱vi是vj的祖先，vj是vi的后代。若<vi,vj>是根樹的邊，則稱vi是vj的父親，vj是vi的兒子，同一結(jié)點(diǎn)的兒