仮区間グラフ

ウィキペディア小見出し辞書

仮区間グラフ（広義区間グラフ）

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

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

区間グラフが p 個の例外区間を除き、他の区間を被覆する区間を持たない場合、p-仮区間グラフと呼ぶ。この表記では、真区間グラフは 0-仮区間グラフである図では、A, C, Dが他の区間を被覆し、この3つ以外は真区間グラフを満たすため、3-仮区間グラフである。