真区間グラフとは？ わかりやすく解説

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/03/06 10:20 UTC 版)

「区間グラフ」の記事における「真区間グラフ（狭義区間グラフ）」の解説

真区間グラフは、被覆するような区間が存在しない区間グラフを指す。図は区間Bが区間Aに被覆され、区間Eは区間Dに、そして更に区間Dは区間Cに被覆されているため、真区間グラフではない。単位区間グラフはすべての区間が長さ1であるような区間グラフである。同一区間を持たない単位区間グラフは、真区間グラフである。真区間グラフが常に単位区間グラフであるわけではないが、単位区間グラフは真区間グラフである。真区間グラフは、クローフリーグラフであり、真区間グラフはクローフリー区間グラフである。しかし、区間グラフではないクローフリーグラフも存在する。 区間グラフが、 q 個の例外区間を除き、他の区間に被覆される区間を持たない場合、q-真区間グラフであると呼ぶ。この表記では、真区間グラフは 0-真区間グラフである。図では、B, D, Eの3つが被覆されており、この3つ以外は真区間グラフを満たすため、3-真区間グラフである。

※この「真区間グラフ（狭義区間グラフ）」の解説は、「区間グラフ」の解説の一部です。
「真区間グラフ（狭義区間グラフ）」を含む「区間グラフ」の記事については、「区間グラフ」の概要を参照ください。