離散數(shù)學(xué) 賈振華 第七章 圖

《離散數(shù)學(xué) 賈振華 第七章 圖》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第7章圖本章學(xué)習(xí)目標(biāo)在前面章節(jié)中介紹過二元關(guān)系的圖形表示，即關(guān)系圖。在關(guān)系圖中，我們主要關(guān)心研究對(duì)象之間是否有連線（圖論中稱為邊），這樣的圖正是圖論的主要研究對(duì)象。圖論中還根據(jù)實(shí)際需要，將此類圖進(jìn)行了推廣，并且把它當(dāng)作一個(gè)抽象的數(shù)學(xué)系統(tǒng)來進(jìn)行研究。通過本章學(xué)習(xí)，讀者應(yīng)該掌握以下內(nèi)容：本章學(xué)習(xí)目標(biāo)（1）無向圖、有向圖的定義，圖的基本術(shù)語（2）子圖、生成子圖的概念（3）補(bǔ)圖、圖的同構(gòu)的概念（4）通路、簡單通路、初級(jí)通路的概念及相關(guān)定理（5）回路、簡單回路、初級(jí)回路的概念及相關(guān)定理（6）無向連通圖及有向連通圖的有關(guān)概念（7）圖的矩陣表示（8）帶權(quán)圖及其應(yīng)用：最短路徑問題和關(guān)

2、鍵路徑問題主要內(nèi)容7.1圖的基本概念7.2通路與回路7.3圖的連通性7.4圖的矩陣表示7.5圖的應(yīng)用7.1圖的基本概念7.1.1圖論的發(fā)展(a)(b)哥尼斯堡七橋問題7.1圖的基本概念7.1.2圖的基本概念(a)(b)定義7.1.1無向圖G是由一個(gè)頂點(diǎn)（結(jié)點(diǎn)）集合V（≠φ）和邊E（弧）集合構(gòu)成，并且每條邊e∈Ｅ連接一個(gè)無序的頂點(diǎn)對(duì)。如果存在唯一的一條邊ｅ連接頂點(diǎn)ｕ和ｖ，那么就記作ｅ=（ｕ，ｖ）或ｅ=（ｖ，ｕ）。有向圖Ｄ是由一個(gè)頂點(diǎn)（結(jié)點(diǎn)）集合Ｖ（≠φ）和邊（?。┘希艠?gòu)成，并且每條邊連接一個(gè)有序的頂點(diǎn)對(duì)。如果存在唯一的一條邊ｅ連接頂點(diǎn)的有序?qū)Γ鹾停?那么就記作ｅ=＜ｕ

3、，ｖ＞，表示一條從頂點(diǎn)ｕ到頂點(diǎn)ｖ的邊。如果圖Ｇ（無向圖或有向圖）由頂點(diǎn)集合Ｖ和邊集合Ｅ組成，就記作Ｇ＝＜Ｖ，Ｅ＞。在定義中，常用表示Ｇ無向圖，Ｄ表示有向圖。7.1圖的基本概念7.1.2圖的基本概念例7.1.1畫出下面二圖的圖形（1）無向圖　　　　　　　　，其中7.1圖的基本概念7.1.2圖的基本概念例7.1.1畫出下面二圖的圖形（２）有向圖　　　　　　　　，其中7.1圖的基本概念7.1.2圖的基本概念例7.1.1畫出下面二圖的圖形解：(1)的圖形為7.1-3（a）所示，（2）的圖形為7.1-3（b）所示。7.1圖的基本概念7.1.2圖的基本概念定義7.1.2設(shè)無向圖（

4、1）如果在頂點(diǎn)ｕ和頂點(diǎn)ｖ之間存在一條邊，即若存ｅ∈Ｅ在且ｅ=(u,v)，則稱頂點(diǎn)u和頂點(diǎn)v是彼此相鄰的，簡稱相鄰的，并稱頂點(diǎn)u和頂點(diǎn)v是邊e的端點(diǎn)，e與u（或e與v）是彼此關(guān)聯(lián)的。（2）若ek,el至少有一個(gè)公共端點(diǎn)，則稱邊ek,el是彼此相鄰的，簡稱相鄰的。7.1圖的基本概念7.1.2圖的基本概念定義7.1.3含有平行邊的圖，稱為多重圖。定義7.1.4一個(gè)沒有環(huán)又沒有平行邊的圖，稱為簡單圖。定義7.1.5設(shè)無向圖G=，對(duì)于任意的v∈V，將所有與v關(guān)聯(lián)的邊的條數(shù)，稱為v的度數(shù)，簡稱度，記作dG(v)，簡記為d(v)。設(shè)有向圖D，對(duì)于任意的v∈V，將

5、v作為D中邊的始點(diǎn)的邊的條數(shù)，稱為v的出度，記作，簡記為；將v作為D中邊的終點(diǎn)的邊的條數(shù)，稱為v的入度，記作，簡記為；稱+為v的度數(shù)，記作，簡記為。7.1圖的基本概念7.1.2圖的基本概念設(shè)G為無向圖，記=，，分別稱為無向圖的最大度和最小度。例如在圖7.1-5中，=4，=3。7.1圖的基本概念7.1.2圖的基本概念設(shè)D為一個(gè)有向圖，類似可定義D中的最大度和最小度。另外，令分別稱、、、為D的最大出度、最小出度、最大入度、最小入度。7.1圖的基本概念7.1.2圖的基本概念定理7.1.1設(shè)是有m條邊的圖，則。證明因?yàn)镚中每一條邊（包括環(huán)）均有兩個(gè)端點(diǎn)，而一條邊恰好關(guān)聯(lián)2個(gè)（

6、可能相同）頂點(diǎn)。因此，在一個(gè)圖中，頂點(diǎn)度數(shù)的總和等于邊數(shù)的兩倍。7.1圖的基本概念7.1.2圖的基本概念推論在任何圖（無向圖或有向圖）中，度為奇數(shù)的頂點(diǎn)的個(gè)數(shù)為偶數(shù)。證明設(shè)V1和V2分別是中奇數(shù)度數(shù)和偶數(shù)度數(shù)的頂點(diǎn)集，則由定理7.1.1有(m為的邊數(shù))由于和2m均為偶數(shù)，所以必為偶數(shù)，即

7、V1

8、為偶數(shù)。7.1圖的基本概念7.1.2圖的基本概念定理7.1.2任何有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和。證明：設(shè)有向圖D有m條邊，因?yàn)槊恳粭l有向邊為始點(diǎn)提供1個(gè)出度，為終點(diǎn)提供1個(gè)入度，而所有各頂點(diǎn)的入度之和及出度之和均由m條有向邊提供，所以定理得證。7.1圖的基

9、本概念7.1.2圖的基本概念定義7.1.6設(shè)為圖G的頂點(diǎn)集，稱（，，…,）為G的度數(shù)序列。對(duì)于頂點(diǎn)標(biāo)定的無向圖，它的度數(shù)序列是唯一的。反之，對(duì)于給定的非負(fù)整數(shù)列d=（d1，d2，…，dn），若存在以為頂點(diǎn)集的n階無向圖G，使得d(vi)=di，則稱d是可圖化的。7.1圖的基本概念7.1.2圖的基本概念定理7.1.3設(shè)非負(fù)整數(shù)列d=（d1，d2，…，dn），當(dāng)且僅當(dāng)為偶數(shù)時(shí)，d是可圖化的。例7.1.2（5，4，3，5）和（3，2，1，1，4）可圖化嗎？解由于這兩個(gè)序列中，均為奇數(shù)，由定理7.1.3可知，它們都不可圖化。7.1圖的基本概念7.1.2圖的基