導出子圖
图论
在圖論中,一個圖的導出子圖(induced subgraph)是指,由該圖頂點的一個子集和該圖中兩端均在該子集的所有邊的集合組成的圖。
定義
編輯其正式定義為:設圖 ,令 ,使得 S 是 G 的任意頂點子集。則 G 的導出子圖 中,其頂點集為 S,邊集為 G 的邊集 E 中兩個頂點均屬於 S 的邊的集合。該定義適用於無向圖,有向圖與多重圖。[1]與子圖(subgraph)的不同之處在於,導出子圖中的兩頂點間若在原圖中有邊,則導出子圖中一定包含此邊,而子圖可包含或不包含該邊。
導出子圖 也可以稱為 S 從 G 中導出的子圖,或者 (如果上下文中G沒有歧義) S 的導出子圖。
實例
編輯導出子圖的重要類型包括如下內容:
計算
編輯導出子圖同構問題是子圖同構問題的一種形式,其目的是檢驗一個圖是否可以作為另一個圖的導出子圖。因為它把分團問題作為一個特例,所以它是NP完備的。[4]
參考文獻
編輯- ^ Diestel, Reinhard, Graph Theory, Graduate texts in mathematics 173, Springer-Verlag: 3–4, 2006 [2019-06-14], ISBN 9783540261834, (原始內容存檔於2021-01-25)
- ^ Howorka, Edward, A characterization of distance-hereditary graphs, The Quarterly Journal of Mathematics. Oxford. Second Series, 1977, 28 (112): 417–420, MR 0485544, doi:10.1093/qmath/28.4.417.
- ^ Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin, The strong perfect graph theorem, Annals of Mathematics, 2006, 164 (1): 51–229 [2019-06-14], MR 2233847, arXiv:math/0212070 , doi:10.4007/annals.2006.164.51, (原始內容存檔於2010-06-18).
- ^ Johnson, David S., The NP-completeness column: an ongoing guide, Journal of Algorithms, 1985, 6 (3): 434–451, MR 0800733, doi:10.1016/0196-6774(85)90012-4.