離散數(shù)學(xué)13改.ppt

1、第三篇 圖 論,圖論是組合數(shù)學(xué)的一個(gè)分支，近 30 年發(fā)展十分迅速，并被廣泛地應(yīng)用。 如：生態(tài)學(xué)里棲息地重疊圖、熟人關(guān)系圖、影響圖、好萊塢圖、循環(huán)賽圖、合作圖、呼叫圖、網(wǎng)絡(luò)圖等。,1736年，歐拉研究哥尼斯堡七橋問題； 19世紀(jì) 20世紀(jì)前期，研究游戲問題，如：迷宮問題、博弈問題、棋盤上馬的行走路線等。 最著名的難題是四色問題、哈密頓問題和烏拉姆問題。,歷史悠久,美國數(shù)學(xué)家 Appel 和 Haken 于1976年在高速計(jì)算機(jī)上運(yùn)算了 1200 個(gè)小時(shí)，解決了四色問題。 1847年，基爾霍夫圖論來分析電網(wǎng)絡(luò)，這是圖論在工程技術(shù)領(lǐng)域應(yīng)用的第一例。 直到 20 世紀(jì) 30 年代，圖論成為一門獨(dú)立的

2、學(xué)科。,1、圖的基本概念 2、通路、回路和連通性 3、圖的矩陣表示 4、歐拉圖和哈密頓圖 5、偶圖與匹配 6、平面圖 7、樹,1、圖的基本概念,主要知識點(diǎn)：,第六章 圖,預(yù)備知識：集合的無序積,無序積的定義 設(shè) A、B 是任意集合。集合 稱為 A 和 B 的無序積，記為 。,例1 若 ，則,在 中為什么沒有 這一項(xiàng)？,例題講解,6.1 圖的基本概念,一、圖的定義 1、無向圖及相關(guān)概念,定義6.1 無向圖 G 是一個(gè)二元組 ，記作 ，其中 （1） 稱為頂點(diǎn)集，其元素稱為頂點(diǎn)或結(jié)點(diǎn)； （2）E 稱為邊集，它是 的多重子集，其元素稱為無向邊，簡稱為邊。,例題講解,例2 無向圖 ，其中,畫出其無向圖如

3、 P.218 圖11.1所示。,P.218，例11.1.1,在無向圖 中，若 e = (vi ,vj) 是 G 的一條邊，則稱 vi 和 vj 是邊 e 的端點(diǎn)，稱 e 關(guān)聯(lián)于 vi 和 vj ，并稱 vi 和 vj 是相接的或相鄰的。,v1 , v2,e1,基本術(shù)語,關(guān)聯(lián)于同一頂點(diǎn)的邊稱為自回路；關(guān)聯(lián)于同一對頂點(diǎn) u 和 v 的邊多于一條時(shí)，稱這些邊為平行邊，其條數(shù)稱為邊（u , v）的重?cái)?shù)；不與任何頂點(diǎn)相聯(lián)的點(diǎn)稱為孤立點(diǎn)。 實(shí)例說明：參見 P.218 圖11.1。,零圖 全由孤立點(diǎn)組成的圖。 多重圖 含有平行邊的圖。 線圖 非多重圖。 簡單圖 無自回路的線圖。 平凡圖 只有一個(gè)頂點(diǎn)而無邊的

4、圖。 有限圖 頂點(diǎn)集和邊集均為有限集合的圖。,無向圖的分類,例題講解,例3 指出圖11.2中各圖屬于哪一類？,P.219，例11.1.2,3、有向圖及相關(guān)概念 定義,定義11.1.3 有向圖 G 是一個(gè)二元組 ，記為 ，其中 （1） 稱為頂點(diǎn)集，其元素稱為頂點(diǎn)或結(jié)點(diǎn)； （2）E 稱為邊集，它是 的多重子集，其元素稱為有向邊或孤，簡稱為邊。,例題講解,例4 有向圖 ，其中,畫出其有向圖如 P.219 圖11.3所示。,P.219，例11.1.3,關(guān)聯(lián)、自回路、平行邊、重?cái)?shù)、孤立點(diǎn)等概念與無向圖中的定義類似。補(bǔ)充以下概念： 1）若 是有向圖 G 的一條邊時(shí)，則稱 u 是 e 的始點(diǎn)，v 是 e 的

5、終點(diǎn)。 2）去掉有向圖中邊的箭頭所得到的圖稱為該有向圖的底圖。,基本術(shù)語,二、頂點(diǎn)的度數(shù) 1、定義,定義11.1.4 （1）無向圖 與 v 關(guān)聯(lián)的邊數(shù)（每個(gè)自回路算兩次）稱為 v 的度數(shù)（簡稱度），記為 deg(v)。 （2）有向圖 以 v 為始點(diǎn)的邊數(shù)稱為 v 的出度，記為 deg+(v)；以 v 為終點(diǎn)的邊數(shù)稱為 v 的入度，記為 deg-(v) ；稱deg+(v) + deg-(v) 為 v 的度數(shù)（簡稱度），記為 deg(v) 。,例題講解,例5 指出 P.218 圖11.1 和 P.219 圖11.3 中每個(gè)頂點(diǎn)的度數(shù)。,P.220，例11.1.4,定理11.1.1 設(shè)圖 ，則,2、

6、性質(zhì),性質(zhì)1,推論11.1.1 任何圖中度為奇數(shù)的頂點(diǎn)數(shù)必為偶數(shù)。,性質(zhì)2,定理11.1.3 在有向圖 中有,性質(zhì)3,課堂實(shí)訓(xùn),（1）無向圖 ，其中， （2）給定有向圖 ，其中，,畫出圖并寫出各頂點(diǎn)的度數(shù)（含出度和入度）。,三、子圖,定義11.1.5 設(shè)圖 和 。 （1）若 ，則稱 G 是 G 的子圖，記為 。 （2）若 ，則稱 G 是 G 的真子圖，記為 。 （3）若 ，則稱 G 是 G 的生成子圖或支撐子圖。,定義11.1.5（續(xù)）,（4）若 ，且 E 是所有兩端點(diǎn)均在 V 中的G 的邊組成的集合，則稱 G 是由 V 導(dǎo)出的 G 的子圖。 （5）若 ，則稱 G 是由 E 導(dǎo)出的 G 的子圖

7、。,例題講解,例6 指出下圖中(b) (d)圖是(a)圖的何種子圖？,a,b,c,d,e,(a),P.221，例11.1.5,四、完全圖、補(bǔ)圖 1、完全圖,定義11.1.6 （1）設(shè)圖 是無向簡單圖， 。若 G 中任何頂點(diǎn)都與其余 個(gè)頂點(diǎn)鄰接，則稱 G 是無向完全圖，記為Kn。 （2）設(shè)圖 是有向簡單圖， 。若 ，則稱 G 是有向完全圖，記為Kn。,例題講解,例7 P.222圖11.5中全部都是完全圖。,a,b,c,e,a,b,c,d,e,a,b,d,e,例8 P.221圖11.4中哪些是完全圖?哪些不是完全圖？把不是的補(bǔ)充成為完全圖。,a,b,c,d,e,2、補(bǔ)圖,定義11.1.7 設(shè) 是簡單圖， ， 。若 ， 則稱 H 是 G 的補(bǔ)圖，記為 （這里 表示 Kn 的邊集）。,例題講解,a,b,c,e,a,b,c,d,e,a,b,d,e,例9 求下列各圖的補(bǔ)圖。,a,c,d,e,b,五、圖的同構(gòu) 1、定義,定義11.1.8 設(shè)圖 。 若存在雙射 ，使得 當(dāng)且僅當(dāng) 的重?cái)?shù)相等，則稱 G1 與