導出子圖

在圖論中，一個圖的導出子圖(induced subgraph)是指，由該圖頂點的一個子集和該圖中兩端均在該子集的所有邊的集合組成的圖。

基本介紹

• 中文名：導出子圖
• 外文名：induced subgraph
• 適用領域：圖論
• 所屬學科：數學

定義

設圖G = (V, E)，令S⊂V，使得S是G的任意頂點子集。則G的導出子圖G(S)中，其頂點集為S，邊集為G的邊集E中兩個頂點均屬於S的邊的集合。該定義適用於無向圖，有向圖與多重圖。

常用性質

導出子圖的重要類型包括如下內容：

• 導出路徑是路徑的子圖。無權圖中任意兩個頂點之間的最短路徑是一個導出路徑，因為任意一對頂點之間的附加邊，如果可能導致它不能被導出也會導致它不是最短。反之，在距離遺傳圖中，所有導出路徑都是最短路徑。
• 導出周期是誘導子圖或循環。圖的圍長由其最短周期(導出周期)的長度決定。
• 團和獨立集分別為完全圖和無邊圖的導出子圖。
• 導出匹配是匹配的誘導子圖。
• 一個頂點的鄰域是與其相鄰的所有頂點的導出子圖。

子圖-生成子圖-導出子圖

設圖G = (V, E)，V是G中的所有頂點的集合，E是G中所有邊的集合。

• 子圖定義：子圖G’中所有的頂點和邊均包含於原圖G。即E’∈E，並且V’∈V。
• 生成子圖（Spanning Subgraph）定義：生成子圖G’中頂點個數V’必須和原圖G中V的數量相同，而E’∈E即可。
• 導出子圖 （Induced Subgraph）定義：導出子圖G’，V’∈V，但對於V’中任一頂點，只要在原圖G中有對應邊，那么就要在E’中。