-
子圖
鎖定
子圖是圖論的基本概念之一,指節點集和邊集分別是某一圖的節點集的子集和邊集的子集的圖。若這個節點子集或邊子集是真子集,則稱這個子圖為真子圖;若圖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的極大子圖,在所有極大子圖中,邊數最多的那個稱為最大子圖。
[1]
- 中文名
- 子圖
- 外文名
- subgraph
- 所屬領域
- 圖論
- 相關概念
- 母圖、真子圖、補圖等
子圖基礎知識
子圖子圖的定義
設
為一圖,
且
,稱以
為頂點集,以G中兩個端點都在
中的邊組成邊集
的圖為G的
導出子圖,記作
,又設
且
,稱以
為邊集,以
中邊關聯的頂點為頂點集
的圖為G的
導出的子圖,記作
。
子圖補圖
若圖
,則稱G是自補圖。
子圖相關定理
證明:因為n階圖G是自補圖,所以G與
同構。於是完全圖
的
條邊將各有一半為G與
的邊,即G與
均有
條邊。而圖G的邊數是非負整數,故4一定能整除
,而連續的兩個整數n-1與n總是一個為奇數,一個為偶數,故
或
(k為非負整數)。證畢。
子圖圖的操作
設
為無向圖。
(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之間加一條邊
,稱為加新邊。
在收縮邊和加新邊過程中可能產生環和平行邊。