離散數(shù)學(xué)第八章(第1講)課件

1、圖論的應(yīng)用圖論是一門應(yīng)用性很強(qiáng)的學(xué)科。 20世紀(jì)60年代以來，它在許多領(lǐng)域，如物理學(xué)、生物學(xué)、計(jì)算機(jī)科學(xué)、信息論、運(yùn)籌學(xué)以及語言學(xué)、社會(huì)科學(xué)等有著廣泛的應(yīng)用。圖論在計(jì)算機(jī)科學(xué)中的應(yīng)用：最短通路、最小生成樹、最大匹配、中國(guó)郵遞員問題和旅行售貨員等問題的算法和計(jì)算機(jī)實(shí)現(xiàn)。第八章 圖8.1 圖的基本概念8.2 路與圖的連通性8.3 圖的矩陣表示8.4 賦權(quán)圖及最短路徑8.5 特殊的圖8.1圖的基本概念離散數(shù)學(xué)所研究的圖是不同于幾何圖形、機(jī)械圖形的另一種數(shù)學(xué)結(jié)構(gòu),不關(guān)心圖中頂點(diǎn)的位置、邊的長(zhǎng)短和形狀, 只關(guān)心頂點(diǎn)與邊的聯(lián)結(jié)關(guān)系。如下圖（a）和（b）可以認(rèn)為是同一個(gè)圖形。abcde1e2e6e4e3e5

2、（a）abcde1e6e2e4e3e5（b）abcde1e2e6e4e3e5（1）圖的定義: 一個(gè)圖G可用一個(gè)二元組表示, 其中V(G)為頂點(diǎn)集合, E(G)是邊的集合。 討論定義： (a) V(G) =V1，V2，Vn為有限非空集合,Vi稱為頂點(diǎn)。 (b) E(G)=e1，em為有限的邊集合,ei稱為邊。 可用 e 或e (vi,vj) 來表示圖的邊。（2）無向圖，有向圖 每一條邊都是無向邊的圖稱無向圖。 每一條邊都是有向邊的圖稱有向圖。 bcdabcda例：將右圖用二元組表示為： ， 其中a，b，c，d , 則：，= a，b，c，d ， , （3）鄰接點(diǎn)，孤立結(jié)點(diǎn) 鄰接點(diǎn)：在一個(gè)圖中，若兩

3、個(gè)結(jié)點(diǎn)有一條有向邊或者一條無向邊關(guān)聯(lián),則這兩個(gè)結(jié)點(diǎn)稱為鄰接點(diǎn)。 孤立結(jié)點(diǎn)：在一個(gè)圖中不與任何結(jié)點(diǎn)相鄰接的結(jié)點(diǎn)，稱為孤立結(jié)點(diǎn)。如下圖中結(jié)點(diǎn)v5。v1v2v3v4v5（4）零圖，平凡圖 零圖：僅由孤立結(jié)點(diǎn)構(gòu)成的圖稱為零圖。如圖(a) 平凡圖：僅由一個(gè)孤立結(jié)點(diǎn)構(gòu)成的圖稱為平凡圖。如圖(b)(a)(b)（5） 鄰接邊：關(guān)聯(lián)于同一結(jié)點(diǎn)的兩條邊稱為鄰接邊。（6）自回路（環(huán)）：關(guān)聯(lián)于同一結(jié)點(diǎn)的一條邊稱為自 回路。 如下圖，e4=是自回路（環(huán)）。 e3e4（7）度數(shù)： 在圖G =中，與結(jié)點(diǎn)v（vV）關(guān) 聯(lián)的邊數(shù)，稱為該結(jié)點(diǎn)的度數(shù)，記作deg（v）。約定：每個(gè)環(huán)在其對(duì)應(yīng)結(jié)點(diǎn)上的度數(shù)增加2 。 ABCED最大度,

4、記為：(G)=maxd(v)| vV最小度,記為：(G)=mind(v)| vV定理1 (握手定理) ：每個(gè)圖中，結(jié)點(diǎn)度數(shù)的總和等于邊數(shù)的兩倍。即 證：每條邊必關(guān)聯(lián)兩個(gè)結(jié)點(diǎn)，而一條邊給于關(guān)聯(lián)的每個(gè)結(jié)點(diǎn)的度數(shù)為1。 故上述定理成立。例：在一次10周年同學(xué)聚會(huì)上，想統(tǒng)計(jì)所有人握手的次數(shù)之和，應(yīng)該如何建立該問題的圖論模型？解：將每個(gè)同學(xué)分別作為一個(gè)節(jié)點(diǎn)，如果兩個(gè)人握過一次手就在相應(yīng)的兩個(gè)節(jié)點(diǎn)之間畫一條無向邊，于是得到一個(gè)無向圖。一個(gè)人握手的次數(shù)就是這個(gè)節(jié)點(diǎn)與其他節(jié)點(diǎn)所連接的邊的條數(shù)，進(jìn)而可得出所有人握手的次數(shù)之和。例：無向圖G有6條邊，各有一個(gè)3度和5度節(jié)點(diǎn)，其余均為2度節(jié)點(diǎn)，求G的階數(shù)。解:設(shè)圖G

5、有x個(gè)節(jié)點(diǎn)度數(shù)為2，則G的階數(shù)為x+1+1=x+2。根據(jù)握手定理有： 3+5+2x=12于是x=2，所以G的階數(shù)為2+2=4。定理2：在任何圖中，度數(shù)為奇數(shù)的結(jié)點(diǎn)必定是偶數(shù)個(gè)。例：是否存在一個(gè)無向圖，其度數(shù)序列分別為： (1) 5，4，4，3，3，2，2 (2) 4，4，3，3，2，2，2，2例：設(shè)無向圖G有10條邊，3度和4度節(jié)點(diǎn)各2個(gè)，其余節(jié)點(diǎn)的度數(shù)均小于3，則G至少有多少個(gè)節(jié)點(diǎn)？在最少節(jié)點(diǎn)的情況下，求出G的度數(shù)序列、最大度 和最小度 。（8）入度，出度：在有向圖中，射入一個(gè)結(jié)點(diǎn)的邊數(shù)稱為該結(jié)點(diǎn)的入度。由一個(gè)結(jié)點(diǎn)射出的邊數(shù)稱為該結(jié)點(diǎn)的出度。 結(jié)點(diǎn)的出度與入度和是該結(jié)點(diǎn)的度數(shù)。BCDADeg

6、+（A）=2, Deg-（A）=3Deg+（B）=3, Deg-（B）=2Deg+（C）=1, Deg-（C）=1Deg+（D）=1, Deg-（D）=1例： 一個(gè)3階有向圖的度序列是2，2，4，入度序列是2，0，2，出度序列是 .bcda證：因?yàn)槊恳粭l有向邊必對(duì)應(yīng)一個(gè)入度和出度，若一個(gè)結(jié)點(diǎn)具有一個(gè)入度或出度，則必關(guān)聯(lián)一條有向邊，所以，有向圖中各結(jié)點(diǎn)入度和等于邊數(shù)，各結(jié)點(diǎn)出度和也是等于邊數(shù)，因此，任何有向圖中，入度之和等于出度和。定理3：在任何有向圖中，所有結(jié)點(diǎn)的入度和等于所有結(jié)點(diǎn)的出度之和。（9）平行邊，多重圖，簡(jiǎn)單圖 連接于同一對(duì)結(jié)點(diǎn)間的多條邊稱為是平行邊。含有平行邊的任何一個(gè)圖稱為多重圖

7、。 不含有平行邊和環(huán)的圖稱作簡(jiǎn)單圖。aabc（b）aabc（a）e1e2（10）無向完全圖：簡(jiǎn)單圖G =中，若每一對(duì)結(jié)點(diǎn)間都有無向邊存在，則稱該圖為無向完全圖。定理4：n個(gè)結(jié)點(diǎn)的無向完全圖的邊數(shù)為： 證明：在有n個(gè)結(jié)點(diǎn)的無向完全圖中，任意兩點(diǎn)間都有邊連接， n個(gè)結(jié)點(diǎn)中任意取兩點(diǎn)的組合為：故有n個(gè)結(jié)點(diǎn)的無向完全圖的邊數(shù)為例：有9個(gè)結(jié)點(diǎn)的無向完全圖K9的邊數(shù)為？（11）補(bǔ)圖：給定一個(gè)圖G，由G中所有結(jié)點(diǎn)和所有能使G成為完全圖的添加邊組成的圖，稱為G 相對(duì)于完全圖的補(bǔ)圖，或簡(jiǎn)稱為G的補(bǔ)圖。記作。 如下圖，（a）和（b）互為補(bǔ)圖。（a）v1v2v5v3v4（b）v1v2v3v4v5例：對(duì)于n階簡(jiǎn)單無向

8、圖G，若其邊數(shù)為m，試計(jì)算G的補(bǔ)圖 的邊數(shù)。（12）子圖：設(shè)圖G =，如果有圖G=，且EE，VV，則稱 G 為 G 的子圖。如下圖，（b）、（c）都是（a）的子圖。（a）bcdhgafe（b）bcdhgfe（c）bcdhgaf（13）生成子圖：如果G的子圖包含G的所有結(jié)點(diǎn)，則稱該子圖為G的生成子圖。如下圖，（b）、（c）都是（a）的生成子圖。（a）（c）（b）v2v4v2v3v1v1v3v4v1v4v2v3例：設(shè)G=與G1=是兩個(gè)圖，若 _,則G1為G的生成子圖。（14）圖同構(gòu) 設(shè)圖G =及圖G=，如果存在一雙射函數(shù)g：vivi且e=（vi，vj）是G的一條邊，當(dāng)且僅當(dāng) e=（g（vi ），g（vj）是 G 的一條邊，則稱G與G同構(gòu)，記作GG。兩個(gè)圖同構(gòu)的充要條件是：兩個(gè)圖的結(jié)點(diǎn)和邊分別存在著一一對(duì)應(yīng)的關(guān)系，且保持關(guān)聯(lián)關(guān)系。dbea（a）u3u4u2u1（b）例：存在著一雙射函數(shù)g：g(a)=u3， g(b)=u1， g(e)=u4， g(d)=u2，且有：,分別與,一一對(duì)應(yīng)所以圖(a) 與圖(b)是同構(gòu)的關(guān)系。兩圖同構(gòu)的一些必要條件：（1）結(jié)點(diǎn)數(shù)目相同。（2）邊數(shù)相等。 （3）度數(shù)相同的結(jié)點(diǎn)數(shù)目相同 這幾個(gè)條件不是兩個(gè)圖同構(gòu)的充分條件。下列兩圖，滿足上述三個(gè)條件，但并不同構(gòu)。例：說明