誘導部分グラフ
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/05/18 16:39 UTC 版)
グラフ理論において、誘導部分グラフ（ゆうどうぶぶんグラフ、英: induced subgraph）とは、部分グラフの一種であり、あるグラフから、一部の頂点を取り出し、その頂点対の辺の有無が元のグラフと一致するグラフである。部分グラフは元のグラフから任意の頂点と任意の辺を選択して取り出したグラフであるが、誘導部分グラフは任意の頂点のみを選択し、その頂点間の辺の有無は元のグラフと全て同じであるグラフである。生成部分グラフとも呼ばれる。
- ^ Diestel, Reinhard (2006), Graph Theory, Graduate texts in mathematics, 173, Springer-Verlag, pp. 3–4, ISBN 9783540261834
- ^ Howorka, Edward (1977), “A characterization of distance-hereditary graphs”, The Quarterly Journal of Mathematics. Oxford. Second Series 28 (112): 417–420, doi:10.1093/qmath/28.4.417, MR0485544
- ^ Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006), “The strong perfect graph theorem”, Annals of Mathematics 164 (1): 51–229, arXiv:math/0212070, doi:10.4007/annals.2006.164.51, MR2233847
- ^ Johnson, David S. (1985), “The NP-completeness column: an ongoing guide”, Journal of Algorithms 6 (3): 434–451, doi:10.1016/0196-6774(85)90012-4, MR800733
[続きの解説]
「誘導部分グラフ」の続きの解説一覧
- 1 誘導部分グラフとは
- 2 誘導部分グラフの概要
- 誘導部分グラフのページへのリンク
