《圖的定義和術(shù)語》PPT課件.ppt

《《圖的定義和術(shù)語》PPT課件.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第7章圖線性結(jié)構(gòu)：是研究數(shù)據(jù)元素之間的一對一關(guān)系。在這種結(jié)構(gòu)中，除第一個(gè)和最后一個(gè)元素外，任何一個(gè)元素都有唯一的一個(gè)直接前驅(qū)和直接后繼。樹結(jié)構(gòu)：是研究數(shù)據(jù)元素之間的一對多的關(guān)系。在這種結(jié)構(gòu)中，每個(gè)元素對下(層)可以有0個(gè)或多個(gè)元素相聯(lián)系，對上(層)只有唯一的一個(gè)元素相關(guān)，數(shù)據(jù)元素之間有明顯的層次關(guān)系。圖(Graph)是一種比線性表和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。圖結(jié)構(gòu)：是研究數(shù)據(jù)元素之間的多對多的關(guān)系。在這種結(jié)構(gòu)中，任意兩個(gè)元素之間可能存在關(guān)系。即結(jié)點(diǎn)之間的關(guān)系可以是任意的，圖中任意元素之間都可能相關(guān)。7.

2、1圖的定義和術(shù)語V1V3V2V4V1V2V5V4V3圖7.1圖的示例(a)有向圖G1(b)無向圖G2(a)(b)7.1.1圖的定義和術(shù)語頂點(diǎn)（Vertex)：在圖中的數(shù)據(jù)元素通常稱為頂點(diǎn)（Vertex)。約定V表示頂點(diǎn)的有窮非空集合，VR表示兩個(gè)頂點(diǎn)之間的關(guān)系的集合?；。ˋrc）：表示兩個(gè)頂點(diǎn)v和w之間存在一個(gè)關(guān)系，用表示頂點(diǎn)v到w的一條弧。且稱v為弧尾（Tail）或初始點(diǎn)，稱w為弧頭（Head）或終端點(diǎn)。此時(shí)的圖稱為有向圖（Digraph）。其中，頂點(diǎn)偶對的v和w之間是有序的。

3、無向圖(Undigraph)：若圖關(guān)系集合中，頂點(diǎn)偶對的v和w之間是無序的，稱圖G是無向圖。若屬于VR，必有屬于VR，即VR是對稱的。那么用（v,w）代替這兩個(gè)有序?qū)Γ硎緑和w的一條邊（Edge）。如圖7.1：設(shè)有向圖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)完全無向圖：對于無向圖，若圖中頂點(diǎn)數(shù)為n，用e表示邊的數(shù)目，則e?[0，n(n-1)/2]。具有n(n-1)/2條邊的無向圖稱為完全無向圖。完全無向圖另外的定義是：對于無向圖G=(V，E)，若?vi，vj?V，當(dāng)vi≠vj時(shí)，有(vi,vj)?E，即圖中任意兩個(gè)不同的頂點(diǎn)間都有一條無向邊，這樣的無向圖稱為完全無向圖。完全有向圖：對于有向圖

5、，若圖中頂點(diǎn)數(shù)為n，用e表示弧的數(shù)目，則e?[0，n(n-1)]。具有n(n-1)條邊的有向圖稱為完全有向圖。完全有向圖另外的定義是：對于有向圖G=(V，E)，若?vi，vj?V，當(dāng)vi≠vj時(shí)，有?E并且?E，即圖中任意兩個(gè)不同的頂點(diǎn)間都有一條弧，這樣的有向圖稱為完全有向圖。有很少邊或弧的圖（e

6、V，E)和G’=(V’，E’)，若V’?V且E’?E，則稱圖G’是G的子圖；若V’=V且E’?E，則稱圖G’是G的一個(gè)生成子圖。P7.2對于無向圖G=(V，E)，若邊(v,w)?E，則稱頂點(diǎn)v和w互為鄰接點(diǎn)，即v和w相鄰接。邊(v,w)依附(incident)于頂點(diǎn)v和w，或者說(v,w)和頂點(diǎn)v和w相關(guān)聯(lián)。圖G中和v相關(guān)聯(lián)的邊的數(shù)目稱為頂點(diǎn)v的度(degree)，記為TD(v)。例如無向圖G2。TD(V1)，TD(V2)，TD(V3)，TD(V4)，TD(V5)V1V2V5V4V3G2對于有向圖G

7、=(V，E)，若有向弧?E，則稱頂點(diǎn)v“鄰接到”頂點(diǎn)w，頂點(diǎn)w“鄰接自”頂點(diǎn)v，弧與頂點(diǎn)v和w“相關(guān)聯(lián)”。對有向圖G=(V，E)，若?vi?V，圖G中以頂點(diǎn)v作為尾或初始的有向邊(弧)的數(shù)目稱為頂點(diǎn)v的出度(Outdegree)，記為OD(v)；以v作為頭或終點(diǎn)的有向邊(弧)的數(shù)目稱為頂點(diǎn)v的入度(Indegree)，記為ID(v)。頂點(diǎn)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)一般地，如果頂點(diǎn)vi在的度記為TD(vi)，那么一個(gè)有n個(gè)頂點(diǎn)，e條邊或弧的圖，滿足：∑TD(vi)=2e路徑(Path)：對無向圖G=(V，E)，若從頂點(diǎn)vi經(jīng)過若干條邊能到達(dá)vj，稱頂點(diǎn)vi和vj是連通的，又稱頂點(diǎn)vi到vj有路徑。對有向圖G=(V，E)，從頂點(diǎn)vi到vj有有向路徑，指的是從頂點(diǎn)vi經(jīng)過若干條有向邊(弧)能到達(dá)vj。路徑的長度：路徑上邊或有向邊(弧)的數(shù)目稱為該路徑的長度。在一條