子圖

子圖是圖論的基本概念之一，指節點集和邊集分別是某一圖的節點集的子集和邊集的子集的圖。若這個節點子集或邊子集是真子集，則稱這個子圖為真子圖；若圖G的每一個節點也是它的子圖H的節點，則稱H是G的支撐子圖。設S是V(G)的子集，以S為節點集，以G的所有那些兩端點都在S內的邊組成邊集，所得到的G的子圖稱為S在G中的導出子圖，或更確切地，節點導出子圖。設B是E(G)的子集，由G的所有與B內至少有一條邊關聯的節點組成節點集，以B為邊集，所得到的G的子圖稱為B在G中的邊導出子圖；對於某種性質P，若一個圖的具有P的子圖不是任何具有P的子圖的真子圖，則稱它為具有P的極大子圖，在所有極大子圖中，邊數最多的那個稱為最大子圖。

基礎知識

子圖的定義

設為兩個圖（同為無向圖或同為有向圖），若且，則稱G'是G的子圖，G是G‘的母圖，記作，又若且，則G'稱是G的 真子圖，若，則稱G'是G的 生成子圖。

設為一圖，且 ,稱以為頂點集，以G中兩個端點都在中的邊組成邊集的圖為G的 導出子圖，記作，又設且，稱以為邊集，以中邊關聯的頂點為頂點集的圖為G的 導出的子圖，記作。

在圖1中，設G如圖1(a)所示，取，則的導出子圖如圖1(b)所示，取，則的導出子圖如圖1(c)所示。

圖1（a）

圖1（b）

圖1（c）

補圖

設為n階無向簡單圖，以V為頂點集，以所有使G成為完全圖的的添加邊組成的集合為邊集的圖，稱為G的補圖，記作。

若圖，則稱G是自補圖。

圖2中，（b）和（c）互為補圖，（a）是自補圖。

圖2（a）

圖2（b）

圖2（c）

相關定理

若n階圖G是自補圖，則或，k為非負整數，且圖G有條邊。

證明：因為n階圖G是自補圖，所以G與同構。於是完全圖的條邊將各有一半為G與的邊，即G與均有條邊。而圖G的邊數是非負整數，故4一定能整除，而連續的兩個整數n-1與n總是一個為奇數，一個為偶數，故或（k為非負整數）。證畢。

圖3（a）

圖3(b)

圖的操作

設為無向圖。

(1)設，用表示從G中去掉邊e，稱為 刪除邊e。又設，用表示從G中刪除E'中的所有邊，稱為刪除E'。

(2)設，用表示從G中去掉v及所關聯的一切邊，稱為 刪除頂點v，又設，用表示從G中刪除中的所有邊，稱為刪除V'。

(3)設邊，用表示從G中刪除e後，將e的兩個端點u，v用一個新的頂點w（或用u或用v充當w）代替，使w關聯e以外u，v關聯的所有邊，稱為邊e的收縮。

(4)設（u，v可能相鄰，也可能不相鄰），用（或）表示在u，v之間加一條邊，稱為 加新邊。

在收縮邊和加新邊過程中可能產生環和平行邊。

在圖4中，設(a)圖為G，則(b)圖為，(c)圖為，(d)圖為，(e)圖為，而圖為。

圖4（a）

圖4（b）

圖4（c）

圖4（d）

圖4（e）

圖4（f）

相關詞條

相關搜尋

熱門詞條

聯絡我們