前言：本文主要從數學角度，簡單介紹了圖論中的一些概念與術語，主要基于教材《圖論及其應用》(北京郵電大學出版社)的前6章內容，如有錯誤，誠請指正

---

1.圖的概念

1.1 圖的定義

1.1.1 無向圖相關定義

頂點集/節點集：

其中每個元素稱為圖G的一個頂點/節點

邊集：

其中每個元素 是圖G的一條邊

圖：

其中V(G)為頂點集，E(G)為邊集合

1.1.2 有向圖相關定義

弧集：

其中每個元素 為從 到 的一潭訓

弧相關概念：

弧：ab，稱為一潭訓

頭：b，為弧ab的頭

尾：a，為弧ab的尾

出弧：對a，弧ab是出弧

入弧：對b，弧ab是入弧

有向圖：

其中V(D)為頂點集，A(D)為弧集

基礎圖：

對于有向圖，去掉弧的方向，端點不變，即得到基礎圖；有向圖去掉方向

定向圖：

對于無向圖，為每條邊指定一個方向，即得到定向圖；無向圖加方向

1.2 圖的基本概念

1.2.1 基本概念

階：圖G中頂點個數

或

關聯：

邊ab與頂點a/b相關聯，頂點a/b與邊ab相關聯

相鄰：

a與b相鄰；a是b的鄰點/鄰居

內/外鄰點：

a為b的內鄰點；b為a的外鄰點

對于一個點，所有指向其的點為內鄰點，所有由其指出的點為外鄰點

端點：

a與b是ab的兩個端點

環：

k是一個環，其兩端點相同

棱：

邊ab是一條棱，其兩端點不同

孤立點：

不與任何頂點相鄰的頂點

重邊/平行邊：

邊p與邊q是重邊

重弧：

弧p與弧q是重弧，其端點相同且方向一致

鄰域：

即圖中與u相鄰的點構成的集合

內/外鄰域：

內鄰域： ，即v的所有內鄰點構成的集合

外鄰域： ，即v的所有外鄰點構成的集合

獨立集：

中任意兩個頂點在圖G中互不相鄰，則稱V'為圖G的獨立集

1.2.2 常見圖定義

簡單圖：無環、無重邊的圖

平凡圖：僅有一個頂點的圖(可有多潭訓)

空圖/零圖：沒有邊的圖

有限圖：頂點數與邊數都是有限的圖

嚴格有向圖：無環、無重弧的圖

1.2.3 度相關概念

無向圖：

度： ，頂點v所關聯的邊的數目(環計兩次)

奇點：度為奇數的點

偶點：度為偶數的點

懸掛點/葉點：度為1的點

孤立點：度為0的點

最大度：

最小度：

有向圖：

出度： ，即點v出弧的數目

入度： ，即點v入弧的數目

最大出度：

最大入度：

最小出度：

最小入度：

源點： ，即入度為0的點

匯點： ，即出度為0的點

1.3 同構與恒等

恒等：兩圖的頂點集與邊集完全相同

例：

G與H恒等，與F不恒等

同構：兩圖的頂點集存在某種映射，邊集也存在某種映射，使其能一一對應

例：

G、H、F三者同構

證明：G與H同構

對于點集，可以找到如下映射

對于邊集，可以找到如下映射

能夠使兩圖一一對應，因此同構

1.4 完全圖

完全圖：

定義：圖中任意兩點間都有邊相連，記作

例：

偶圖/二分圖/二部圖：

定義：頂點集可劃分X與Y兩不相交非空子集，對于每條邊，都有一個頂點在X中，另一個頂點在Y中；記作G=(X,Y;E)

例：

完全偶圖/完全二分圖/完全二部圖：

定義：X與Y中任意兩點都有唯一邊相連

例：

1.5 子圖

1.5.1 基本概念

子圖：若且，則稱H是G的子圖，記作

母圖：若 ，則稱G是H的母圖

真子圖：若 且 ，則稱H是G的真子圖

生成子圖：若 且 ，則稱H是G的生成子圖

點匯出子圖：

定義：若 (即以V'為頂點集，V'中所有邊為邊集)，則 稱為G的點匯出子圖

例：

邊匯出子圖：

定義：若(即以E'為邊集，E'中所有端點為點集)，則 稱為G的邊匯出子圖

例：

基礎簡單圖：從圖G中去掉所有重邊和環后所得的簡單圖，稱為圖G的基礎簡單圖

1.5.2 圖的基本運算

點減法：

定義：

邊減法：

定義：

例：

并：

交：

1.5.3 其他概念

不相交：若 ，則稱G1與G2為不相交的

邊不相交：若 ，則稱G1與G2為邊不相交的

聯圖：對于兩不相交的圖 和 的并圖 ，連接 與 中每對頂點所得到的圖，稱為圖與的聯圖，記作

k-正則圖：

定義：無向圖G中的每個頂點的度數都是常數k，則稱為k-正則圖

例：

補圖：

定義：

例：

極大子圖：圖G的子圖H具有性質P，若不存在具有性質P的子圖F，使得 ，則稱H為圖G的具有性質P的極大子圖

極小子圖：圖G的子圖H具有性質P，對任意的具有性質P的子圖F，使得 ，則稱H為圖G的具有性質P的極小子圖

線圖/邊圖：以圖G的邊集E(G)作為頂點集合，兩頂點相鄰的充要條件是這兩頂點在圖G中是相鄰的邊

1.6 路與連通

1.6.1 路及相關概念

途徑： 圖G中一個頂點與邊交替出現的有限非空序列，；不引起混淆時可簡化，將其中的邊去掉

起點：

終點：

內部頂點：

長：途徑W的邊數k

節/段：途徑W上任意連續一段

逆途徑：將起點與終點調換得到的逆向序列，記作

銜接：若途徑W的終點是途徑W'的起點，則可將其銜接，記作WW'

跡：邊互不相同的途徑(點可重復)

跡長：跡上的邊數

路：頂點互不相同的途徑(邊可重復)

路長：路上的邊數

最長路：對于(u,v)兩點間，邊數最多的路

最短路：對于(u,v)兩點間，邊數最少的路

距離：(u,v)兩點的最短路，即u與v的距離

例子：

1.6.2 連通的相關概念

連通：u與v之間有路

連通圖：圖中任意兩點間都有路

連通分支：

定義：

例：連通分支數為3

直徑： ，即圖中最長的最短路

邊割/割集：

即為邊割

可達：有向圖D中，存在從u到v的路，則稱v為從u可達的

雙向連通：若u與v相互可達，則稱u與v雙向連通

競賽圖：完全圖的定向圖

1.7 圈

閉途徑：起點與終點相同且長度大于0的途徑

閉跡/回路：起點與終點相同的跡

圈：起點與終點相同的路

閉途徑/閉跡/圈的長度：包含邊的個數

奇/偶圈：長度為奇數/偶數的圈

k-圈：長度為k的圈

圈長：最短圈的長度

周長：最長圈的長度

Hamilton圈：圖中所有頂點都在圈上

例：

---

2.樹與最優樹

2.1 樹的概念

森林：不含圈的圖

樹：連通的無圈圖

割邊： 若e使得 ，則稱e為圖G的割邊；即去掉該邊，使得圖的連通分支數減小

非割邊：若e使得 ，則稱e為圖G的非割邊

樹葉：樹中度為1的頂點

割點：

若圖G的邊集E(G)可分為兩非空子集 和 ，使得 ,則稱v為圖G的割點

偏心率： ，即v點到距其最遠的頂點w之間的距離

中心：偏心率最小的頂點

半徑： ，即中心點的偏心率

直徑： ，即圖G的最大偏心率

2.2 樹的性質

若G為樹，則以下定義等價：

2.3 生成樹

生成樹：一棵樹T如果是連通圖G的生成子圖，則稱樹T為圖G的生成樹

最優生成樹：所有生成樹中權值合最小的一個

關聯邊割： ，即圖G中所有與頂點v相關聯的邊的集合

鍵：使得 的極小邊集B，稱為圖G的鍵

例：

補圖： ，為圖G中圖H的補圖

余樹：當T為圖G的生成樹時，稱 為圖G的余數

---

3.匹配與覆寫

3.1 匹配

匹配：圖G的一個邊子集M中，每條邊兩個端點不同，且任意兩條邊互不相鄰，則稱M為G的一個匹配

相匹配：若邊 ，則稱點u與點v在M下相匹配

M-飽和：若邊 ，則稱點u與點v為M-飽和的

M-不飽和：若點u所有相關聯的邊都不屬于一個匹配M，則稱u為M-不飽和的

完美匹配：圖G中每一個頂點都被一個匹配M所飽和

最大匹配：對任意匹配M'，都有 ，則稱M為最大匹配

完全匹配：偶圖中的完美匹配

鄰集：N(S)，圖中所有與S中頂點相鄰的頂點集合

1-因子：完美匹配M的邊匯出子圖G[M],稱為G的1-因子

M-交錯路：對于圖G的一個匹配M，P是圖G中一條路，若P的邊交替屬于M和E(G)\M，則稱路P為圖G的M-交錯路

M-可擴路：若交錯路P的起點與終點都是M-不飽和的，則稱P為圖G的M-可擴路

奇分支：頂點數為奇數的分支

偶分支：頂點數為偶數的分支

例：

3.2 覆寫

例圖：

獨立集：圖G的頂點子集V'中任意兩個頂點在圖G中互不相鄰，則稱V'是圖G的獨立集；其匯出子圖G[V']為空圖

例：V'={v1,v5}是獨立集，因為v1與v5不相鄰

團：圖G的頂點子集S中任意兩個頂點在圖G中都相鄰，則稱S為圖G的團；其匯出子圖G[S]為完全圖

覆寫：對于圖G的頂點子集K，若圖G的每條邊中至少有一個端點在K中，則稱K為圖G的覆寫；其匯出子圖G[V\K]為空圖或V\K為獨立集

例：K={v1,v3,v5,v7}是一個覆寫，因為任找一條邊，一定有一個端點屬于K

最大獨立集：頂點數最多的獨立集

獨立數：最大獨立集的頂點數，記作α(G)

例：{v2,v4,v7}為最大獨立集，獨立數α=3

最小覆寫：頂點數最少的覆寫

覆寫數：最小覆寫的頂點數，記作β(G)

例：{v1,v3,v5,v7}為最小覆寫，β=4

---

4.遍歷問題

4.1 Euler圖

環游：通過圖中每條邊至少一次的閉途徑

Euler環游：通過圖中每條邊恰一次的閉途徑

Euler跡：通過圖中每條邊的跡 / 通過圖中每條邊恰一次的途徑(一筆畫)

Euler圖：包含Euler環游的圖

例：Ae1Be3Ce4Be2A 為Euler環游

充要條件：圖G為Euler圖的 <=> 圖G中所有點的度數為偶數

4.2 Hamilton圖

Hamilton路：通過圖中每個頂點的路 = 生成路

Hamilton圈：通過圖中每個頂點的圈 = 生成圈

Hamilton圖：包含Hamilton圈的圖

例：

閉包：

定義：圖G的簡單生成母圖，即由G開始，通過反復將其中不相鄰且度之和大于等等于v的頂點用新邊相連，直到不能繼續為止，記作c(G)

例：后圖為前圖閉包

---

5.網路流

5.1 網路及相關概念

網路：N=(X,Y,I,A,c)為一個網路，當：

(1)D=(V,A)是一個有向圖

(2)c是A上的非負函式

(3)X與Y是兩個非空不相交子集，其余頂點集合為I

發點集合/源點集合：N中的X

發點/源點：X中的頂點

收點集合/宿點集合：N中的Y

收點/宿點：Y中的頂點

中間點集合：N中的I

中間頂點：I中的頂點

容量函式：N中的c

容量：c(a)的值

例：

其中N=(X,Y,I,A,c)，X={x1,x2}，Y={y1,y2,y3}，I={v1,v2,v3,v4}，各容量為邊權值

5.2 流及相關概念

流：定義在N=(X,Y,I,A,c)上的的整數函式f(.)為流，當：

(1)容量約束條件：

(2)守恒條件：

流量：f(a)為弧a上的流量

零流：f(a)=0

合成流出流量(流出凈流量)：

合成流入流量(流入凈流量)：

流值：

例：val f = 6

5.3 最大流

最大流：若不存在 (.)，使得 ，則稱 (.)為最大流

割：對網路N=(x,y,I,A,c)，和V(N)的一個頂點子集S，若 ，則稱為網路N中的割

容量：

最小割：對網路中的一個割K'，若對任意割K都有 ,則稱K'為網路N的最小割

對弧a：

f-零的：f(a)=0

f-正的：f(a)>0

f-不飽和的：f(a)<c(a)

f-飽和的：f(a)=c(a)

對路p：

f-飽和的：l(P)=0

f-不飽和的：l(P)>0

f-可增路：P是以x為起點，以y為終點的f-不飽和路

修改流：

稱f'為網路N基于P的修改流