【正文】 第 8章 圖論 第 8章 圖論 圖的基本概念 路徑和回路 圖的矩陣表示 二部圖 平面圖 樹 有向樹 運(yùn)輸網(wǎng)絡(luò) ABCD問題是要從這四塊陸地中任何一塊開始，通過每一座橋正好一次，再回到起點(diǎn)。 歐拉在 1736年解決了這個(gè)問題 。 判定法則：如果通奇數(shù)座橋的地方不止兩個(gè)，那么滿足要求的路線便不存在了。如果只有兩個(gè)地方通奇數(shù)座橋，則可從其中任何一地出發(fā)找到所要求的路線。若沒有一個(gè)地 方通奇數(shù)座橋，則從任何一地出發(fā)，所求的路線都能實(shí)現(xiàn) 第 8章 圖論 定義 ―1 一個(gè) 圖 G是一個(gè)三重組 〈 V(G),E(G),ΦG〉 ,其中V(G)是一個(gè)非空的 結(jié)點(diǎn) (或叫頂點(diǎn) )集合 ,E(G)是 邊 的集合 ,ΦG是從邊集 E到結(jié)點(diǎn)偶對集合上的函數(shù)。一個(gè)圖可以用一個(gè)圖形表示。 例 1設(shè) G=〈 V(G),E(G),ΦG〉 ,其中 V(G)={a,b,c,d},E(G)={e1,e2,e3,e4, e5,e6,e7},ΦG(e1)=(a,b),ΦG(e2)=(a,c),ΦG(e3)=(b,d), ΦG(e4)=(b,c),ΦG(e5)=(d,c),ΦG(e6)=(a,d),ΦG(e7)=(b,b) 則圖 G可用圖 ― 1表示 。 圖的基本概念 圖 第 8章 圖論 第 8章 圖論 定義中的結(jié)點(diǎn)偶對可以是有序的 ,也可以是無序的。若邊 e所對應(yīng)的偶對 〈 a,b〉 是有序的 ,則稱 e是 有向邊 。有向邊簡稱弧 ,a叫弧 e的始點(diǎn) ,b叫弧 e的終點(diǎn) ,統(tǒng)稱為 e的端點(diǎn)。稱 e是關(guān)聯(lián)于結(jié)點(diǎn) a和 b的 ,結(jié)點(diǎn) a和結(jié)點(diǎn) b是 鄰接的 。若邊 e所對應(yīng)的偶對 (a,b)是無序的 ,則稱 e是 無向邊 。無向邊簡稱棱 ,除無始點(diǎn)和終點(diǎn)的術(shù)語外 ,其它術(shù)語與有向邊相同。 每一條邊都是有向邊的圖稱為 有向圖 , 第三章中的關(guān)系圖都是有向圖的例子 。 每一條邊都是無向邊的圖稱為 無向圖 ；如果在圖中一些邊是有向邊 ,而另一些邊是無向邊 ,則稱這個(gè)圖是 混合圖 。 我們僅討論有向圖和無向圖 ,且 V(G)和 E(G)限于有限集合 。 第 8章 圖論 約定用 〈 a,b〉 表示有向邊 ,(a,b)表示無向邊 ,既表示有向邊又表示無向邊時(shí)用 ［ a,b］ 。 有向圖和無向圖也 可互相轉(zhuǎn)化 。例如 ,把無向圖中每一條邊都看作兩條方向不同的有向邊 ,這時(shí)無向圖就成為有向圖。又如 ,把有向圖中每條有向邊都看作無向邊 ,就得到無向圖。這個(gè)無向圖習(xí)慣上叫做該 有向圖的底圖 。 在圖中 ,不與任何結(jié)點(diǎn)鄰接的結(jié)點(diǎn)稱為 弧立結(jié)點(diǎn) ；全由孤立結(jié)點(diǎn)構(gòu)成的圖稱為 零圖 。關(guān)聯(lián)于同一結(jié)點(diǎn)的一條邊稱為 自回路 ；自回路的方向不定。自回路的有無不使有關(guān)圖論的各個(gè)定理發(fā)生重大變化 ,所以有許多場合都略去自回路。 第 8章 圖論 在有向圖中 ,兩結(jié)點(diǎn)間 (包括結(jié)點(diǎn)自身間 )若同始點(diǎn)和同終點(diǎn)的邊多于一條 ,則這幾條邊稱為 平行邊 。在無向圖中 ,兩結(jié)點(diǎn)間 (包括結(jié)點(diǎn)自身間 )若多于一條邊 ,則稱這幾條邊為平行邊。兩結(jié)點(diǎn) a、 b間互相平行的邊的條數(shù)稱為 邊 ［ a,b］ 的重?cái)?shù) 。僅有一條時(shí)重?cái)?shù)為 1,無邊時(shí)重?cái)?shù)為 0。 定義 ―2 含有平行邊的圖稱為 多重圖 。 非多重圖稱為 線圖 。無自回路的線圖稱為 簡單圖 。 在圖 ―3 中 ,(a)、 (b)是多重圖 ,(c)是線圖 ,(d)是簡單圖 ,關(guān)系圖都是線圖。 第 8章 圖論 圖 ―3 第 8章 圖論 定義 ―3 賦權(quán)圖 G是一個(gè)三重組 〈 V,E,g〉 或四重組 〈 V,E,f,g〉 ,其中 V是結(jié)點(diǎn)集合 , E是邊的集合 ,f是定義在 V上的函數(shù) ,g是定義在 E上的函數(shù)。 右圖給出一個(gè)賦權(quán)圖 。 V={v1,v2,v3} E={e1,e2}={(v1,v2),(v2,v3)} f(v1)=5,f(v2)=8,f(v3)=11 g(e1)=,g(e2)= 第 8章 圖論 結(jié)點(diǎn)的次數(shù) 定義 ―4 在 有向圖中 ,對于任何結(jié)點(diǎn) v,以 v為始點(diǎn)的邊的條數(shù)稱為結(jié)點(diǎn) v的 引出次數(shù) (或出度 ),記為 deg+(v)。以 v為終點(diǎn)的邊的條數(shù)稱為結(jié)點(diǎn) v的 引入次數(shù) (或入度 ),記為 deg(v)。結(jié)點(diǎn) v的引出次數(shù)和引入次數(shù)之和稱為結(jié)點(diǎn)v的 次數(shù) (或度數(shù) ),記作 deg(v)。在無向圖中 ,結(jié)點(diǎn) v的次數(shù)是與結(jié)點(diǎn) v相關(guān)聯(lián)的邊的條數(shù) ,也記為 deg(v)。孤立結(jié)點(diǎn)的次數(shù)為零。 第 8章 圖論 定理 ―1 設(shè) G是一個(gè) (n,m)圖 ,它的結(jié)點(diǎn)集合為V={v1,v2,…,vn},則 11d eg ( ) d eg ( ) 2nniiiim??????????1d eg ( ) 2niim???? 證 因?yàn)槊恳粭l邊提供兩個(gè)次數(shù) ,而所有各結(jié)點(diǎn)次數(shù) 之和為 m條邊所提供 ,所以上式成立。 在有向圖中 ,上式也可寫成 : 第 8章 圖論 定理 ―2 在圖中 ,次數(shù)為奇數(shù)的結(jié)點(diǎn)必為偶數(shù)個(gè)。 證 設(shè)次數(shù)為偶數(shù)的結(jié)點(diǎn)有 n1個(gè) ,記為 (i=1,2,…,n1)。 次數(shù)為奇數(shù)的結(jié)點(diǎn)有 n2個(gè) ,記為 (i=1,2,… ,n2)。 由上一定理得 iE?iO?121 1 12 d eg ( ) d eg ( ) d eg ( )iinnni E Oi i im ? ? ?? ? ?? ? ?? ? ? 因?yàn)榇螖?shù)為偶數(shù)的各結(jié)點(diǎn)次數(shù)之和為偶數(shù)。所以 前一項(xiàng)次數(shù)為偶數(shù) 。若 n2為奇數(shù) ,則第二項(xiàng)為奇數(shù) ,兩項(xiàng) 之和將為奇數(shù) ,但這與上式矛盾。故 n2必為偶數(shù)。證畢。 第 8章 圖論 圖 ―5 第 8章 圖論 定義 ―5 各結(jié)點(diǎn)的次數(shù)均相同的圖稱為正則圖 ,各結(jié)點(diǎn)的次數(shù)均為 k時(shí)稱為 k― 正則圖。 下圖所示的稱為彼得森 (Petersen)圖 ,是 3― 正則圖。 第 8章 圖論 圖的同構(gòu) 定義 G=〈 V,E〉 和 G′=〈 V′,E′〉 是兩個(gè)圖 ,若存在從 V到 V′的雙射函數(shù) Φ,使對任意 a、 b∈ V,［ a,b∈ E當(dāng)且僅當(dāng)［ Φ(a),Φ(b)］ ∈ E′,并且［ a,b］和［ Φ(a),Φ(b)］有相同的重?cái)?shù) ,則稱 G和 G′是 同構(gòu)的 。 上述定義說明 ,兩個(gè)圖的各結(jié)點(diǎn)之間 ,如果存在一一對應(yīng)關(guān)系 ,而且這種對應(yīng)關(guān)系保持了結(jié)點(diǎn)間的鄰接關(guān)系(在有向圖時(shí)還保持邊的方向 )和邊的重?cái)?shù) ,則這兩個(gè)圖是同構(gòu)的 ,兩個(gè)同構(gòu)的圖除了頂點(diǎn)和邊的名稱不同外實(shí)際上代表同樣的 組合結(jié)構(gòu)。 第 8章 圖論 例 2 (a)、 (b)兩圖是同構(gòu)的。因?yàn)榭勺饔?br />