|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ ラフ : [らふ] 1. (adj,n) rough 2. (adj,n) rough
補グラフ(ほグラフ、)は、グラフ理論の用語。グラフ にとっての補グラフとは、 において隣接している頂点が補グラフでは必ず隣接していないことと同値である。したがって、あるグラフの補グラフを作成するには、そのグラフの存在しない辺を全て描き、既存の辺を全て消去すればよい。グラフの差集合とは異なり、辺だけが相補的である。 == 形式的構築 == 頂点群 と辺群 のグラフ があるとき、その補グラフ は以下のように構築される。 * である。 * 個の頂点のクリーク について、 とする。 補グラフは、ラムゼー理論などのグラフ理論で使われ、NP完全問題であることの証明にも使われる。 抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)』 ■ウィキペディアで「補グラフ」の詳細全文を読む スポンサード リンク
|