エントリーの編集

エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
記事へのコメント0件
- 注目コメント
- 新着コメント
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています

- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
グラフの同型性判定
説明 二つのグラフ g, h に対して同型すなわち頂点の置換 p であって (u,v) ∈ E(g) iff (p[u], p[v]) ∈ ... 説明 二つのグラフ g, h に対して同型すなわち頂点の置換 p であって (u,v) ∈ E(g) iff (p[u], p[v]) ∈ E(h) なるものが存在するかどうかを判定する. 今のところこの問題は NP 完全かどうかすらわかっていない(多くの人は NP 完全ではないが P でもないと信じていると思う).しかしバックトラックによる枝刈り付の全探索が多くの場合うまくいくことが実験によって分かっており,ランダムグラフに対しては O(V log V) で動くことも知られている. 以下の実装は次のアルゴリズムによる. g, h の頂点を次数の小さい順にソートする. 同じ次数のものに対して頂点を対応させてみる. それまでに対応を作った部分と整合性を確かめる. 整合していれば再帰的にチェックする. 計算量 最悪 O(V!).しかしランダムグラフを入力とした実験によると,V = 1000 く