1、圖的定義

圖 是一個(gè)頂點(diǎn)集合Vertex和一個(gè)頂點(diǎn)間關(guān)系的集合Edge組成，記G=(V,E)
V(Vertex)：頂點(diǎn)的有限非空集合。
E(Edge)：頂點(diǎn)間關(guān)系的有限集合（邊集）。
存在一個(gè)結(jié)點(diǎn)v，可能含有多個(gè)前驅(qū)節(jié)點(diǎn)和后繼結(jié)點(diǎn)。
例如：

2、無向圖和有向圖

無向圖

在G=(V,E)中，如果對于任意的結(jié)點(diǎn)a,b∈V，當(dāng)(a,b)∈E時(shí)，必有(b,a)∈E（即關(guān)系R對稱），此圖稱為無向圖。
無向圖中用不帶箭頭的邊表示頂點(diǎn)的關(guān)系。
例如：
V={1,2,3,4,5}
E={(1,2),(1,3),(1,4),(2,3),(2,5),(3,5),(4,5)}

有向圖

在G=(V,E)中，如果對于任意的結(jié)點(diǎn)a,b∈V，當(dāng)(a,b)∈E時(shí)，(b,a)∈E未必成立，稱此圖為有向圖。
有向圖中通常用帶箭頭的邊連接兩個(gè)有關(guān)聯(lián)的結(jié)點(diǎn)。
例如：
V={1,2,3,4,5}
E={

帶權(quán)圖
一般的圖邊上沒有數(shù)字，邊僅表示兩個(gè)頂點(diǎn)間相連接關(guān)系。如：圖2；
圖中的邊可以加上表示某種含義的數(shù)值，數(shù)值稱為邊的權(quán)。
例如：

3、頂點(diǎn)的度

在無向圖中，頂點(diǎn)v的度是指與頂點(diǎn)v相連的邊的數(shù)目D(v)。
如：圖2中，D(2)=3。

在有向圖中，
入度：

以該頂點(diǎn)為終點(diǎn)的邊的數(shù)目。
出度：

以該頂點(diǎn)為起點(diǎn)的邊的數(shù)目。
度=該頂點(diǎn)的（入度+出度）
如： 圖3中，ID(3)=2，OD(3)=1，D(5)=ID(5)+OD(5)=1+2=3。

奇點(diǎn)\偶點(diǎn):

度數(shù)為奇數(shù)的頂點(diǎn)叫奇點(diǎn)，度數(shù)為偶數(shù)的點(diǎn)叫偶點(diǎn)。
所有頂點(diǎn)的度等于邊數(shù)的兩倍。

4、路徑、回路

在圖G=(V,E)中，過對于結(jié)點(diǎn)a,b，存在滿足下述條件的結(jié)點(diǎn)序列x1...xk(k>1)有x1=a,xk=b,(xi,xi+1)∈E,i=1...k?1，則稱結(jié)點(diǎn)序列x1=a,x2,...,xk=b為結(jié)點(diǎn)a到b的一條路徑，而路徑上邊的數(shù)目(k-1)則稱為該路徑的長度。
如果一條路徑上的結(jié)點(diǎn)除起點(diǎn)x1和終點(diǎn)xk可以相同外，其它結(jié)點(diǎn)均不相同，稱此路徑為一條簡單路徑。x1=xk的簡單路徑稱為回路（也稱為環(huán)）。
例如：

路徑(1,2,3,5)，長度=3；
路徑(1,2,3,5,2)，長度=4；
回路(1,2,5,4,1)，長度=4；

路徑(1,2,5,4)，長度=3.

5、連通性

連通：如果存在一條從頂點(diǎn)u到v的路徑，則稱u和v是連通的。
連通圖：圖中任意兩個(gè)頂點(diǎn)都是連通的，稱為連通圖；否則為非連通圖。
連通分量：無向圖中的極大連通子圖。
例如：
圖2，圖3，連通圖。

圖5，非連通圖。
有3個(gè)連通分量：{1,2,4,5},{3,6},{7,8}