?目錄

前言

圖的基本概念

1.什么是圖？

2 .圖的相關(guān)術(shù)語

3 .有向圖和無向圖

4.簡單圖和多重圖

5.連通圖、強(qiáng)連通圖、非連通圖

?6.權(quán)與網(wǎng)

7.子圖和(強(qiáng))連通分量

?8.生成樹和生成森林

---

前言

? ? ? ? 今天我們學(xué)習(xí)一種新的數(shù)據(jù)結(jié)構(gòu)-----圖，大家在日常生活中經(jīng)常都會跟“圖”打交道，比如說地圖，電路圖等等……，那我們都會發(fā)現(xiàn)圖都有一個共同特點(diǎn)，那就是圖里面的路徑是沒有規(guī)律的，一個地點(diǎn)到另一個地點(diǎn)的路徑是不唯一的，同樣的在數(shù)據(jù)結(jié)構(gòu)當(dāng)中圖也是這樣子的，那下面就一起進(jìn)入到圖的學(xué)習(xí)當(dāng)中吧~

圖的基本概念

1.什么是圖？

????????前面總結(jié)了“樹”這種數(shù)據(jù)結(jié)構(gòu)，而這篇博客總結(jié)的是更為復(fù)雜的一種數(shù)據(jù)結(jié)構(gòu)：圖（graph），它表明了物件與物件之間的“多對多”的一種復(fù)雜關(guān)系。圖包含了兩個基本元素：頂點(diǎn)（vertex, 簡稱V）和邊（edge,簡稱E）。

?定義：結(jié)點(diǎn)集合V={v1,v2,v3,v4……}和連接節(jié)點(diǎn)的邊集合 E={e1,e2,e3,e4……}組成的二元組G=<V,E> 稱作為圖（graph）。圖中節(jié)點(diǎn)集合的基數(shù)n稱作為圖的階數(shù)(order)。圖G<V,E>稱作為n階圖或者（n,m）圖。

2 .圖的相關(guān)術(shù)語

完全圖: 任意兩個點(diǎn)都有一條邊相連

?

稀疏圖: 有很少邊或弧的圖 (e<nlogn)
稠密圖:有較多邊或弧的圖。
網(wǎng):邊/弧帶權(quán)的圖。
鄰接:有邊/弧相連的兩個頂點(diǎn)之間的關(guān)系
????????存在(vi vj)，則稱vi和vj;互為鄰接點(diǎn);
????????存在<vi,vj>，則稱vi鄰接到vj， vi鄰接于vj

關(guān)聯(lián)(依附): 邊/弧與頂點(diǎn)之間的關(guān)系
????????存在(vi, vj)/ <vi, vj>， 則稱該邊/狐關(guān)聯(lián)于vi和vj

頂點(diǎn)的度: 與該頂點(diǎn)相關(guān)聯(lián)的邊的數(shù)目，記為TD(v)在有向圖中,頂點(diǎn)的度等于該頂點(diǎn)的入度與出度之和。

????????頂點(diǎn) v 的入度是以v 為終點(diǎn)的有向邊的條數(shù)記作ID(v)

????????頂點(diǎn) v 的出度是以 v 為始點(diǎn)的有向邊的條數(shù)記作 OD(v)

路徑:接續(xù)的邊構(gòu)成的頂點(diǎn)序列。
路徑長度: 路徑上邊或弧的數(shù)目/權(quán)值之和?；芈?環(huán)): 第一個頂點(diǎn)和最后一個頂點(diǎn)相同的路徑簡單路徑: 除路徑起點(diǎn)和終點(diǎn)可以相同外，其余頂點(diǎn)均不相同的路徑

簡單回路(簡單環(huán)): 除路徑起點(diǎn)和終點(diǎn)相同外，其余頂點(diǎn)均不相同的路徑?

3 .有向圖和無向圖

?　　如果給圖的每條邊規(guī)定一個方向，那么得到的圖稱為有向圖。在有向圖中，從一個頂點(diǎn)出發(fā)的邊數(shù)稱為該點(diǎn)的出度，而指向一個頂點(diǎn)的邊數(shù)稱為該點(diǎn)的入度。相反，邊沒有方向的圖稱為無向圖。

1.有向圖的寫法表示：

2.無向圖的寫法表示：

4.簡單圖和多重圖

定義：含有平行邊的圖叫做多重圖

? ? ? ? ? ? 既不含平行邊，又不含有自換的圖叫做簡單圖?

多重圖：?簡單圖：

5.連通圖、強(qiáng)連通圖、非連通圖

連通圖：在無向圖G=( V,E) )中，若對任何兩個頂點(diǎn) v、u都存在從v 到 u 的路徑，則稱G是連通圖

強(qiáng)連通圖：在有向圖G=( V,E) )中，若對任何兩個頂點(diǎn) v、u都存在從v 到 u 的路徑，則稱G是強(qiáng)連通圖

區(qū)分，無向圖滿足連通性，就叫做連通圖，有向圖叫做強(qiáng)連通圖

非連通圖：跟連通圖反過來，存在一個節(jié)點(diǎn)v無法到達(dá)另一個節(jié)點(diǎn)u的圖，就稱作為非連通圖?

?6.權(quán)與網(wǎng)

權(quán)與網(wǎng)：

????????圖中邊或弧所具有的相關(guān)數(shù)稱為權(quán)。表明從一個頂點(diǎn)到另一個頂點(diǎn)的距離或耗費(fèi)
????????帶權(quán)的圖稱為網(wǎng)

網(wǎng)，如圖所示：

7.子圖和(強(qiáng))連通分量

子圖：

下圖中，b和c哪個是a的子圖？ 答案：c?

連通分量：無向圖G 的極大連通子圖稱為G的連通分量

????????極大連通子圖意思是: 該子圖是 G 連通子圖，將G 的任何不在該子圖中的頂點(diǎn)加入，子圖不再連通

強(qiáng)連通分量：有向圖G 的極大強(qiáng)連通子圖稱為G的強(qiáng)連通分量

????????極大強(qiáng)連通子圖意思是: 該子圖是G的強(qiáng)連通子圖，將D的任何不在該子圖中的頂點(diǎn)加入，子圖不再是強(qiáng)連通的.

補(bǔ)充

極小連通子圖:該子圖是G 的連通子圖，在該子圖中刪除任何一條邊子圖不再連通

?8.生成樹和生成森林

生成樹:包含無向圖G 所有頂點(diǎn)的極小連通子圖

生成森林:對非連通圖，由各個連通分量的生成樹的集合

以上就是本期的全部內(nèi)容了，如果你學(xué)過離散數(shù)學(xué)就都學(xué)過這些的，這些圖論的知識點(diǎn)很重要的，一定要會哦！下一期我們就講圖的存儲結(jié)構(gòu)。

分享一張壁紙：?