翻訳と辞書 Words near each other ・ 裙帯菜 ・ 裙蔕菜 ・ 裚 ・ 裛 ・ 補 ・ 補(佐)薬 ・ 補(体)結(合)抗体 ・ 補い ・ 補う ・ 補てつ(綴)、人工 ・ 補グラフ ・ 補中益気湯 ・ 補任 ・ 補任帳 ・ 補任状 ・ 補佐 ・ 補佐司教 ・ 補佐官 ・ 補佐役 ・ 補佐薬 Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク 補グラフ ： ウィキペディア日本語版 補グラフ[ほぐらふ] 補グラフ（ほグラフ、）は、グラフ理論の用語。グラフ $H$ にとっての補グラフとは、$H$ において隣接している頂点が補グラフでは必ず隣接していないことと同値である。したがって、あるグラフの補グラフを作成するには、そのグラフの存在しない辺を全て描き、既存の辺を全て消去すればよい。グラフの差集合とは異なり、辺だけが相補的である。 == 形式的構築 == 頂点群 $V\_G$ と辺群 $E\_G$ のグラフ $G(V\_G,\; E\_G)$ があるとき、その補グラフ $H(V\_H,\; E\_H)$ は以下のように構築される。 * $V\_H\; =\; V\_G$ である。 * $n\; =\; |V\_G|$ 個の頂点のクリーク $K^n(V\_K,\; E\_K)$ について、$E\_H\; =\; E\_K\; \backslash setminus\; E\_G$ とする。 補グラフは、ラムゼー理論などのグラフ理論で使われ、NP完全問題であることの証明にも使われる。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「補グラフ」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.