離散數(shù)學圖的基本概念1第1頁，共28頁，2023年，2月20日，星期一第6章圖6.1圖的基本概念6.2圖的連通性6.3圖的矩陣表示6.4幾種特殊的圖2第2頁，共28頁，2023年，2月20日，星期一6.1

圖的基本概念6.1.1無向圖與有向圖6.1.2頂點的度數(shù)與握手定理6.1.3簡單圖、完全圖、正則圖、圈圖、輪圖、方體圖6.1.4子圖、補圖6.1.5圖的同構3第3頁，共28頁，2023年，2月20日，星期一無序?qū)εc多重集合無序?qū)?2個元素構成的集合,記作(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)}多重集合:元素可以重復出現(xiàn)的集合重復度:元素在多重集合中出現(xiàn)的次數(shù)例如S={a,b,b,c,c,c},a,b,c

的重復度依次為1,2,34第4頁，共28頁，2023年，2月20日，星期一無向圖定義6.1無向圖G=<V,E>,其中V稱為頂點集,其元素稱為頂點或結點;E是VV的多重子集,稱為邊集,其元素稱為無向邊，簡稱邊.有時用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頁，2023年，2月20日，星期一有向圖定義6.2有向圖D=<V,E>,其中V稱為頂點集,其元素稱為頂點或結點;E是VV的多重子集,稱為邊集,其元素稱為有向邊，簡稱邊.有時用V(D)和E(D)分別表示V和E

有限圖:V,E都是有窮集合的圖n階圖:n個頂點的圖零圖:E=的圖平凡圖:1階零圖e1e2e3e4e5e6e7dabc6第6頁，共28頁，2023年，2月20日，星期一頂點和邊的關聯(lián)與相鄰設無向圖G=<V,E>,

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

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

vj,則稱ek與vi(

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

ek,elE,

若(vi,vj)E,則稱vi,vj相鄰;若ek,el有一個公共端點,則稱ek,el相鄰.對有向圖有類似定義.設ek=vi,vj是有向圖的一條邊,又稱vi是ek的始點,vj是ek的終點,vi鄰接到vj,vj鄰接于vi7第7頁，共28頁，2023年，2月20日，星期一頂點的度數(shù)設G=<V,E>為無向圖,vV,v的度數(shù)(度)

d(v):v作為邊的端點次數(shù)之和懸掛頂點:度數(shù)為1的頂點懸掛邊:與懸掛頂點關聯(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是懸掛頂點,e7是懸掛邊,e1是環(huán)e1e2e3e4e5e6e7v5v1v2v3v48第8頁，共28頁，2023年，2月20日，星期一頂點的度數(shù)(續(xù))設D=<V,E>為有向圖,vV,v的出度d+(v):v作為邊的始點次數(shù)之和v的入度d(v):v作為邊的終點次數(shù)之和v的度數(shù)(度)d(v):v作為邊的端點次數(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,+=4,+=0,=3,=1,=5,=3e1e2e3e4e5e6e7dabc9第9頁，共28頁，2023年，2月20日，星期一握手定理定理6.1

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

有向圖所有頂點的入度之和等于出度之和等于邊數(shù)證每條邊恰好提供1個入度和1個出度10第10頁，共28頁，2023年，2月20日，星期一圖的度數(shù)列設無向圖G的頂點集V={v1,v2,…,vn}G的度數(shù)列:d(v1),d(v2),…,d(vn)如右圖度數(shù)列:4,4,2,1,3設有向圖D的頂點集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頁，2023年，2月20日，星期一實例(2)能例1

下述2組數(shù)能成為無向圖的度數(shù)列嗎?(1)3,3,3,4;(2)1,2,2,3解(1)不可能.有奇數(shù)個奇數(shù).12第12頁，共28頁，2023年，2月20日，星期一實例例2已知圖G有10條邊,4個3度頂點,其余頂點的度數(shù)均小于等于2,問G至少有多少個頂點?解設G有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頁，2023年，2月20日，星期一實例例4

證明不存在具有奇數(shù)個面且每個面都具有奇數(shù)條棱的多面體.證用反證法.假設存在這樣的多面體,作無向圖G=<V,E>,其中V={v|v為多面體的面},

E={(u,v)|u,vVu與v有公共的棱uv}.根據(jù)假設,|V|為奇數(shù)且vV,d(v)為奇數(shù).這與握手定理的推論矛盾.14第14頁，共28頁，2023年，2月20日，星期一實例例5

設9階無向圖的每個頂點的度數(shù)為5或6,證明它至少有5個6度頂點或者至少有6個5度頂點.證討論所有可能的情況.設有a個5度頂點和b個6度頂點(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個6度頂點,(4)和(5)至少6個5度頂點方法二假設b<5,則a>9-5=4.由握手定理的推論,a

615第15頁，共28頁，2023年，2月20日，星期一簡單圖定義6.4

在無向圖中,關聯(lián)同一對頂點的2條或2條以上的邊,稱為平行邊,平行邊的條數(shù)稱為重數(shù)在有向圖中,具有相同始點和終點的2條或2條以上的邊稱為有向平行邊,簡稱平行邊,平行邊的條數(shù)稱為重數(shù)含平行邊的圖稱為多重圖既無平行邊也無環(huán)的圖稱為簡單圖16第16頁，共28頁，2023年，2月20日，星期一實例e5和e6是平行邊重數(shù)為2不是簡單圖e2和e3是平行邊,重數(shù)為2e6和e7不是平行邊不是簡單圖e1e2e3e4e5e6e7v5v1v2v3v4e1e2e3e4e5e6e7dabc17第17頁，共28頁，2023年，2月20日，星期一完全圖與正則圖無向完全圖:每對頂點之間都有一條邊的無向簡單圖.n階無向完全圖記作Kn,頂點數(shù)n,邊數(shù)m=n(n-1)/2,==n-1有向完全圖:每對頂點之間均有兩條方向相反的邊的有向簡單圖.頂點數(shù)n,邊數(shù)m=n(n-1),+=+=-=-=n-1,==2(n-1)k-正則圖:每個頂點的度數(shù)均為k的無向簡單圖頂點數(shù)n,邊數(shù)m=kn/218第18頁，共28頁，2023年，2月20日，星期一實例K3K53階有向完全圖2正則圖4正則圖3正則圖彼得松圖19第19頁，共28頁，2023年，2月20日，星期一圈圖與輪圖無向圈圖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)放一個頂點,且與圈圖的每個頂點之間恰有一條邊,n

420第20頁，共28頁，2023年，2月20日，星期一方體圖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頁，2023年，2月20日，星期一子圖定義6.10

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

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

以V為頂點集,以兩端點都在V中的所有邊為邊集的G的子圖稱作V的導出子圖,記作G[V]設EE且E,

以E為邊集,以E中邊關聯(lián)的所有頂點為頂點集的G的子圖稱作E的導出子圖,記作G[E]22第22頁，共28頁，2023年，2月20日，星期一實例(1),(2),(3)是(1)的子圖,(2),(3)是真子圖,(1)是母圖.(1),(3)是(1)的生成子圖.(2)是{d,e,f}的導出子圖,也是{e5,e6,e7}導出子圖.(3)是{e1,e3,e5,e7}的導出子圖aabbccdddeeefffe1e1e2e3e3e4e5e5e5e6e6e7e7e7(1)(2)(3)23第23頁，共28頁，2023年，2月20日，星期一補圖定義6.11設G=<V,E>為n階無向簡單圖,記=VV

-E,稱為G的補圖24第24頁，共28頁，2023年，2月20日，