7.1有向圖及無向圖

《7.1有向圖及無向圖》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、第七章圖的基本概念第八章一些特殊的圖7.1無向圖及有向圖7.2通路、回路、圖的連通性7.3圖的矩陣表示7.4最短路徑及關(guān)鍵路徑最短路徑關(guān)鍵路徑8.1二部圖8.2歐拉圖8.3哈密爾頓圖8.4平面圖作業(yè)7.1無向圖及有向圖設(shè)A,B為兩集合,稱{{a,b}｜a∈A∧b∈B}為A與B的無序積,記作A＆B．將無序?qū)a,b}記作(a,b).無向圖一個無向圖G是一個二元組,即G＝,其中,(1)V是一個非空的集合,稱為G的頂點集,V中元素稱為頂點或結(jié)點；(2)E是無序積V＆V的一個多重子集,稱E為G的邊集,E中元素稱為無向邊或簡稱邊.有向圖一個有

2、向圖D是一個二元組,即D＝,其中,(1)V同無向圖中的頂點集；(2)E是卡氏積的多重子圖,其元素稱為有向邊,也簡稱邊.給每條邊賦與權(quán)的圖G=稱為加權(quán)圖，記為G=,其中W表示各邊權(quán)的集合。23.57.8設(shè)ek＝(vi,vj)為無向圖G＝中的一條邊,稱vi,vj為ek的端點,ek與vi(或vj)是彼此關(guān)聯(lián)的.無邊關(guān)聯(lián)的頂點稱為孤立點.若一條邊所關(guān)聯(lián)的兩個頂點重合,則稱此邊為環(huán).ek與vi(或vj)的關(guān)聯(lián)次數(shù)1vi≠vj,2vi＝vj,0vi(vj)不是ek的端點bavV’設(shè)G＝為一無向圖或有向圖

3、(1)若V,E都是有窮集合,則稱G是有限圖.(2)若｜V｜＝n,則稱G為n階圖．(3)若E＝?,則稱G為零圖．特別是,若此時又有｜V｜＝1,則稱G為平凡圖.相鄰設(shè)無向圖G＝〈V,E〉,vi,vj∈V,ek,el∈E.(1)若存在一條邊e以vi,vj為端點,即e＝(vi,vj),則稱vi,vj是彼此相鄰的,簡稱相鄰的．(2)若ek,el至少有一個公共端點,則稱ek,el是彼此相鄰的,簡稱相鄰的．始點終點以上兩定義對有向圖也是類似的若ek＝〈vi,vj〉,除稱vi,vj是ek的端點外,還稱vi是ek的始點,vj是ek的終點,vi鄰接到vj,vj鄰接于vi.度

4、設(shè)G＝為一無向圖,vj∈V,稱vj作為邊的端點的次數(shù)之和為vi的度數(shù),簡稱度,記作d(vj).稱度數(shù)為1的頂點為懸掛頂點,它所對應(yīng)的邊為懸掛邊.設(shè)D＝為一有向圖,vj∈V,稱vj作為邊的始點的次數(shù)之和,為vj的出度,記作d+(vj)；稱vj作為邊的終點的次數(shù)之和,為vj的入度,記作d-(vj)；稱vj作為邊的端點的次數(shù)之和,為vj的度數(shù),簡稱度,記作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；de

5、g(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是懸掛結(jié)點，為懸掛邊。最大度和最小度對于圖G＝,記Δ(G)＝max{d(v)｜v∈V},?(G)＝min{d(v)｜v∈V},分別稱為G的最大度和最小度.若D＝〈V,E〉是有向圖,除了Δ(D),?(D)外,還有最大出度、最大入度、最小出度、最小入度,分別定義為基本定理(握手定理)設(shè)圖G＝為無向圖或有向圖,V＝{v1,v2,...,vn

6、},

7、E

8、=m(m為邊數(shù)),則推論任何圖(無向的或有向的)中,度為奇數(shù)的頂點個數(shù)為偶數(shù).定理設(shè)有向圖D＝,V＝{v1,v2,...,vn},｜E｜＝m,則度數(shù)序列設(shè)V＝{v1,v2,...,vn}為圖G的頂點集,稱(d(v1),d(v2),...,d(vn))為G的度數(shù)序列.例7.1(1)(3,3,2,3),(5,2,3,1,4)能成為圖的度數(shù)序列嗎？為什么？(2)已知圖G中有10條邊,4個3度頂點,其余頂點的度數(shù)均小于等于2.問G中至少有多少個頂點？為什么？平行邊、重數(shù)、多重圖、簡單圖在無向圖中,關(guān)聯(lián)一對頂點的無向邊如果多于1條,稱這些邊為平

9、行邊.平行邊的條數(shù)稱為重數(shù).在有向圖中,關(guān)聯(lián)一對頂點的有向邊如果多于1條,且它們的始點與終點相同,則稱這些邊為有向平行邊,簡稱平行邊.含平行邊的圖稱為多重圖.既不含平行邊,也不含環(huán)的圖稱為簡單圖.例無向完全圖、有向完全圖設(shè)G=是n階無向簡單圖,若G中任何頂點都與其余的n－1個頂點相鄰,則稱G為n階無向完全圖,記作Kn.設(shè)D=為n階有向簡單圖,若對于任意的頂點u,v∈V(u≠v),既有有向邊,又有,則稱D是n階有向完全圖.Kn均指無向完全圖.圖7.2在圖7.2(1)中所示為K4,(2)所示為K5,(3)所示為3階有向

10、完全圖.子圖、真子圖設(shè)G=,G‘=是兩個圖.若V’?V,