圖的定義與術(shù)語

在線性表中，每個元素之間只有一個直接前驅(qū)和一個直接后繼，在樹形結(jié)構(gòu)中，數(shù)據(jù)元素之間是層次關(guān)系，并且每一層上的數(shù)據(jù)元素可能和下一層中多個元素相關(guān)，但只能和上一層中一個元素相關(guān)。

但這僅僅都只是一對一，一對多的簡單模型，如果要研究如人與人之間關(guān)系就非常復(fù)雜了。

萬惡圖為首，前邊可能有些童鞋會感覺樹的術(shù)語好多，可來到了圖這章節(jié)，你才知道什么叫做真正的術(shù)語多！

圖的定義

圖（Graph）是由頂點的有窮非空集合和頂點之間邊的集合組成，通常表示為：G(V,E)，其中，G表示一個圖，V是圖G中頂點的集合，E是圖G中邊的集合。

對于圖的定義，我們需要明確幾個注意的地方：

1. 線性表中我們把數(shù)據(jù)元素叫元素，樹中叫結(jié)點，在圖中數(shù)據(jù)元素我們則稱之為頂點(Vertex)。
2. 線性表可以沒有數(shù)據(jù)元素，稱為空表，樹中可以沒有結(jié)點，叫做空樹，而圖結(jié)構(gòu)在咱國內(nèi)大部分的教材中強調(diào)頂點集合V要有窮非空。
3. 線性表中，相鄰的數(shù)據(jù)元素之間具有線性關(guān)系，樹結(jié)構(gòu)中，相鄰兩層的結(jié)點具有層次關(guān)系，而圖結(jié)構(gòu)中，任意兩個頂點之間都可能有關(guān)系，頂點之間的邏輯關(guān)系用邊來表示，邊集可以是空的。

圖的各種奇葩定義

無向邊：若頂點Vi到Vj之間的邊沒有方向，則稱這條邊為無向邊(Edge)，用無序偶(Vi,Vj)來表示。

上圖G1是一個無向圖，G1={V1,E1}，其中

• V1={A,B,C,D}，
• E1={(A,B),(B,C),(C,D),(D,A),(A,C)}

有向邊：若從頂點Vi到Vj的邊有方向，則稱這條邊為有向邊，也成為弧(Arc)，用有序偶<Vi,Vj>來表示，Vi稱為弧尾，Vj稱為弧頭。

上圖G2是一個無向圖，G2={V2,E2}，其中

• V2={A,B,C,D}，
• E2={<B,A>,<B,C>,<C,A>,<A,D>}

簡單圖：在圖結(jié)構(gòu)中，若不存在頂點到其自身的邊，且同一條邊不重復(fù)出現(xiàn)，則稱這樣的圖為簡單圖。

以下兩個則不屬于簡單圖：

無向完全圖：在無向圖中，如果任意兩個頂點之間都存在邊，則稱該圖為無向完全圖。含有n個頂點的無向完全圖有n*(n-1)/2條邊。

有向完全圖：在有向圖中，如果任意兩個頂點之間都存在方向互為相反的兩條弧，則稱該圖為有向完全圖。含有n個頂點的有向完全圖有n*(n-1)條邊。

稀疏圖和稠密圖：這里的稀疏和稠密是模糊的概念，都是相對而言的，通常認為邊或弧數(shù)小于n*logn（n是頂點的個數(shù)）的圖稱為稀疏圖，反之稱為稠密圖。

有些圖的邊或弧帶有與它相關(guān)的數(shù)字，這種與圖的邊或弧相關(guān)的數(shù)叫做權(quán)(Weight)，帶權(quán)的圖通常稱為網(wǎng)(Network)。

假設(shè)有兩個圖G1=(V1,E1)和G2=(V2,E2)，如果V2?V1，E2?E1，則稱G2為G1的子圖(Subgraph)。

圖的頂點與邊之間的關(guān)系

對于無向圖G=(V,E)，如果邊(V1,V2)∈E，則稱頂點V1和V2互為鄰接點(Adjacent)，即V1和V2相鄰接。

邊(V1,V2)依附(incident)于頂點V1和V2，或者說邊(V1,V2)與頂點V1和V2相關(guān)聯(lián)。

頂點V的度(Degree)是和V相關(guān)聯(lián)的邊的數(shù)目，記為TD(V)，如下圖，頂點A與B互為鄰接點，邊(A,B)依附于頂點A與B上，頂點A的度為3。

對于有向圖G=(V,E)，如果有<V1,V2>∈E，則稱頂點V1鄰接到頂點V2，頂點V2鄰接自頂點V1。

以頂點V為頭的弧的數(shù)目稱為V的入度(InDegree)，記為ID(V)，以V為尾的弧的數(shù)目稱為V的出度(OutDegree)，記為OD(V)，因此頂點V的度為TD(V)=ID(V)+OD(V)。

下圖頂點A的入度是2，出度是1，所以頂點A的度是3。

無向圖G=(V,E)中從頂點V1到頂點V2的路徑(Path)。

下圖用紅線列舉了從頂點B到頂點D的四種不同路徑：

如果G是有向圖，則路徑也是有向的。

下圖用紅線列舉頂點B到頂點D的兩種路徑，而頂點A到頂點B就不存在路徑啦：

路徑的長度是路徑上的邊或弧的數(shù)目。

第一個頂點到最后一個頂點相同的路徑稱為回路或環(huán)(Cycle)。

序列中頂點不重復(fù)出現(xiàn)的路徑稱為簡單路徑，除了第一個頂點和最后一個頂點之外，其余頂點不重復(fù)出現(xiàn)的回路，稱為簡單回路或簡單環(huán)。

下圖左側(cè)是簡單環(huán)，右側(cè)不是簡單環(huán)：

連通圖

在無向圖G中，如果從頂點V1到頂點V2有路徑，則稱V1和V2是連通的，如果對于圖中任意兩個頂點Vi和Vj都是連通的，則稱G是連通圖(ConnectedGraph)

下圖左側(cè)不是連通圖，右側(cè)是連通圖：

無向圖中的極大連通子圖稱為連通分量。

注意以下概念：

1. 首先要是子圖，并且子圖是要連通的；
2. 連通子圖含有極大頂點數(shù)；
3. 具有極大頂點數(shù)的連通子圖包含依附于這些頂點的所有邊。

在有向圖G中，如果對于每一對Vi到Vj都存在路徑，則稱G是強連通圖。

有向圖中的極大強連通子圖稱為有向圖的強連通分量。

下圖左側(cè)并不是強連通圖，右側(cè)是。并且右側(cè)是左側(cè)的極大強連通子圖，也是左側(cè)的強連通分量。

最后我們再來看連通圖的生成樹定義。

所謂的一個連通圖的生成樹是一個極小的連通子圖，它含有圖中全部的n個頂點，但只有足以構(gòu)成一棵樹的n-1條邊。

如果一個有向圖恰有一個頂點入度為0，其余頂點的入度均為1，則是一棵有向樹。