離散數(shù)學教學課件：第7章 圖的基本概念

圖論簡介圖論是一個古老的數(shù)學分支，它起源于游戲難題的研究。圖論的內(nèi)容十分豐富，應用得相當廣泛，許多學科，諸如運籌學、信息論、控制論、網(wǎng)絡理論、博弈論、化學、生物學、物理學、社會科學、語言學、計算機科學等，都以圖作為工具來解決實際問題和理論問題。隨著計算機科學的發(fā)展，圖論在以上各學科中的作用越來越大，同時圖論本身也得到了充分的發(fā)展。本課程在第七，八，九各章中介紹與計算機科學關(guān)系密切的圖論的內(nèi)容。

第七章

圖的基本概念

第一節(jié)

無向圖及有向圖

內(nèi)容：有向圖，無向圖的基本概念。重點：1、有向圖，無向圖的定義，

2、圖中頂點，邊，關(guān)聯(lián)與相鄰，頂點度數(shù)等基本概念，3、各頂點度數(shù)與邊數(shù)的關(guān)系及推論，內(nèi)容：有向圖，無向圖的基本概念。5、圖的同構(gòu)的定義。重點：4、簡單圖，完全圖，子圖，補圖的概念，一、圖的概念。1、定義。無序積無向圖中元素為無向邊，簡稱邊。，有向圖中元素為有向邊，簡稱邊。，一、圖的概念。1、定義。無序積2、圖的表示法。有向圖，無向圖的頂點都用小圓圈表示。無向邊——連接頂點的線段。有向邊——以為始點，以為終點的有向線段。例1、(1)無向圖，圖形表示如右：圖形表示如右：例1、(2)有向圖，3、相關(guān)概念。(1)有限圖——都是有限集的圖。階圖——的圖。零圖——的圖。特別，若又有，稱平凡圖。(2)關(guān)聯(lián)

(邊與點關(guān)系)——設(shè)邊(或)，則稱與(或)關(guān)聯(lián)。3、相關(guān)概念。(2)3、相關(guān)概念。(2)孤立點——無邊關(guān)聯(lián)的點。環(huán)——一條邊關(guān)聯(lián)的兩個頂點重合，稱此邊為環(huán)

(即兩頂點重合的邊)。3、相關(guān)概念。(2)懸掛點——只有一條邊與其關(guān)聯(lián)的點，所對應的邊叫懸掛邊。(3)平行邊——關(guān)聯(lián)于同一對頂點的若干條邊稱為平行邊。平行邊的條數(shù)稱為重數(shù)。多重圖——含有平行邊的圖。簡單圖——不含平行邊和環(huán)的圖。如例1的(1)中，與關(guān)聯(lián)的次數(shù)均為1，與關(guān)聯(lián)的次數(shù)為2，邊都是相鄰的，為孤立點，為懸掛點，為懸掛邊，為環(huán)，為平行邊，重數(shù)2，

為多重圖。4、完全圖設(shè)為階無向簡單圖，若中每個頂點都與其余個頂點相鄰，則稱

為階無向完全圖，記作。若有向圖的任一對頂點，既有有向邊又有有向邊，則稱為有向完全圖。例如：二、頂點的度數(shù)，握手定理。1、頂點的度數(shù)

(簡稱度)。無向圖的度數(shù)記，指與，相關(guān)聯(lián)的邊的條數(shù)。有向圖的度數(shù)，二、頂點的度數(shù)，握手定理。1、頂點的度數(shù)

(簡稱度)。最大度

最小度對有向圖相應地還有，，，。如例1的(2)中，，。設(shè)為圖的頂點集，稱

為的度數(shù)序列。2、握手定理。定理1：設(shè)圖為無向圖或有向圖，為邊數(shù))，，(則定理2：設(shè)為有向圖，，則，。2、握手定理推論：任何圖中，度為奇數(shù)的頂點個數(shù)為偶數(shù)。

例2、(1)能成為圖的度數(shù)

，序列嗎？為什么？(2)已知圖中有10條邊，4個3度頂點，其余頂點的度數(shù)均小于3，問中至少有多少個頂點？為什么？三、子圖，補圖。1、子圖定義：設(shè)是兩個圖，若，，且，則稱是的子圖，是的母圖，記作。真子圖——且(即或)。生成子圖——且。三、子圖，補圖。導出子圖——非空，以為頂點集，以兩端均在中的邊的全體為邊集的的子圖，稱的導出子圖?！强?，以為邊集，以中邊關(guān)聯(lián)的頂點的全體為頂點集的的子圖，稱的導出子圖。例3、上圖中，(1)－(6)都是(1)的子圖，其中(2)－(6)為真子圖，(1)－(5)為生成子圖。2、補圖定義。設(shè)為無向完全圖，，為無向簡單圖，其中，，則稱，相對于互為補圖，記，。如例3中，四、圖的同構(gòu)。定義：設(shè)兩個無向圖，，若存在雙射函數(shù)，使得對于任意的，當且僅當并且與重數(shù)相同，則稱與同構(gòu)，記作。例4、例5、(1)畫出4個頂點，3條邊的所有非同構(gòu)的無向簡單圖。解：只有如下3個圖：例5、(2)畫出3個頂點，2條邊的所有非同構(gòu)的有向簡單圖。解：只有如下4個圖：第二節(jié)

通路，回路，圖的連通性

內(nèi)容：圖的通路，回路，連通性。重點：1、通路，回路，簡單通路，回路，初級通路，回路的定義，2、圖的連通性的概念，3、短程線，距離的概念。一、通路，回路。1、通路

(回路)中頂點和邊的交替序列——，其中(無向圖)，或(有向圖)，——始點，——終點，稱為到的通路。當時，為回路。一、通路，回路。2、簡單通路，簡單回路。簡單通路

(跡)簡單回路

(閉跡)復雜通路

(回路)一、通路，回路。3、初級通路，初級回路。初級通路

(路徑)初級回路

(圈)初級通路

(回路)簡單通路

(回路)，但反之不真。4、通路，回路的長度——中邊的數(shù)目。例1、(1)圖(1)中，從的通路有：到…………長度3長度6長度6例1、(1)圖(1)中，從的通路有：到…………初級通路簡單通路復雜通路例1、(2)…………長度3長度4長度7圖(2)中過)有：的回路

(從到例1、(2)…………初級回路(圈)初級回路(圈)復雜回路圖(2)中過)有：的回路

(從到5、圖中最短的回路。如圖：6、性質(zhì)。定理：階圖中，若從頂點到存在通路，則從到存在長度小于等于在一個的通路。推論：階圖中，若從頂點到存在通路，則從到存在長度小于等于在一個的初級通路。6、性質(zhì)。定理：階圖中，若到自身存在回路，則從到自身存在長度小于等于的回路。在一個推論：階圖中，若到自身存在一個簡單回路，則從到自身存在長度小于等于的初級回路。在一個6、性質(zhì)。由以上定理可知，在階圖中，任何一條初級通路的長度任何一條初級回路的長度二、圖的連通性。1、連通，可達。無向圖中，從到存在通路，稱到是連通的(雙向)。有向圖中，從到存在通路，稱可達(注意方向)。2、短程線，距離。短程線——連通或可達的兩點間長度最短的通路。距離——短程線的長度，記無向圖有向圖2、短程線，距離。若之間無通路(或不可達)，規(guī)定距離滿足：(1)，時，等號成立。

(2)若是無向圖，還具有對稱性，。3、無向圖的連通。為連通圖——是平凡圖，或都是連通的。中任兩點為非連通圖——中至少有兩點不連通。3、無向圖的連通。設(shè)是一個無向圖，是中頂點之間的連通關(guān)系，則是等價關(guān)系。設(shè)將劃分成個等價類：，由它們導出的子圖稱為的連通分支，其個數(shù)記為4、有向圖的連通?！腥我粚旤c都互相可達(雙向)——中任一對頂點至少一向可達——略去中有向邊的方向后得到的無向圖連通連通強連通單向連通弱連通強連通單向連通弱連通例2、強連通單向連通例2、單向連通弱連通非連通圖第三節(jié)

圖的矩陣表示內(nèi)容：關(guān)聯(lián)矩陣，鄰接矩陣，可達矩陣。重點：1、有向圖，無向圖的關(guān)聯(lián)矩陣，2、有向圖的鄰接矩陣。了解：有向圖的可達矩陣。一、無向圖的關(guān)聯(lián)矩陣。1、設(shè)無向圖，，，的關(guān)聯(lián)矩陣，例1、無向圖(下圖所示)，求。解：2、性質(zhì)。(1)(2)(3)握手定理(4)，當且僅當為孤立點。2、性質(zhì)。(5)若第列與第列相同，則說明與為平行邊。二、有向圖的關(guān)聯(lián)矩陣。1、設(shè)無環(huán)有向圖，，，的關(guān)聯(lián)矩陣，其中例2、有向圖(下圖所示)，求。解：2、性質(zhì)。(1)(2)(3)三、有向圖的鄰接矩陣。1、設(shè)有向圖，，的鄰接矩陣，，其中指鄰接到的邊的條數(shù)

(非負整數(shù))。例3、有向圖(下圖所示)，求。解：2、性質(zhì)。(1)(2)(3)(4)為中環(huán)的個數(shù)。3、求中長度為的通路數(shù)和回路數(shù)。(1)令矩陣乘法其中表示從到長度為2的通路數(shù)或回路數(shù)。3、求中長度為的通路數(shù)和回路數(shù)?？紤]，簡記為。其中表示從到長度為或回路數(shù)。的通路數(shù)中長度為為的通路總數(shù)，其中為中長度為的回路總數(shù)。3、求中長度為的通路數(shù)和回路數(shù)。(2)設(shè)則中元素為中到長度小于等于的通路總數(shù)，為中長度小于等于的通路總數(shù)，其中為中長度小于等于的回路總數(shù)。例4、在例3的有向圖中求，，。解：，，四、有向圖的可達性矩陣。(了解)設(shè)為有向圖，，令，四、有向圖的可達性矩陣。(了解)可達性矩陣其中元素可由求得：第七章

小結(jié)與例題一、無向圖與有向圖。1、基本概念。有向圖與無向圖的定義；關(guān)聯(lián)與鄰接(相鄰)；頂點的度數(shù)；零圖與平凡圖；簡單圖與多重圖；完全圖；子圖，補圖；圖的同構(gòu)。一、無向圖與有向圖。2、運用。(1)靈活運用握手定理及其推論，(2)判斷兩個圖是否同構(gòu)，(3)畫出滿足某些條件的子圖，補圖等。二、通路，回路，圖的連通性。1、基本概念。通路和回路；無向圖和有向圖中頂點之間的可達關(guān)系；短程線，距離；有向圖連通的分類。二、通路，回路，圖的連通性。2、運用。(1)判斷有向圖或無向圖中通路(回路)的類型。(2)求短程線和距離。(3)判斷有向圖連通的類型。三、圖的矩陣表示。1、基本概念。無向圖的關(guān)聯(lián)矩陣，有向圖的關(guān)聯(lián)矩陣和鄰接矩陣。2、運用。(1)關(guān)聯(lián)矩陣的行和、頂點度數(shù)間的關(guān)系。(2)由有向圖的鄰接矩陣的次冪求從一頂點到另一頂點的長度為的通路數(shù)。例1、設(shè)圖，其中，分別由下面給出。判斷哪些是簡單圖，哪些是多重圖？(1)(2)(3)簡單圖多重圖不是例1、設(shè)圖，其中，分別由下面給出。判斷哪些是簡單圖，哪些是多重圖？(4)(5)(6)簡單圖多重圖不是例2、下列各序列中，可以構(gòu)成無向簡單圖的度數(shù)序列的有哪些？(1)可以(2)不可以(3)可以(4)不可以(5)不可以例3、右圖所示的無向圖中，分別求：不同的初級通路(路徑)。(1)之間所有解：有7條，分別為，，，，和，。(2)之間的短程線。(3)。解：。解：。例4、(1)畫出完全圖的所有非同構(gòu)的生成子圖。解：例4、(1)畫出完全圖的所有非同構(gòu)的生成子圖。解：例4、(1)畫出完全圖的所有非同構(gòu)的生成子圖。(2)的生成子圖有幾個是連通圖？解：有6個：例5、下圖所示的六個圖中，強連通，單向連通，弱連通的分別有哪些？強連通單向連通弱連通例5、下圖所示的六個圖中，強連通，單向連通，弱連通的分別有哪些？單向連通強連通強連通例6、已知圖的鄰接矩陣，，(1)例6、已知圖的鄰接矩陣，，(2)從到長度為2的通路數(shù)。解：因，所以從到長度為2的通路數(shù)為2。例6、已知圖的鄰接矩陣，，(3)從到長度為3的通路數(shù)。解：因，所以從到長度為3的通路數(shù)為5。例6、已知圖的鄰接矩陣，，(4)過長度為3的回路數(shù)。解：因，所以過長度為3的回路數(shù)為3。例7、下列各圖中各有多少個頂點。(1)16條邊，每個頂點的度數(shù)均為2。解：設(shè)頂點數(shù)為，由握手定理，有，解得。解：設(shè)頂點數(shù)為，解得。(2)21條邊，3個度數(shù)為4的頂點，其余頂點的度數(shù)均為3。有，由握手定理，例7、下列各圖中各有多少個頂點。(3)24條邊，每個頂點的度數(shù)均相同。解：設(shè)頂點數(shù)為，由握手定理，設(shè)每個頂點的度數(shù)均為，其正整數(shù)解有：，，，，，，，。，則有例7、下列各圖中各有多少個頂點。(3)24條邊，每個頂點的度數(shù)均相同。