圖的定義和基本術(shù)語(yǔ)

1、圖的定義和基本術(shù)語(yǔ)數(shù) 據(jù) 結(jié) 構(gòu)圖圖的定義和基本術(shù)語(yǔ)圖：圖G由V（G）和E（G）這兩個(gè)集合所組成，記為G=（V，E），其中V（G）是頂點(diǎn)（Vertex）的非空集，每個(gè)頂點(diǎn)可以標(biāo)以不同的字符或數(shù)字；E（G）是邊（Edge）的集合，特殊情況下E（G）可以是空集。每個(gè)邊由其所連接的兩個(gè)頂點(diǎn)表示。無(wú)向圖：對(duì)于一個(gè)圖G，若邊集合E（G）為無(wú)向邊的集合，則稱(chēng)該圖為無(wú)向圖。有向圖：對(duì)于一個(gè)圖G，若邊集合E（G）為有向邊的集合，則稱(chēng)該圖為有向圖。圖圖6.1 有向圖與無(wú)向圖無(wú)向圖G1有向圖G2圖完全圖：在一個(gè)有n個(gè)頂點(diǎn)的無(wú)向圖中，若每個(gè)頂點(diǎn)到其它（n-1）個(gè)頂點(diǎn)都連有一條邊，則圖中共有n(n-1)/2條邊，這種

2、圖稱(chēng)為完全圖（Complete graph，也稱(chēng)完備圖）。左圖所示就是n=4的完全圖，它一共有六條邊。 圖權(quán)和網(wǎng)絡(luò)：有些圖， 對(duì)應(yīng)每條邊有一相應(yīng)的數(shù)值，這個(gè)數(shù)值叫做該邊的權(quán)(Weight)。邊上帶權(quán)的圖稱(chēng)為帶權(quán)圖，也稱(chēng)為網(wǎng)絡(luò)(Network)。子圖：設(shè)有兩個(gè)圖G =(V,E)和G=(V,E)，若V(G)是V(G)的子集，且E(G)是E(G)的子集，則稱(chēng)G是G的子圖(Subgraph)。例如圖6.3所示的圖是圖6.1中G1的一些子圖。 圖圖6.3 子圖圖頂點(diǎn)的度：圖中與每個(gè)頂點(diǎn)相連的邊數(shù)，叫該頂點(diǎn)的度(Degree)。例如圖6.1的圖G1中，頂點(diǎn)的度數(shù)為2，頂點(diǎn)的度數(shù)為3，。 入度、出度：對(duì)于有

3、向圖，頂點(diǎn)的度分為入度和出度，入度是以該頂點(diǎn)為終點(diǎn)的入邊數(shù)目；出度是以該頂點(diǎn)為起點(diǎn)的出邊數(shù)目，該頂點(diǎn)的度等于其入度和出度之和。例如在圖6.1的圖G2中，頂點(diǎn)的入度為1，出度為2，而頂點(diǎn)的入度為1，出度為0，因?yàn)橛幸粭l邊指向它，而沒(méi)有邊從它指出去。 圖路徑：在一個(gè)圖中，若從某頂點(diǎn)Vp出發(fā)，沿一些邊經(jīng)過(guò)頂點(diǎn)V1,V2,Vm到達(dá)，Vq，則稱(chēng)頂點(diǎn)序列(Vp, V1,V2,Vm, Vq)為從Vp到Vq的路徑(Path)。路徑長(zhǎng)度：對(duì)于無(wú)權(quán)的圖，路徑長(zhǎng)度指的是沿此路徑上邊的數(shù)目；對(duì)于有權(quán)圖，一般是取沿路徑各邊的權(quán)之和作為此路徑的長(zhǎng)度。若一條路徑上各頂點(diǎn)均不重復(fù)，即路徑經(jīng)過(guò)每一頂點(diǎn)不超過(guò)一次，則此路徑叫做簡(jiǎn)

4、單路徑。如果從一個(gè)頂點(diǎn)出發(fā)又回到該頂點(diǎn)，即Vp與Vq相同，則此路徑叫做環(huán)路（Cycle）。圖連通、連通圖：在無(wú)向圖中，如果從頂點(diǎn)Vi到頂點(diǎn)Vj之間有路徑，則稱(chēng)這兩個(gè)頂點(diǎn)是連通的。如果圖中任意一對(duì)頂點(diǎn)都是連通的，則稱(chēng)此圖是連通圖(Connected graph)。連通分量：例如圖6.1中的圖G1是連通圖。圖6.4中的圖就是非連通圖，非連通圖的每一個(gè)極大連通子圖叫連通分量(Connected Component)，此圖包括二個(gè)連通分量。 圖圖6.4 非連通圖G圖強(qiáng)連通圖和強(qiáng)連通分量：在有向圖G中，如果從頂點(diǎn)Vi到頂點(diǎn)Vj和從頂點(diǎn)Vj到頂點(diǎn)Vi之間都有路徑，則稱(chēng)這兩個(gè)頂點(diǎn)是強(qiáng)連通的。如果圖中任何一對(duì)頂點(diǎn)都是強(qiáng)連通的，則此圖叫做強(qiáng)連通圖。非強(qiáng)連通圖的每一個(gè)極大強(qiáng)連通子圖叫做強(qiáng)連通分