補グラフ

ウィキペディア

補グラフ

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/05/24 19:13 UTC 版)

補グラフ（ほグラフ、英: complement graph）は、グラフ理論の用語。グラフ $H$ にとっての補グラフとは、$H$ において隣接している頂点が補グラフでは必ず隣接していないことと同値である。したがって、あるグラフの補グラフを作成するには、そのグラフの存在しない辺を全て描き、既存の辺を全て消去すればよい。グラフの差集合とは異なり、辺だけが相補的である。