圖的結構

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

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

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

4、出度——以該頂點為起點的邊的數目和圖的階：圖中頂點的個數。例如圖4—14中的圖的階是4，圖1—3中分別是6和3。度數為奇數的頂點叫做奇點，度數為偶數的點叫做偶點。例如圖14中，A和C是奇點，B和D是偶點。[定理1]圖G中所有頂點的度數之和等于邊數的2倍。因為計算頂點的度數時。每條邊均用到2次。[定理2]任意一個圖一定有偶數個奇點。連通：如果頂點u，v屬于G，u，v之間有一條從u通過若干條邊到達v的通路，則認為頂點u和v是連通的。連通圖：

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

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