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

幾種特殊的圖

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

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

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

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

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

v－e+r=2.127.3.6樹

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

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

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

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

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

連通圖G至少有一棵生成樹。G只要刪邊去回路→連通無回路。GT1T2T318

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

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

1.在G中選取最小權的邊ei，置i=1；

2.當i=n－1時結束，否則轉3；

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

ei+1無回路，且ei+1具有最小的權；

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

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

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

在根樹中若vi可達vj

且通路長度≥2，則稱vi是vj的祖先，vj是vi的后代。若<vi,vj>是根樹的邊，則稱vi是vj的父親，vj是vi的兒子，同一結點的兒