資源描述：
《《圖的定義和術語》PPT課件.ppt》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。
1、第7章圖線性結構：是研究數(shù)據(jù)元素之間的一對一關系。在這種結構中，除第一個和最后一個元素外，任何一個元素都有唯一的一個直接前驅和直接后繼。樹結構：是研究數(shù)據(jù)元素之間的一對多的關系。在這種結構中，每個元素對下(層)可以有0個或多個元素相聯(lián)系，對上(層)只有唯一的一個元素相關，數(shù)據(jù)元素之間有明顯的層次關系。圖(Graph)是一種比線性表和樹更為復雜的數(shù)據(jù)結構。圖結構：是研究數(shù)據(jù)元素之間的多對多的關系。在這種結構中，任意兩個元素之間可能存在關系。即結點之間的關系可以是任意的，圖中任意元素之間都可能相關。7.
2、1圖的定義和術語V1V3V2V4V1V2V5V4V3圖7.1圖的示例(a)有向圖G1(b)無向圖G2(a)(b)7.1.1圖的定義和術語頂點（Vertex)：在圖中的數(shù)據(jù)元素通常稱為頂點（Vertex)。約定V表示頂點的有窮非空集合，VR表示兩個頂點之間的關系的集合?；。ˋrc）：表示兩個頂點v和w之間存在一個關系，用表示頂點v到w的一條弧。且稱v為弧尾（Tail）或初始點，稱w為弧頭（Head）或終端點。此時的圖稱為有向圖（Digraph）。其中，頂點偶對的v和w之間是有序的。
3、無向圖(Undigraph)：若圖關系集合中，頂點偶對的v和w之間是無序的，稱圖G是無向圖。若屬于VR，必有屬于VR，即VR是對稱的。那么用（v,w）代替這兩個有序對，表示v和w的一條邊（Edge）。如圖7.1：設有向圖G1和無向圖G2，形式化定義分別是：G1=(V1，A1)V1={v1,v2,v3,v4}A1={,,,}G2=(V2，E2)V2={v1,v2,v3,v4,v5}E2={(v1,v2),(v1,v4
4、),(v2,v3),(v2,v5),(v3,v1),(v3,v5)}V1V3V2V4V1V2V5V4V3圖7.1圖的示例(a)有向圖G1(b)無向圖G2(a)(b)完全無向圖：對于無向圖，若圖中頂點數(shù)為n，用e表示邊的數(shù)目，則e?[0，n(n-1)/2]。具有n(n-1)/2條邊的無向圖稱為完全無向圖。完全無向圖另外的定義是：對于無向圖G=(V，E)，若?vi，vj?V，當vi≠vj時，有(vi,vj)?E，即圖中任意兩個不同的頂點間都有一條無向邊，這樣的無向圖稱為完全無向圖。完全有向圖：對于有向圖
5、，若圖中頂點數(shù)為n，用e表示弧的數(shù)目，則e?[0，n(n-1)]。具有n(n-1)條邊的有向圖稱為完全有向圖。完全有向圖另外的定義是：對于有向圖G=(V，E)，若?vi，vj?V，當vi≠vj時，有?E并且?E，即圖中任意兩個不同的頂點間都有一條弧，這樣的有向圖稱為完全有向圖。有很少邊或弧的圖（e6、V，E)和G’=(V’，E’)，若V’?V且E’?E，則稱圖G’是G的子圖；若V’=V且E’?E，則稱圖G’是G的一個生成子圖。P7.2對于無向圖G=(V，E)，若邊(v,w)?E，則稱頂點v和w互為鄰接點，即v和w相鄰接。邊(v,w)依附(incident)于頂點v和w，或者說(v,w)和頂點v和w相關聯(lián)。圖G中和v相關聯(lián)的邊的數(shù)目稱為頂點v的度(degree)，記為TD(v)。例如無向圖G2。TD(V1)，TD(V2)，TD(V3)，TD(V4)，TD(V5)V1V2V5V4V3G2對于有向圖G
7、=(V，E)，若有向弧?E，則稱頂點v“鄰接到”頂點w，頂點w“鄰接自”頂點v，弧與頂點v和w“相關聯(lián)”。對有向圖G=(V，E)，若?vi?V，圖G中以頂點v作為尾或初始的有向邊(弧)的數(shù)目稱為頂點v的出度(Outdegree)，記為OD(v)；以v作為頭或終點的有向邊(弧)的數(shù)目稱為頂點v的入度(Indegree)，記為ID(v)。頂點v的出度與入度之和稱為v的度，記為TD(v)。即TD(v)=OD(v)+ID(v)例如圖7.1所示的無向圖。OD(v1)，ID(,1)，TD(v
8、1)；OD(v3)，ID(,3)，TD(v1)V1V3V2V4(G1)一般地，如果頂點vi在的度記為TD(vi)，那么一個有n個頂點，e條邊或弧的圖，滿足：∑TD(vi)=2e路徑(Path)：對無向圖G=(V，E)，若從頂點vi經過若干條邊能到達vj，稱頂點vi和vj是連通的，又稱頂點vi到vj有路徑。對有向圖G=(V，E)，從頂點vi到vj有有向路徑，指的是從頂點vi經過若干條有向邊(弧)能到達vj。路徑的長度：路徑上邊或有向邊(弧)的數(shù)目稱為該路徑的長度。在一條
