圖的結(jié)構(gòu)

1、圖的結(jié)構(gòu)1圖的基本知識圖的基本知識一、什么是圖一、什么是圖什么是計(jì)算機(jī)中所說的圖請先看下面的“柯尼斯堡橋問題”。傳說在東普魯士境內(nèi)，有一座柯尼斯堡城，希雷格爾河流經(jīng)這個(gè)城市的克奈霍福島后，就將這個(gè)城市一分為二，形成如圖1—1（左）的A、B、C、D4個(gè)地區(qū)。人們建造了7座橋?qū)⑦@4個(gè)地區(qū)連起來。在游覽中有人提出，是否可以從A地出發(fā)，各座橋恰好通過一次，最后又回到原來出發(fā)地呢這個(gè)問題在18世紀(jì)被數(shù)學(xué)家歐拉解決了。他把這個(gè)問題轉(zhuǎn)化為圖1—1右邊

2、所示的圖。圖上用A、B、C、D4個(gè)頂點(diǎn)分別表示4個(gè)地區(qū)，用兩點(diǎn)間的線段表示連接各地的橋。這樣原來的問題就轉(zhuǎn)化為：從A頂點(diǎn)出發(fā)經(jīng)過其中每一條線段一次，而且僅一次，再回到A點(diǎn)的“一筆畫”問題。歐拉對柯尼斯堡問題作出了否定的結(jié)論。因?yàn)閷τ诿恳粋€(gè)頂點(diǎn)，不論如何經(jīng)過，必須有一條進(jìn)路和一條出路，所以對每一個(gè)頂點(diǎn)(除起點(diǎn)和終點(diǎn))來說與它有關(guān)的線段(稱為邊)必須是偶數(shù)條。而圖11(右)的頂點(diǎn)有關(guān)的線段都是奇數(shù)條，因此不可能一筆畫出。而如圖1—2中的圖形

3、是可以一筆畫出的。歐拉通過對柯尼斯堡橋問題的研究，于1736年發(fā)表了著名的關(guān)于圖論的論文，從而創(chuàng)立了圖論的學(xué)說。圖1—2一類的問題就是圖論中所指的圖。又如，有6個(gè)足球隊(duì)之間進(jìn)行循環(huán)賽，他們比賽的場次可以用圖13(1)來表示。有3個(gè)人相互寫信，可以用圖1—3(2)來表示。示用尖括號）簡單圖（無環(huán)）與完全圖（每一對不同的頂點(diǎn)都有一條邊相連）頂點(diǎn)的度：與頂點(diǎn)關(guān)聯(lián)的邊的數(shù)目，有向圖中等于該頂點(diǎn)的入度與出度之和。入度——以該頂點(diǎn)為終點(diǎn)的邊的數(shù)目和

4、出度——以該頂點(diǎn)為起點(diǎn)的邊的數(shù)目和圖的階：圖中頂點(diǎn)的個(gè)數(shù)。例如圖4—14中的圖的階是4，圖1—3中分別是6和3。度數(shù)為奇數(shù)的頂點(diǎn)叫做奇點(diǎn)，度數(shù)為偶數(shù)的點(diǎn)叫做偶點(diǎn)。例如圖14中，A和C是奇點(diǎn)，B和D是偶點(diǎn)。[定理1]圖G中所有頂點(diǎn)的度數(shù)之和等于邊數(shù)的2倍。因?yàn)橛?jì)算頂點(diǎn)的度數(shù)時(shí)。每條邊均用到2次。[定理2]任意一個(gè)圖一定有偶數(shù)個(gè)奇點(diǎn)。連通：如果頂點(diǎn)u，v屬于G，u，v之間有一條從u通過若干條邊到達(dá)v的通路，則認(rèn)為頂點(diǎn)u和v是連通的。連通圖：

5、如果對于圖G中每一對不同頂點(diǎn)u，v都有一條(u，v)通路，則稱G是連通圖。通路指u邊1頂點(diǎn)1邊2頂點(diǎn)2……v，點(diǎn)和邊交替相接，且互不相同。2圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)在計(jì)算機(jī)中，有多種方法存儲(chǔ)圖的信息，由于圖的結(jié)構(gòu)復(fù)雜，使用廣泛，一般應(yīng)根據(jù)實(shí)際的應(yīng)用，選擇適合的表示方法。常用的圖的存儲(chǔ)結(jié)構(gòu)有鄰接矩陣、鄰接多重表和鄰接表。1、鄰接矩陣、鄰接矩陣（數(shù)組）鄰接矩陣是表示頂點(diǎn)之間相鄰關(guān)系的矩陣，實(shí)質(zhì)上是一個(gè)二維數(shù)組。設(shè)G=(VE)是具有n(n=1

6、)個(gè)頂點(diǎn)的圖，則G的鄰接矩陣是具有如下性質(zhì)的n階方陣：若(ViVj)或是E(G)中的邊，則A[ij]=1，否則A[ij]=0，如：|0101||00000||1011||10000|A（G）=|0101|B（G）=|00010||1110||00000||01101|顯見用鄰接矩陣表示的無向圖是一個(gè)對稱的矩陣。圖的類型定義：Cconstn=Typeadj=0..1adjm=array[1..n1..n]OFadj鄰接矩陣graph=RE