導出子圖

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

定義

其正式定義為：設圖 ${\displaystyle G=(V,E)}$，令 ${\displaystyle S\subset V}$，使得 S 是 G 的任意頂點子集。則 G 的導出子圖 ${\displaystyle G[S]}$ 中，其頂點集為 S，邊集為 G 的邊集 E 中兩個頂點均屬於 S 的邊的集合。該定義適用於無向圖，有向圖與多重圖。^[1]與子圖（subgraph）的不同之處在於，導出子圖中的兩頂點間若在原圖中有邊，則導出子圖中一定包含此邊，而子圖可包含或不包含該邊。

導出子圖 ${\displaystyle G[S]}$ 也可以稱為 S 從 G 中導出的子圖，或者 (如果上下文中G沒有歧義) S 的導出子圖。

實例

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

盒子中蛇的問題涉及到在超立方體圖中的最長導出路徑

• 導出路徑是路徑的子圖。無權圖中任意兩個頂點之間的最短路徑是一個導出路徑，因為任意一對頂點之間的附加邊，如果可能導致它不能被導出也會導致它不是最短。反之，在距離遺傳圖中，所有導出路徑都是最短路徑。^[2]
• 導出周期是誘導子圖或循環。圖的圍長由其最短周期(導出周期)的長度決定。根據強完美圖定理，導出周期及其補圖在完美圖的特徵中處於至關重要的地位。^[3]
• 團和獨立集分別為完全圖和無邊圖的導出子圖。
• 導出匹配是匹配的誘導子圖。
• 一個頂點的鄰域是與其相鄰的所有頂點的導出子圖。

計算

導出子圖同構問題是子圖同構問題的一種形式，其目的是檢驗一個圖是否可以作為另一個圖的導出子圖。因為它把分團問題作為一個特例，所以它是NP完備的。^[4]