最新離散數(shù)學(xué)第7章教學(xué)講義ppt.ppt

《最新離散數(shù)學(xué)第7章教學(xué)講義ppt.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、離散數(shù)學(xué)第7章圖論是一個(gè)古老的數(shù)學(xué)分支，它起源于游戲難題的研究。圖論的內(nèi)容十分豐富，應(yīng)用得相當(dāng)廣泛，許多學(xué)科，諸如運(yùn)籌學(xué)、信息論、控制論、網(wǎng)絡(luò)理論、博弈論、化學(xué)、生物學(xué)、物理學(xué)、社會(huì)科學(xué)、語(yǔ)言學(xué)、計(jì)算機(jī)科學(xué)等，都以圖作為工具來(lái)解決實(shí)際問(wèn)題和理論問(wèn)題。隨著計(jì)算機(jī)科學(xué)的發(fā)展，圖論在以上各學(xué)科中的作用越來(lái)越大，同時(shí)圖論本身也得到了充分的發(fā)展。本課程在第七，八，九各章中介紹與計(jì)算機(jī)科學(xué)關(guān)系密切的圖論的內(nèi)容。第七章圖的基本概念第一節(jié)無(wú)向圖及有向圖一、圖的概念。1、定義。無(wú)序積2、圖的表示法。有向圖，無(wú)向圖的頂點(diǎn)都用小圓圈表示。無(wú)向邊——連接頂點(diǎn)的線段。有向邊——以為始點(diǎn)，以為終點(diǎn)的

2、有向線段。例1、(1)無(wú)向圖，圖形表示如右：圖形表示如右：例1、(2)有向圖，3、相關(guān)概念。(1)有限圖——都是有限集的圖。階圖——的圖。零圖——的圖。特別，若又有，稱(chēng)平凡圖。(2)關(guān)聯(lián)(邊與點(diǎn)關(guān)系)——設(shè)邊(或)，則稱(chēng)與(或)關(guān)聯(lián)。3、相關(guān)概念。(2)3、相關(guān)概念。(2)孤立點(diǎn)——無(wú)邊關(guān)聯(lián)的點(diǎn)。環(huán)——一條邊關(guān)聯(lián)的兩個(gè)頂點(diǎn)重合，稱(chēng)此邊為環(huán)(即兩頂點(diǎn)重合的邊)。3、相關(guān)概念。(2)懸掛點(diǎn)——只有一條邊與其關(guān)聯(lián)的點(diǎn)，所對(duì)應(yīng)的邊叫懸掛邊。(3)平行邊——關(guān)聯(lián)于同一對(duì)頂點(diǎn)的若干條邊稱(chēng)為平行邊。平行邊的條數(shù)稱(chēng)為重?cái)?shù)。多重圖——含有平行邊的圖。簡(jiǎn)單圖——不含平行邊和環(huán)的圖。如例1的(

3、1)中，與關(guān)聯(lián)的次數(shù)均為1，與關(guān)聯(lián)的次數(shù)為2，邊都是相鄰的，為孤立點(diǎn)，為懸掛點(diǎn)，為懸掛邊，為環(huán)，為平行邊，重?cái)?shù)2，為多重圖。4、完全圖設(shè)為階無(wú)向簡(jiǎn)單圖，若中每個(gè)頂點(diǎn)都與其余個(gè)頂點(diǎn)相鄰，則稱(chēng)為階無(wú)向完全圖，記作。若有向圖的任一對(duì)頂點(diǎn)，既有有向邊又有有向邊，則稱(chēng)為有向完全圖。例如：二、頂點(diǎn)的度數(shù)，握手定理。1、頂點(diǎn)的度數(shù)(簡(jiǎn)稱(chēng)度)。無(wú)向圖的度數(shù)記，指與，相關(guān)聯(lián)的邊的條數(shù)。有向圖的度數(shù)，二、頂點(diǎn)的度數(shù)，握手定理。1、頂點(diǎn)的度數(shù)(簡(jiǎn)稱(chēng)度)。最大度最小度對(duì)有向圖相應(yīng)地還有，，，。如例1的(2)中，，。設(shè)為圖的頂點(diǎn)集，稱(chēng)為的度數(shù)序列。2、握手定理。定理1：設(shè)圖為無(wú)向圖或有向圖，為邊數(shù)

4、)，，(則定理2：設(shè)為有向圖，，則，。2、握手定理推論：任何圖中，度為奇數(shù)的頂點(diǎn)個(gè)數(shù)為偶數(shù)。例2、(1)能成為圖的度數(shù)，序列嗎？為什么？(2)已知圖中有10條邊，4個(gè)3度頂點(diǎn)，其余頂點(diǎn)的度數(shù)均小于3，問(wèn)中至少有多少個(gè)頂點(diǎn)？為什么？三、子圖，補(bǔ)圖。1、子圖定義：設(shè)是兩個(gè)圖，若，，且，則稱(chēng)是的子圖，是的母圖，記作。真子圖——且(即或)。生成子圖——且。三、子圖，補(bǔ)圖。導(dǎo)出子圖——非空，以為頂點(diǎn)集，以兩端均在中的邊的全體為邊集的的子圖，稱(chēng)的導(dǎo)出子圖?！强?，以為邊集，以中邊關(guān)聯(lián)的頂點(diǎn)的全體為頂點(diǎn)集的的子圖，稱(chēng)的導(dǎo)出子圖。例3、上圖中，(1)－(6)都是(1)的子圖，其中(2)

5、－(6)為真子圖，(1)－(5)為生成子圖。2、補(bǔ)圖定義。設(shè)為無(wú)向完全圖，，為無(wú)向簡(jiǎn)單圖，其中，，則稱(chēng)，相對(duì)于互為補(bǔ)圖，記，。如例3中，四、圖的同構(gòu)。定義：設(shè)兩個(gè)無(wú)向圖，，若存在雙射函數(shù)，使得對(duì)于任意的，當(dāng)且僅當(dāng)并且與重?cái)?shù)相同，則稱(chēng)與同構(gòu)，記作。例4、例5、(1)畫(huà)出4個(gè)頂點(diǎn)，3條邊的所有非同構(gòu)的無(wú)向簡(jiǎn)單圖。解：只有如下3個(gè)圖：例5、(2)畫(huà)出3個(gè)頂點(diǎn)，2條邊的所有非同構(gòu)的有向簡(jiǎn)單圖。解：只有如下4個(gè)圖：第二節(jié)通路，回路，圖的連通性內(nèi)容：圖的通路，回路，連通性。重點(diǎn)：1、通路，回路，簡(jiǎn)單通路，回路，初級(jí)通路，回路的定義，2、圖的連通性的概念，3、短程線，距離的概念。一、通

6、路，回路。1、通路(回路)中頂點(diǎn)和邊的交替序列——，其中(無(wú)向圖)，或(有向圖)，——始點(diǎn)，——終點(diǎn)，稱(chēng)為到的通路。當(dāng)時(shí)，為回路。一、通路，回路。2、簡(jiǎn)單通路，簡(jiǎn)單回路。簡(jiǎn)單通路(跡)簡(jiǎn)單回路(閉跡)復(fù)雜通路(回路)一、通路，回路。3、初級(jí)通路，初級(jí)回路。初級(jí)通路(路徑)初級(jí)回路(圈)初級(jí)通路(回路)簡(jiǎn)單通路(回路)，但反之不真。4、通路，回路的長(zhǎng)度——中邊的數(shù)目。例1、(1)圖(1)中，從的通路有：到…………長(zhǎng)度3長(zhǎng)度6長(zhǎng)度6例1、(1)圖(1)中，從的通路有：到…………初級(jí)通路簡(jiǎn)單通路復(fù)雜通路例1、(2)…………長(zhǎng)度3長(zhǎng)度4長(zhǎng)度7圖(2)中過(guò))有：的回路(從到例1、(

7、2)…………初級(jí)回路(圈)初級(jí)回路(圈)復(fù)雜回路圖(2)中過(guò))有：的回路(從到5、圖中最短的回路。如圖：6、性質(zhì)。定理：階圖中，若從頂點(diǎn)到存在通路，則從到存在長(zhǎng)度小于等于在一個(gè)的通路。推論：階圖中，若從頂點(diǎn)到存在通路，則從到存在長(zhǎng)度小于等于在一個(gè)的初級(jí)通路。6、性質(zhì)。定理：階圖中，若到自身存在回路，則從到自身存在長(zhǎng)度小于等于的回路。在一個(gè)推論：階圖中，若到自身存在一個(gè)簡(jiǎn)單回路，則從到自身存在長(zhǎng)度小于等于的初級(jí)回路。在一個(gè)6、性質(zhì)。由以上定理可知，在階圖中，任何一條初級(jí)通路的長(zhǎng)度任何一條初級(jí)回路的長(zhǎng)度二、圖的連通性。1、連通，可