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

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

1、第7章圖論7.1圖的基本概念7.2路與回路7.3圖的矩陣表示7.4歐拉圖7.5哈密爾頓圖7.6樹(shù)7.7二部圖和平面圖第7章圖論7.1.1圖的基本類(lèi)型定義7.1所謂圖G是一個(gè)三元組，G=，其中V(G)是一個(gè)非空的結(jié)點(diǎn)集合，E（G）是邊的集合，φG是從邊集合E到結(jié)點(diǎn)無(wú)序偶或有序偶集合上的函數(shù)。定義7.2如果兩個(gè)結(jié)點(diǎn)之間有多條邊（對(duì)于有向圖，則有多條同方向的邊），則稱(chēng)這些邊為平行邊，兩相結(jié)點(diǎn)a，b間平行邊的條數(shù)稱(chēng)為邊的重?cái)?shù)。含有平行邊的圖稱(chēng)為多重圖，不含平行邊和自回路的圖稱(chēng)為簡(jiǎn)單圖

2、。第7章圖論7.1.2圖中結(jié)點(diǎn)的度數(shù)1．無(wú)向圖中結(jié)點(diǎn)的度數(shù)定義7.3設(shè)圖G是無(wú)向圖，v是圖G中的結(jié)點(diǎn)，所有與v關(guān)聯(lián)的邊的條數(shù)，稱(chēng)為點(diǎn)v的度數(shù)，記作deg(v)。定理7.1設(shè)圖G是具有n個(gè)點(diǎn)，m條邊的無(wú)向圖，其中結(jié)點(diǎn)集合為V={v1，v2，…，vn}，則第7章圖論7.1.2圖中結(jié)點(diǎn)的度數(shù)2．有向圖中結(jié)點(diǎn)的度數(shù)定義7.5設(shè)圖G是有向圖，v是圖G中的結(jié)點(diǎn)，以v為始點(diǎn)的有向邊的條數(shù)稱(chēng)為v的出度，記個(gè)deg+(v)，以v為終點(diǎn)的有向邊的條數(shù)稱(chēng)為v的入度，記作deg－(v)。定理7.2設(shè)有向圖G具有n個(gè)結(jié)點(diǎn)，m條邊

3、，其中結(jié)點(diǎn)構(gòu)成的集合V={v1，v2，…，vn}，則有第7章圖論7.1.3完全圖1．無(wú)向完全圖定義7.6在n階無(wú)向圖中，如果任意兩個(gè)不同的結(jié)點(diǎn)之間都有一條邊關(guān)聯(lián)，則稱(chēng)此無(wú)向圖為無(wú)向完全圖，記作Kn。定理7.3n個(gè)結(jié)點(diǎn)的無(wú)向完全圖Kn的邊數(shù)是。第7章圖論7.1.3完全圖2．有向完全圖定理7.4n個(gè)結(jié)點(diǎn)的有向完全圖Kn的邊數(shù)是n2。定義7.7在n階有向圖中，如果任意兩個(gè)結(jié)點(diǎn)都有兩條方向相反的有向邊關(guān)聯(lián)，且每一個(gè)結(jié)點(diǎn)都有自回路，則稱(chēng)此有向圖為有向完全圖。第7章圖論7.1.3完全圖3．競(jìng)賽圖定義7.8設(shè)G為n階

4、有向圖，如果G的底圖為無(wú)向完全圖Kn，則稱(chēng)G為競(jìng)賽圖。第7章圖論7.1.4圖的同構(gòu)定義7.9設(shè)圖G的點(diǎn)集為V，邊集為E，圖G′的點(diǎn)集為V′，邊集為E′。如果存在著V到V′的雙射函數(shù)f，使對(duì)任意的u，vV，(u，v)E（或E），當(dāng)且僅當(dāng)（f（u），f（v））E′（或E′），則稱(chēng)圖G和G′同構(gòu)，記作GG′。第7章圖論7.1.5補(bǔ)圖定義7.10設(shè)G=為任意的n階無(wú)向簡(jiǎn)單圖，則所有使G成為Kn添加的邊和G的n個(gè)結(jié)點(diǎn)構(gòu)成的圖稱(chēng)為圖G的補(bǔ)圖，記作。定義7.11設(shè)G=

5、>是任意一個(gè)n階無(wú)向圖，V={v1，v2，…，vn}，稱(chēng)d（v1），d（v2），…，d（vn）為G的度數(shù)列。對(duì)于結(jié)點(diǎn)標(biāo)定的無(wú)向圖，它的度數(shù)列是唯一的。反之，對(duì)于給定的非負(fù)整數(shù)列d=（d1，d2，…，dn），若存在以V={v1，v2，…，vn}為結(jié)點(diǎn)n階無(wú)向圖G，使得d（vi）=di，則稱(chēng)d是可圖化的。特別地，若得到的圖是簡(jiǎn)單圖，則稱(chēng)d是可簡(jiǎn)單圖化的。第7章圖論7.1.5補(bǔ)圖定理7.5設(shè)非負(fù)整數(shù)列d=（d1，d2，…，dn），當(dāng)且僅當(dāng)為偶數(shù)時(shí)，d是可圖化的。定理7.6設(shè)非負(fù)整數(shù)列d=（d1，d2，…，dn

6、），（n-1）≥d1≥d2≥…≥dn≥0，則d是可簡(jiǎn)單圖化的，當(dāng)且僅當(dāng)對(duì)于每個(gè)整數(shù)r，1≤r≤（n-1），≤r（r-1）+且為偶數(shù)。定理7.7設(shè)非負(fù)整數(shù)列d=（d1，d2，…，dn），（n-1）≥d1≥d2≥…≥dn≥0，則d是可簡(jiǎn)單化的當(dāng)且僅當(dāng)d′=（-1，-1，…，-1，，…，）。第7章圖論7.1.6子圖定義7.12設(shè)G=和G=是兩個(gè)圖，（1）若V'?V且E'?E，則稱(chēng)G'是G的子圖；（2）若G'是G的子圖，但V'≠V或E'≠E，則稱(chēng)G'是G的真子圖；（3）若G‘是G的子圖，

7、且V’=V，則稱(chēng)G‘是G的生成子圖或支撐子圖。第7章圖論7.2路與回路7.2.1通路與回路定義7.13在無(wú)向圖（或有向圖）G=中，設(shè)v0，v1，…，vn∈V，e0，e1，…，en∈E，其中ei是關(guān)聯(lián)于結(jié)點(diǎn)vi-1，vi的邊，交替序列v0e0v1e1…en-1vn稱(chēng)為聯(lián)結(jié)v0到vn的通路或路。v0和vn分別稱(chēng)為通路的起點(diǎn)和終點(diǎn)，通路中所含邊的條數(shù)稱(chēng)為該通路的長(zhǎng)度。如果通路中的始點(diǎn)與終點(diǎn)相同，則稱(chēng)這條路為回路。第7章圖論7.2路與回路7.2.1通路與回路定理7.8在n階無(wú)向圖中，如果存在一條從vi

8、到vj的通路，則從vi到vj必有一條長(zhǎng)度不大于n-1的基本通路。定理7.9在n階無(wú)向圖中，如果存在一條通過(guò)vi的回路，則必有一條長(zhǎng)度不大于n的通過(guò)vi的基本回路。第7章圖論7.2路與回路7.2.2圖的連通性1．無(wú)向圖的連通性定義7.14設(shè)圖G是無(wú)向圖，u和v是圖G中的兩個(gè)結(jié)點(diǎn)，如果u和v之間有通路，則稱(chēng)u，v是連通的，并規(guī)定u與自身是連通的。定義7.15若圖G是平凡圖或G中任意兩點(diǎn)都是連通的，則稱(chēng)圖G為連通圖，否則稱(chēng)G為非連通圖或分離圖。第