子圖是圖論的基本概念之一，指節點集和邊集分別是某一圖的節點集的子集和邊集的子集的圖。若這個節點子集或邊子集是真子集，則稱這個子圖為真子圖；若圖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的極大子圖，在所有極大子圖中，邊數最多的那個稱為最大子圖。
基本介紹
- 中文名：子圖
- 外文名：subgraph
- 所屬領域：圖論
- 相關概念：母圖、真子圖、補圖等
基礎知識,子圖的定義,補圖,相關定理,圖的操作,
基礎知識
子圖的定義
設
為一圖，
且
,稱以
為頂點集，以G中兩個端點都在 中的邊組成邊集
的圖為G的 導出子圖，記作
，又設
且
，稱以
為邊集，以
中邊關聯的頂點為頂點集
的圖為G的
導出的子圖，記作
。
在圖1中，設G如圖1(a)所示，取
，則
的導出子圖 如圖1(b)所示，取
，則
的導出子圖 如圖1(c)所示。
圖1（a）
圖1（b）
圖1（c）補圖
若圖
，則稱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）