最小頂点分離
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/10/05 07:45 UTC 版)
弦グラフに限らず、頂点分離（英語版）（vertex separator）とは、それらを除去すると残されたグラフが非連結となるような頂点集合を指す。最小頂点分離とは、頂点分離の部分集合が頂点分離とならない場合、その頂点分離を最小頂点分離と呼ぶ。弦グラフの頂点分離はクリークでありDirac (1961)、この性質は弦グラフがパーフェクトグラフである証明に使われた。 弦グラフの族は、A∪SとS∪Bは弦グラフである誘導部分グラフであり、Sはクリークであり、そしてA と B 間に辺が存在しないという3つを満たす、空集合ではない頂点集合A、S、Bに分割できるグラフとして再帰的に定義できる。つまり、クリークによって小さな部分グラフに再帰的に分解されるグラフである。このため、弦グラフは decomposable graphsとも呼ばれていた。
※この「最小頂点分離」の解説は、「弦グラフ」の解説の一部です。
「最小頂点分離」を含む「弦グラフ」の記事については、「弦グラフ」の概要を参照ください。
ウィキペディア小見出し辞書の「最小頂点分離」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 最小頂点分離のページへのリンク
