離散數(shù)學(xué)：5-1-1 圖的基本概念

第三部分圖論引例——哥尼斯堡七橋問題轉(zhuǎn)化Euler(歐拉)1736年包含兩個(gè)要素：對(duì)象(陸地)對(duì)象間的二元關(guān)系(是否有橋連接)轉(zhuǎn)化問題：是否能從任一個(gè)頂點(diǎn)開始，通過每條邊恰好一次再回到起點(diǎn)？問題：是否能從A、B、C、D中的任一地開始走，通過每座橋恰好一次再回到起點(diǎn)？ABCDABCD圖論中討論的圖第三部分圖論圖論是離散數(shù)學(xué)的重要組成部分，是近代應(yīng)用數(shù)學(xué)的重要分支。

1736年是圖論歷史元年，瑞士數(shù)學(xué)家歐拉發(fā)表了關(guān)于圖論的第一篇論文，解決了著名的哥尼斯堡七橋問題。歐拉是公認(rèn)的圖論創(chuàng)始人。1936年，匈牙利數(shù)學(xué)家寇尼格出版了圖論的第一部專著《有限圖與無限圖理論》，這是圖論發(fā)展史上重要的里程碑，它標(biāo)志著圖論將進(jìn)入突飛猛進(jìn)發(fā)展的新階段。

第三部分圖論近50年來，隨著計(jì)算機(jī)科學(xué)的發(fā)展，圖論更以驚人的速度向前發(fā)展，真是異軍突起，活躍非凡。作為描述事務(wù)之間關(guān)系的手段或稱工具，圖論在許多領(lǐng)域都得到廣泛的應(yīng)用，如：計(jì)算機(jī)科學(xué)、物理學(xué)、化學(xué)、運(yùn)籌學(xué)、信息論、控制論、網(wǎng)絡(luò)理論、社會(huì)科學(xué)以及經(jīng)濟(jì)管理、軍事、國防、工農(nóng)業(yè)生產(chǎn)等方面。第三部分圖論第5章圖的基本概念第6章特殊的圖第7章樹

第5章圖的基本概念5.1無向圖與有向圖5.2通路、回路、圖的連通性5.3圖的矩陣表示5.4最短路徑和關(guān)鍵路徑5.1無向圖及有向圖無序?qū)蓚€(gè)體x，y的無序序列稱為無序?qū)?，記?x,y)。(x,y)=(y,x)無序積:

AB={(x,y)|xAyB}如A={a,b},B={c,d}

則AB={(a,c),(a,d),(b,c),(b,d)}=BA

AA={(a,a),(a,b),(b,b)}多重集合:元素可以重復(fù)出現(xiàn)的集合。無向圖無向圖G=<V,E>,

其中(1)V是非空有窮集合，其元素稱為頂點(diǎn)。(2)E為VV的多重子集，其元素稱為無向邊，簡稱邊.如G=<V,E>如圖所示,

其中V={v1,v2,…,v5},E={(v1,v1),(v1,v2),(v1,v5),

(v2,v5),(v2,v3),

(v2,v3),(v4,v5)}

有向圖有向圖D=<V,E>,

其中(1)V是非空有窮集合,其元素稱為頂點(diǎn)。(2)E為VV的多重子集，其元素

稱為有向邊，簡稱邊.如D=<V,E>如圖所示,

V={a,b,c,d}E={<a,a>,<a,b>,<a,b>,<a,d>,<b,c>,<c,d>,<d,c>}D的基圖：用無向邊代替所有有向邊所得到的圖注意：圖的數(shù)學(xué)定義與圖形表示,在同構(gòu)(待敘)的意義下是一一對(duì)應(yīng)的。無向圖與有向圖的表示通常用G表示無向圖，V(G)——G的頂點(diǎn)集E(G)——G的邊集.ek表示無向邊通常用D表示有向圖,V(D)——D的頂點(diǎn)集E(D)——D的邊集.ek表示有向邊n階圖——

n個(gè)頂點(diǎn)的圖。有限圖——

V,E都是有窮集合的圖。零圖——

E=（即無邊的圖）。平凡圖——

1階零圖（|V|=1，E=，只有一個(gè)頂點(diǎn)的圖）空?qǐng)D——

V=（無頂點(diǎn)的圖）

常用G泛指無向圖和有向圖.無向圖頂點(diǎn)和邊的關(guān)聯(lián)設(shè)ek=(vi,vj)是無向圖G=<V,E>的一條邊,稱vi,vj為ek的端點(diǎn),ek與vi(

vj)關(guān)聯(lián).若vi

vj,則稱ek與vi(

vj)的關(guān)聯(lián)次數(shù)為1;若vi=vj,則稱ek為環(huán),此時(shí)稱ek與vi的關(guān)聯(lián)次數(shù)為2;若vi不是ek端點(diǎn),則稱ek與vi的關(guān)聯(lián)次數(shù)為0.如右圖：v2,v5為e4的端點(diǎn),e4與v2(v5)關(guān)聯(lián).e1為環(huán),e1與v1

的關(guān)聯(lián)次數(shù)為2e7與v4(v5)的關(guān)聯(lián)次數(shù)為1、與v2關(guān)聯(lián)次數(shù)為0無向圖頂點(diǎn)和邊的相鄰設(shè)ek=(vi,vj)是無向圖G=<V,E>的一條邊,無邊關(guān)聯(lián)的頂點(diǎn)稱作孤立點(diǎn).若(vi,vj)E,則稱vi,vj相鄰;若ek,el至少有一個(gè)公共端點(diǎn),則稱ek,el相鄰.如右圖：孤立點(diǎn)：v6頂點(diǎn)間的相鄰：v4,v5相鄰;邊之間的相鄰：e2,e5相鄰.有向圖頂點(diǎn)和邊的相鄰設(shè)有向圖D=<V,E>,設(shè)ek=<vi,vj>是有向圖的一條邊,又稱vi是ek的始點(diǎn),vj是ek的終點(diǎn),vi鄰接到vj,vj鄰接于vi.如右圖：a是e2的始點(diǎn)，b是e2的終點(diǎn)，a鄰接到b,b鄰接于a。無向圖頂點(diǎn)的度數(shù)

設(shè)G=<V,E>為無向圖,vV,v的度數(shù)(度)

d(v):v作為邊的端點(diǎn)次數(shù)之和懸掛頂點(diǎn):度數(shù)為1的頂點(diǎn)懸掛邊:與懸掛頂點(diǎn)關(guān)聯(lián)的邊

G的最大度(G)=max{d(v)|vV}G的最小度(G)=min{d(v)|vV}如右圖

d(v1)=4,d(v4)=1,(G)=4,(G)=1,

v4是懸掛頂點(diǎn),e7是懸掛邊,e1是環(huán)

有向圖頂點(diǎn)的度數(shù)設(shè)D=<V,E>為有向圖,vV,v的出度d+(v):v作為邊的始點(diǎn)次數(shù)之和

v的入度d(v):v作為邊的終點(diǎn)次數(shù)之和

v的度數(shù)(度)d(v):v作為邊的端點(diǎn)次數(shù)之和

d(v)=d+(v)+d-(v)最大出度+(D),最小出度+(D)最大入度(D),最小入度(D)最大度(D),最小度(D)

例如

d+(a)=4,d-(a)=1,d(a)=5,d+(b)=0,d-(b)=3,d(b)=3,+(D)=4,+(D)=0,(D)=3,(D)=1,

(D)=5,(D)=3.

握手定理

定理

設(shè)圖G=<V,E>無向圖或有向圖，|V|=n，|E|=m則圖中所有頂點(diǎn)度數(shù)之和都等于邊數(shù)的2倍。有向圖的所有頂點(diǎn)入度之和等于出度之和等于邊數(shù).證:因?yàn)镚中每條邊（包括環(huán)）均有兩個(gè)端點(diǎn)，所以在計(jì)算G中各頂點(diǎn)度數(shù)之和時(shí)，每條邊均提供2度，m條邊共提供2m度.有向圖的每條邊提供一個(gè)入度和一個(gè)出度,故所有頂點(diǎn)入度之和等于出度之和，且等于邊數(shù).握手定理(續(xù))推論

任何無向圖和有向圖中奇度頂點(diǎn)的個(gè)數(shù)必為偶數(shù).證:設(shè)G=<V,E>為任意圖，令

V1={v|vVd(v)為奇數(shù)}

V2={v|vVd(v)為偶數(shù)}則V1V2=V,V1V2=，

由握手定理可知

由于2m,均為偶數(shù)，所以也為偶數(shù),但因?yàn)閂1中頂點(diǎn)度數(shù)都為奇數(shù)，所以|V1|必為偶數(shù).圖的度數(shù)列

設(shè)無向圖G的頂點(diǎn)集V={v1,v2,…,vn}G的度數(shù)列:d(v1),d(v2),…,d(vn)上圖度數(shù)列:4,4,2,1,3圖的度數(shù)列

設(shè)有向圖D的頂點(diǎn)集V={v1,v2,…,vn}D的出度列:d+(v1),d+(v2),…,d+(vn)D的入度列:d(v1),d(v2),…,d(vn)

D的度數(shù)列:d(v1),d(v2),…,d(vn)如右圖出度列:4,0,2,1入度列:1,3,1,2度數(shù)列:5,3,3,3握手定理的應(yīng)用1例1：

(3,3,3,4),(2,3,4,6,8)能成為圖的度數(shù)列嗎?解：不可能.它們奇度頂點(diǎn)的個(gè)數(shù)都為奇數(shù).例2:已知圖G有10條邊,4個(gè)3度頂點(diǎn),其余頂點(diǎn)的度數(shù)均不大于2,問G至少有幾個(gè)頂點(diǎn)?

解：設(shè)G有n個(gè)頂點(diǎn).由握手定理,43+2(n-4)210

解得n8握手定理的應(yīng)用2例3：

證明：不存在具有奇數(shù)個(gè)面且每個(gè)面都具有奇數(shù)條棱的多面體。證用反證法.假設(shè)存在這樣的多面體,

作無向圖G=<V,E>,其中V={v|v為多面體的面},E={(u,v)|u,vVu與v有公共的棱uv}.

根據(jù)假設(shè),|V|為奇數(shù)，且vV,d(v)為奇數(shù).則總度數(shù)為奇數(shù)，這與握手定理的推論矛盾!多重圖與簡單圖

定義：在無向圖中,如果有2條或2條以上的邊關(guān)聯(lián)同一對(duì)頂點(diǎn),則稱這些邊為平行邊,平行邊的條數(shù)稱為重?cái)?shù).含平行邊的圖