離散數(shù)學(xué)圖的基本概念1第1頁，課件共28頁，創(chuàng)作于2023年2月第6章圖6.1圖的基本概念6.2圖的連通性6.3圖的矩陣表示6.4幾種特殊的圖2第2頁，課件共28頁，創(chuàng)作于2023年2月6.1

圖的基本概念6.1.1無向圖與有向圖6.1.2頂點(diǎn)的度數(shù)與握手定理6.1.3簡單圖、完全圖、正則圖、圈圖、輪圖、方體圖6.1.4子圖、補(bǔ)圖6.1.5圖的同構(gòu)3第3頁，課件共28頁，創(chuàng)作于2023年2月無序?qū)εc多重集合無序?qū)?2個(gè)元素構(gòu)成的集合,記作(a,b)無序積:AB={(x,y)|xAyB}例如A={a,b,c},B={1,2}AB=BA={(a,1),(b,1),(c,1),(a,2),(b,2),(c,2)}AA={(a,a),(a,b),(a,c),(b,b),(b,c),(c,c)}BB={(1,1),(1,2),(2,2)}多重集合:元素可以重復(fù)出現(xiàn)的集合重復(fù)度:元素在多重集合中出現(xiàn)的次數(shù)例如S={a,b,b,c,c,c},a,b,c

的重復(fù)度依次為1,2,34第4頁，課件共28頁，創(chuàng)作于2023年2月無向圖定義6.1無向圖G=<V,E>,其中V稱為頂點(diǎn)集,其元素稱為頂點(diǎn)或結(jié)點(diǎn);E是VV的多重子集,稱為邊集,其元素稱為無向邊，簡稱邊.有時(shí)用V(G)和E(G)分別表示V和E例如,G=<V,E>如圖所示,其中V={v1,v2,…,v5}E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)}e1e2e3e4e5e6e7v5v1v2v3v45第5頁，課件共28頁，創(chuàng)作于2023年2月有向圖定義6.2有向圖D=<V,E>,其中V稱為頂點(diǎn)集,其元素稱為頂點(diǎn)或結(jié)點(diǎn);E是VV的多重子集,稱為邊集,其元素稱為有向邊，簡稱邊.有時(shí)用V(D)和E(D)分別表示V和E

有限圖:V,E都是有窮集合的圖n階圖:n個(gè)頂點(diǎn)的圖零圖:E=的圖平凡圖:1階零圖e1e2e3e4e5e6e7dabc6第6頁，課件共28頁，創(chuàng)作于2023年2月頂點(diǎn)和邊的關(guān)聯(lián)與相鄰設(shè)無向圖G=<V,E>,

ek=(vi,vj)E,稱vi,vj為ek的端點(diǎn),ek與vi(

vj)關(guān)聯(lián).若vi=vj,則稱ek為環(huán).無邊關(guān)聯(lián)的頂點(diǎn)稱作孤立點(diǎn).若vi

vj,則稱ek與vi(

vj)的關(guān)聯(lián)次數(shù)為1;若vi=vj,則稱ek與vi的關(guān)聯(lián)次數(shù)為2;若vi不是邊e的端點(diǎn),則稱e與vi的關(guān)聯(lián)次數(shù)為0.設(shè)vi,vjV,

ek,elE,

若(vi,vj)E,則稱vi,vj相鄰;若ek,el有一個(gè)公共端點(diǎn),則稱ek,el相鄰.對(duì)有向圖有類似定義.設(shè)ek=vi,vj是有向圖的一條邊,又稱vi是ek的始點(diǎn),vj是ek的終點(diǎn),vi鄰接到vj,vj鄰接于vi7第7頁，課件共28頁，創(chuàng)作于2023年2月頂點(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(v5)=3,d(v2)=4,d(v1)=4,(G)=4,(G)=1,

v4是懸掛頂點(diǎn),e7是懸掛邊,e1是環(huán)e1e2e3e4e5e6e7v5v1v2v3v48第8頁，課件共28頁，創(chuàng)作于2023年2月頂點(diǎn)的度數(shù)(續(xù))設(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)懸掛頂點(diǎn),懸掛邊例如d+(a)=4,d-(a)=1,d(a)=5,d+(b)=0,d-(b)=3,d(b)=3,+=4,+=0,=3,=1,=5,=3e1e2e3e4e5e6e7dabc9第9頁，課件共28頁，創(chuàng)作于2023年2月握手定理定理6.1

任何圖(無向圖和有向圖)的所有頂點(diǎn)度數(shù)之和都等于邊數(shù)的2倍.證圖中每條邊(包括環(huán))均有兩個(gè)端點(diǎn),所以在計(jì)算各頂點(diǎn)度數(shù)之和時(shí),每條邊均提供2度,m條邊共提供2m度.推論任何圖(無向圖和有向圖)都有偶數(shù)個(gè)奇度頂點(diǎn)定理6.2

有向圖所有頂點(diǎn)的入度之和等于出度之和等于邊數(shù)證每條邊恰好提供1個(gè)入度和1個(gè)出度10第10頁，課件共28頁，創(chuàng)作于2023年2月圖的度數(shù)列設(shè)無向圖G的頂點(diǎn)集V={v1,v2,…,vn}G的度數(shù)列:d(v1),d(v2),…,d(vn)如右圖度數(shù)列:4,4,2,1,3設(shè)有向圖D的頂點(diǎn)集V={v1,v2,…,vn}D的度數(shù)列:d(v1),d(v2),…,d(vn)D的出度列:d+(v1),d+(v2),…,d+(vn)D的入度列:d(v1),d(v2),…,d(vn)如右圖度數(shù)列:5,3,3,3

出度列:4,0,2,1

入度列:1,3,1,2e1e2e3e4e5e6e7v5v1v2v3v4e1e2e3e4e5e6e7dabc11第11頁，課件共28頁，創(chuàng)作于2023年2月實(shí)例(2)能例1

下述2組數(shù)能成為無向圖的度數(shù)列嗎?(1)3,3,3,4;(2)1,2,2,3解(1)不可能.有奇數(shù)個(gè)奇數(shù).12第12頁，課件共28頁，創(chuàng)作于2023年2月實(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例3已知5階有向圖的度數(shù)列和出度列分別為3,3,2,3,3和1,2,1,2,1,求它的入度列解2,1,1,1,213第13頁，課件共28頁，創(chuàng)作于2023年2月實(shí)例例4

證明不存在具有奇數(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ù).這與握手定理的推論矛盾.14第14頁，課件共28頁，創(chuàng)作于2023年2月實(shí)例例5

設(shè)9階無向圖的每個(gè)頂點(diǎn)的度數(shù)為5或6,證明它至少有5個(gè)6度頂點(diǎn)或者至少有6個(gè)5度頂點(diǎn).證討論所有可能的情況.設(shè)有a個(gè)5度頂點(diǎn)和b個(gè)6度頂點(diǎn)(1)a=0,b=9;(2)a=2,b=7;(3)a=4,b=5;(4)a=6,b=3;(5)a=8,b=1(1)~(3)至少5個(gè)6度頂點(diǎn),(4)和(5)至少6個(gè)5度頂點(diǎn)方法二假設(shè)b<5,則a>9-5=4.由握手定理的推論,a

615第15頁，課件共28頁，創(chuàng)作于2023年2月簡單圖定義6.4

在無向圖中,關(guān)聯(lián)同一對(duì)頂點(diǎn)的2條或2條以上的邊,稱為平行邊,平行邊的條數(shù)稱為重?cái)?shù)在有向圖中,具有相同始點(diǎn)和終點(diǎn)的2條或2條以上的邊稱為有向平行邊,簡稱平行邊,平行邊的條數(shù)稱為重?cái)?shù)含平行邊的圖稱為多重圖既無平行邊也無環(huán)的圖稱為簡單圖16第16頁，課件共28頁，創(chuàng)作于2023年2月實(shí)例e5和e6是平行邊重?cái)?shù)為2不是簡單圖e2和e3是平行邊,重?cái)?shù)為2e6和e7不是平行邊不是簡單圖e1e2e3e4e5e6e7v5v1v2v3v4e1e2e3e4e5e6e7dabc17第17頁，課件共28頁，創(chuàng)作于2023年2月完全圖與正則圖無向完全圖:每對(duì)頂點(diǎn)之間都有一條邊的無向簡單圖.n階無向完全圖記作Kn,頂點(diǎn)數(shù)n,邊數(shù)m=n(n-1)/2,==n-1有向完全圖:每對(duì)頂點(diǎn)之間均有兩條方向相反的邊的有向簡單圖.頂點(diǎn)數(shù)n,邊數(shù)m=n(n-1),+=+=-=-=n-1,==2(n-1)k-正則圖:每個(gè)頂點(diǎn)的度數(shù)均為k的無向簡單圖頂點(diǎn)數(shù)n,邊數(shù)m=kn/218第18頁，課件共28頁，創(chuàng)作于2023年2月實(shí)例K3K53階有向完全圖2正則圖4正則圖3正則圖彼得松圖19第19頁，課件共28頁，創(chuàng)作于2023年2月圈圖與輪圖無向圈圖Cn=<V,E>,其中V={v1,v2,…,vn},E={(v1,v2),(v2,v3),…,(vn-1,vn),(vn,v1)},n

3有向圈圖Cn=<V,E>,其中V={v1,v2,…,vn},E={<v1,v2>,<v2,v3>,…,<vn-1,vn>,<vn,v1>},n

3輪圖Wn:無向圈圖Cn-1內(nèi)放一個(gè)頂點(diǎn),且與圈圖的每個(gè)頂點(diǎn)之間恰有一條邊,n

420第20頁，課件共28頁，創(chuàng)作于2023年2月方體圖n方體圖Qn=<V,E>是2n階無向簡單圖,其中

V={v|v=a1a2…an,ai=0,1,i=1,2,…,n}E={(u,v)|u,vVu與v恰好有一位數(shù)字不同}.010001101100000101001111010011110121第21頁，課件共28頁，創(chuàng)作于2023年2月子圖定義6.10

設(shè)G=<V,E>,G=<V,E>是2個(gè)圖(同為無向圖,或同為有向圖)若VV且EE,

則稱G為G的子圖,G為G的母圖,記作GG若GG且V=V,則稱G為G的生成子圖若VV或EE,稱G為G的真子圖設(shè)VV且V,

以V為頂點(diǎn)集,以兩端點(diǎn)都在V中的所有邊為邊集的G的子圖稱作V的導(dǎo)出子圖,記作G[V]設(shè)EE且E,

以E為邊集,以E中邊關(guān)聯(lián)的所有頂點(diǎn)為頂點(diǎn)集的G的子圖稱作E的導(dǎo)出子圖,記作G[E]22第22頁，課件共28頁，創(chuàng)作于2023年2月實(shí)例(1),(2),(3)是(1)的子圖,(2),(3)是真子圖,(1)是母圖.(1),(3)是(1)的生成子圖.(2)是{d,e,f}的導(dǎo)出子圖,也是{e5,e6,e7}導(dǎo)出子圖.(3)是{e1,e3,e5,e7}的導(dǎo)出子圖aabbccdddeeefffe1e1e2e3e3e4e5e5e5e6e6e7e7e7(1)(2)(3)23第23頁，課件共28頁，創(chuàng)作于2023年2月補(bǔ)圖定義6.11設(shè)G=<V,E>為n階無向簡單圖,記=VV

-E,稱為G的補(bǔ)圖24第24頁，課件共28頁，創(chuàng)作于