七章圖的基本概念ppt課件

1、第七章 圖的根本概念7.1 無向圖及有向圖7.2 通路、回路、圖的連通性7.3 圖的矩陣表示作 業(yè)7.1 無向圖及有向圖設A,B為兩集合,稱 a,baAbB為A與B的無序積,記作AB將無序對a,b記作(a,b).無向圖一個無向圖G是一個二元組,即G,其中, (1)V是一個非空的集合,稱為G的頂點集,V中元素稱為頂點或結點； (2)E是無序積VV的一個多重子集,稱E為G的邊集,E中元素稱為無向邊或簡稱邊.有向圖一個有向圖D是一個二元組,即D,其中, (1)V同無向圖中的頂點集； (2)E是卡氏積的多重子圖,其元素稱為有向邊,也簡稱邊.給每條邊賦與權的圖G=稱為加權圖，記為G=,其中W表示各邊權的

2、集合。23.57.8設ek(vi,vj)為無向圖G中的一條邊,稱vi,vj為ek的端點, ek與vi(或vj)是彼此關聯的.無邊關聯的頂點稱為孤立點.假設一條邊所關聯的兩個頂點重合,那么稱此邊為環(huán).ek與vi(或vj)的關聯次數1vivj,2vi vj,0vi(vj)不是ek的端點bavV設G為一無向圖或有向圖 (1)假設V,E都是有窮集合,那么稱G是有限圖. (2)假設Vn,那么稱G為n階圖 (3)假設E,那么稱G為零圖特別是,假設此時又有V1,那么稱G為平凡圖.相鄰設無向圖GV,E,vi, vjV, ek,elE.(1)假設存在一條邊e以vi, vj為端點,即e(vi, vj),那么稱vi

3、, vj是彼此相鄰的,簡稱相鄰的(2)假設ek, el至少有一個公共端點,那么稱ek, el是彼此相鄰的,簡稱相鄰的始點 終點以上兩定義對有向圖也是類似的假設ek vi, vj,除稱vi, vj是ek的端點外,還稱vi是ek的始點, vj是ek的終點,vi鄰接到vj,vj鄰接于vi.度設G為一無向圖,vjV,稱vj作為邊的端點的次數之和為vi的度數,簡稱度,記作d(vj).稱度數為1的頂點為懸掛頂點,它所對應的邊為懸掛邊.設D為一有向圖,vjV,稱vj作為邊的始點的次數之和,為vj的出度,記作d+(vj)；稱vj作為邊的終點的次數之和,為vj的入度,記作d-(vj)；稱vj作為邊的端點的次數之

4、和,為vj的度數,簡稱度,記作d(vj).顯然d(vj)d + (vj)d- (vj).deg(v1)3，deg+(v1)2，deg-(v1)1；deg(v2)3，deg+(v2)2，deg-(v2)1；deg(v3)5，deg+(v3)2，deg-(v3)3；deg(v4)deg+(v4)deg-(v4)0；deg(v5)1，deg+(v5)0，deg-(v5)1；其中，v5是懸掛結點，為懸掛邊。最大度和最小度對于圖G,記(G)maxd(v)vV, (G)mind(v)vV,分別稱為G的最大度和最小度.假設DV,E是有向圖,除了(D),(D)外,還有最大出度、最大入度、最小出度、最小入度,分

5、別定義為根本定理(握手定理)設圖G為無向圖或有向圖,Vv1,v2,.,vn,|E|=m(m為邊數),那么推論任何圖(無向的或有向的)中,度為奇數的頂點個數為偶數.定理設有向圖D,Vv1,v2,.,vn,Em,那么度數序列設Vv1,v2,.,vn為圖G的頂點集,稱(d(v1),d(v2),.,d(vn)為G的度數序列. 例7.1 (1) (3,3,2,3),(5,2,3,1,4)能成為圖的度數序列嗎？為什么？ (2) 知圖G中有10條邊,4個3度頂點,其他頂點的度數均小于等于2.問G中至少有多少個頂點？為什么？平行邊、重數、多重圖、簡單圖在無向圖中,關聯一對頂點的無向邊假設多于1條,稱這些邊為平

6、行邊.平行邊的條數稱為重數. 在有向圖中,關聯一對頂點的有向邊假設多于1條,且它們的始點與終點一樣,那么稱這些邊為有向平行邊,簡稱平行邊.含平行邊的圖稱為多重圖.既不含平行邊,也不含環(huán)的圖稱為簡單圖.例無向完全圖、有向完全圖設G=是n階無向簡單圖,假設G中任何頂點都與其他的n1個頂點相鄰,那么稱G為n階無向完全圖,記作Kn. 設D=為n階有向簡單圖,假設對于恣意的頂點u,vV(uv),既有有向邊,又有,那么稱D是n階有向完全圖.Kn均指無向完全圖.圖7.2在圖7.2(1)中所示為K4,(2)所示為K5,(3)所示為3階有向完全圖.子圖、真子圖設G=, G =是兩個圖.假設VV,且EE,那么稱G

7、 是G的子圖, G 是G的母圖,記做G G.假設G G且GG(即VV或E E),那么G是G的真子圖.生成子圖、導出子圖假設G G且V=V那么稱V是V的生成子圖.設V1V ,且V1,以V1為頂點集,以兩端點均在V1中的全體邊為邊集的G的子圖,稱為V1導出的導出子圖. 設E1 E,且E1 ,以E1為邊集,以E1中關聯的頂點的全體為頂點集的G的子圖稱為E1導出的導出子圖. 在如以下圖中，給出了圖G以及它的真子圖G和生成子圖G。G是結點集v1，v2，v4，v5，v6的導出子圖。補圖設G=是n階無向簡單圖.以V為頂點集,以一切能使G成為完全圖Kn的添加邊組成的集合為邊集的圖,稱為G相對于完全圖Kn的補圖,簡稱G的補圖,記作 . 有向簡單圖的補圖可類似定義.圖7.4圖的同構例如以下圖(a)、(b)、(c)、(d)所示，圖(a)、圖(b)、圖(c)和圖(d)所表示的圖形實踐上都是一樣的。同構設兩個無向圖 G1=,G2=,假設存在雙射函數：V1V2,使得對于恣意的e=(vi,vj)E1當且僅當e=( (vi), (vj)E2,并且e與e的重數一樣,那么稱G1與G2是同構的,記作G1 G2.有向圖的同構(1)(2),頂點之間的對應關系為av1,b v2,c v3,d v4,