一、圖的定義

1、什么是圖？

圖G=(V,E)? ?如圖，無向圖G

頂點集V={,,...,}，用|V|表示圖G的頂點個數

? ?如：V={A,B,C,D} ,|V|=4

邊集E={(u,v)|uV, vV}， 用|E|表示圖G的邊的條數

如：E={(u,v)|(A,B),(A,D),(A,C),(C,D)}，|E|=4zhu

注：

1、圖不可以是空圖。線性表可以是空表，樹可以是空樹

2、圖中不能一個頂點都沒有，V非空

3、但是圖中可以沒有邊，E為空，此時圖中只有頂點沒有邊

2、簡單圖和多重圖

簡單圖的條件：

1、不存在重復邊

2、不存在頂點到自身的邊

多重圖的條件：

某兩個頂點之間的變數大于1條，又允許頂點通過一條邊自身關聯

3、有向圖

E是有向邊（簡稱弧）的有限集合，弧是頂點的有序對。

記為<v,w>，v為弧頭，w為弧尾。也稱v鄰接到w。

如圖為有向圖G，注意邊集E={(u,v)|(A,B),(B,A),(A,C),(A,D),(C,D)}，AB兩個頂點有兩條邊

4、無向圖

E是無向邊的有限結合，邊是頂點的無序對。

記為<v,w>或<w,v>，也稱v和w互為鄰接點。

5、頂點的度，入度、出度

頂點的度針對無向圖、有向圖，所有頂點的度=邊數*2

入度、出度僅用于有向圖

6、路徑、路徑長度、回路

1、路徑

頂點A到頂點D的之間的一條路徑是指頂點序列A,C,D，關聯的邊也是路徑的構成要素

簡單路徑——頂點不重復

2、路徑上的邊的數目成為路徑長度

如，頂點A到頂點D的路徑長度為2

3、第一個頂點和最后一個頂點相同的路徑成為回路或環

簡單回路——除第一個頂點和最后一個頂點之外，其他頂點不重復的回路

如，A-C-D-A

注：

1、若一個圖有n個頂點，并且大于n-1條邊，則此圖一定有環

7、距離

頂點間最短路徑，則此路徑的長度稱為距離

若兩點之間不存在路徑，則距離為無窮(∞)

8、子圖

G=(V,E)和=(,)，若是V的子集，是G的子集，則稱是G的子圖

V()=V(G)，則稱其為G的生成子圖。? （即包含所有頂點）

注：

并非V和E的任何子集都能構成子圖

如果中某些邊的頂點不再中，此時不是圖

9、連通、連通圖、連通分量

此節僅針對無向圖，有向圖與強連通有關

1、連通——頂點v到頂點w有路徑存在

2、連通圖——任意兩個頂點之間均連通

若有n個頂點，至少n-1條邊，成為連通圖；

若有n個頂點，至多條邊，不是連通圖；

計算方法：排除一個點，將其余點的邊都鋪滿

此時，，一旦達到就會形成連通圖。

3、連通分量——無向圖中的極大連通子圖

極大連通子圖——子圖必須連通，包含盡可能多的頂點和邊

10、強連通圖、強連通分量

此節僅針對有向圖，無向圖與連通有關

1、強連通——從頂點v到頂點w和從頂點w到頂點v都有路徑

2、強連通圖——任意一對頂點強連通

若有n個頂點，至少n條邊，成為強連通圖

3、強連通分量——有向圖中的極大強連通子圖

如圖，虛線內記為極大強連通子圖

11、生成樹、生成森林

連通圖的生成樹——包含圖中全部頂點的一個極小連通子圖

極小連通子圖——包含圖中的全部頂點，保持子圖連通且邊數盡可能少

圖中頂點數為n，則生成樹含有n-1條

砍一條邊->非連通圖? ? ? 加一條邊->回路

在非連通圖中，連通分量的生成樹構成了非連通圖的生成森林

12、邊的權、網、帶權路徑長度

邊上帶有權值的圖稱為帶權圖，也稱為網。

路徑上所有邊的權值之和，稱為該路徑的帶權路徑長度。

13、完全圖（也稱簡單完全圖）

對于無向圖，有條邊的無向圖稱為無向完全圖，即完全圖中任意兩個頂點之間都存在邊

對于有向圖，有n(n-1)條弧的有向圖稱為有向完全圖，即任意兩個頂點之間都存在方向相反的兩條弧。也就是條邊。

14、有向樹

有向樹——一個頂點的入度為0，其余頂點的入度均為1的有向圖

有向樹不是強連通圖

n個頂點的樹，必有n-1條邊

n個頂點的圖，若|E|>n-1，則一定有回路

二、易混淆定義

若一個圖有n個頂點，并且大于n-1條邊，則此圖一定有環

圖中頂點數為n，則生成樹含有n-1條

若有n個頂點，至少n-1條邊，成為連通圖；

若有n個頂點，至多條邊，不是連通圖；

若有n個頂點，至少n條邊，成為強連通圖

距離、路徑長度、帶權路徑長度