Loading AI tools
图论 来自维基百科,自由的百科全书
在圖論中,一個圖的導出子圖(induced subgraph)是指,由該圖頂點的一個子集和該圖中兩端均在該子集的所有邊的集合組成的圖。
其正式定義為:設圖 ,令 ,使得 S 是 G 的任意頂點子集。則 G 的導出子圖 中,其頂點集為 S,邊集為 G 的邊集 E 中兩個頂點均屬於 S 的邊的集合。該定義適用於無向圖,有向圖與多重圖。[1]
導出子圖 也可以稱為 S 從 G 中導出的子圖,或者 (如果上下文中G沒有歧義) S 的導出子圖。
導出子圖的重要類型包括如下內容:
導出子圖同構問題是子圖同構問題的一種形式,其目的是檢驗一個圖是否可以作為另一個圖的導出子圖。因為它把分團問題作為一個特例,所以它是NP完備的。[4]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.