2.1.3 圖的運算

與數、向量和矩陣相似，圖與圖之間，以及圖自身存在許多運算，這些運算代表了不同的功能。隨著圖論研究的深入，未來還會產生更多的圖運算。本小節介紹一些基本的圖運算。

1．子圖與圖的一元運算

對于圖G和H，如果并且，那么稱H是的子圖；進一步，若或者，則稱H是的真子圖。在圖的子圖中，有兩類特殊且重要的子圖：生成子圖與導出子圖。

設為的一個子圖，若，則稱為的生成子圖。設且，由導出的子圖為頂點導出子圖，記作，它是圖的一個子圖：，。與頂點導出子圖相似，可定義邊導出子圖（簡稱邊導子圖）：設是圖的非空邊子集，以為邊集，以中邊的端點的全體為頂點集所構成的子圖稱為由導出的的子圖，記作。

（1）刪點運算。導出子圖簡記為（），它是從中刪去中的頂點及與這些頂點相關聯的全部邊得到的子圖。特別地，當時，簡記為，稱為的刪點子圖。

（2）刪邊運算。若，則從中刪去邊所得之圖記作，稱為刪邊子圖。若且，則表示從中刪去得到的子圖。圖2.8所示為各種子圖的示例。

（a） 　　　　　　　　　　　　　　　　　　　　　　　　　　（b） 　　　　　　　　　　　　　　　　　　　　　　　　　　（c）

（d） 　　　　　　　　　　　　　　　　　　　　　　　　　　（e） 　　　　　　　　　　　　　　　　　　　　　　　　　　（f）

圖2.8　各種子圖的示例

（a）圖　（b）的一個生成子圖　（c）　（d）　（e）　（f）

基于子圖的概念，下面給出連通圖與樹的定義。

設是一個階圖。若，在中存在從到的一條路，則稱是連通的，或稱為連通圖。令H是G的一個子圖，如果H是連通的，并且H不是G的任何連通子圖的真子圖，那么稱H是G的一個連通分支。若在中存在一個子圖是圈，則稱是含圈圖，否則稱為森林。特別地，連通的森林被稱為樹。換言之，樹就是連通的無圈圖。

刪點運算與刪邊運算均為圖的一元運算，它們是針對一個圖的運算。

2．二元運算

下面給出5種常用的兩個圖之間的運算，也稱為圖的二元運算：并運算、交運算、差運算、環和運算、聯運算。這里，用和表示兩個圖。

（1）并運算，記作。

若與無公共邊，即和的邊不重合，則稱為和的直和，故本書提及直和運算時，參與運算的圖之間沒有公共邊。

（2）交運算，記作。

（3）差運算，記作，是指從中刪除的邊所得的子圖。

（4）環和運算，記作，是指由與的并減與的交所得到的圖，即。

上述4種運算的示例如圖2.9所示。

（a） 　　　　　　　　　　　　　　　　　　　　　　　　　　　　（b） 　　　　　　　　　　　　　　　　　　　　　　　　　　　　（c）

（d） 　　　　　　　　　　　　　　　　　　　　　　　　　　　　（e） 　　　　　　　　　　　　　　　　　　　　　　　　　　　　（f）

圖2.9　并運算、交運算、差運算與環和運算的示例

（a）　（b）　（c）　（d）　（e）　（f）

（5）聯運算，記作。頂點集與邊集分別為

圖2.10所示為與和它們的聯圖。

（a） 　　　　　　　　　　　　　　　　　　　　　　（b） 　　　　　　　　　　　　　　　　　　　　　　（c） 　　　　　　　　

圖2.10　兩個圖與它們的聯圖

（a）　（b）　（c）

3．其他一元運算

刪點運算、刪邊運算均為圖的一元運算，下面給出另外兩個常用的一元運算：補運算與收縮運算。

（1）補運算。設是簡單圖，將的補運算（簡稱補）記作，其中，邊集且。圖2.11所示為圖與它的補。易證：一個階簡單圖與它的補的并圖是一個階完全圖，即。故有

注2.5　當且僅當一個圖的補是空圖時這個圖是完全圖。

（a） 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（b）

圖2.11　圖和它的補

（a）　（b）

在網絡分析或系統分析研究中，圖與它的補之間的相互關系有直接應用：一個網絡的結構越復雜，它的補網絡的結構就越簡單。所以，可通過研究補網絡來分析原網絡的特性。

（2）收縮運算。設是一個簡單圖，。在中，收縮是指：把中的頂點子集視為一個（新的）頂點，記作；刪除G中頂點都在中的邊；中原來與中頂點關聯的邊變成與關聯；中其余的頂點與邊保持不變。我們把這樣得到的新圖稱為圖關于的收縮圖，記作，并把此過程稱為關于頂點子集的收縮運算。特別地，且當，且時，稱為在中收縮邊得到的圖，記作，并把此過程稱為縮邊運算。圖2.12所示為圖與關于頂點子集、邊及的收縮圖、及。

（a） 　　　　　　　　　　　　　　　　　　　　　　　　　　（b） 　　　　　　　　　　　　　　　　　　　　　　　　　　（c）

（d）

圖2.12　圖與關于頂點子集、邊及的收縮圖、及

（a）　（b）　（c）　（d）