誘導子圖

在圖理論的數學字段中，圖形的誘導子圖是另一個圖形，由圖形的頂點的子集以及所有邊緣（來自原始圖）連接該子集中的頂點對。

定義

正式，讓是任何圖表，讓是 $G$ 的任何子集。然後誘導的子圖是其頂點集的圖其邊緣集由所有邊緣組成在。也就是說，對於任何兩個頂點，，，，和相鄰當且僅當它們鄰近。相同的定義適用於無向圖，有向圖甚至多編碼。

誘導的子圖也可以稱為誘導的子圖經過，或（如果上下文可以選擇明確的）誘導的子圖。

誘導子圖的重要類型包括以下內容。

誘導的路徑是誘導的子圖，是路徑。未加權圖中任意兩個頂點之間的最短路徑始終是一條誘發的路徑，因為可能導致其不被誘導的頂點之間的任何其他邊緣也會導致其最短。相反，在距離 - 遺傳圖中，每個誘導的路徑都是最短的路徑。
誘導的循環是誘導的亞圖，是循環。圖的周長是由最短循環的長度定義的，這始終是誘發的循環。根據強大的完美圖定理，誘導的周期及其補充在完美圖的表徵中起著至關重要的作用。
集團和獨立的集合是誘發的子圖，分別是完整的圖形或無進出圖。
誘發的匹配是匹配的誘發子圖。
頂點的鄰域是與之相鄰的所有頂點的誘導子圖。

誘導的子圖同構問題是子圖同構問題的一種形式，即目標是測試是否可以找到一個圖作為另一個圖的誘導子圖。因為它包括集團問題作為一種特殊情況，所以它是NP完整的。