5

たとえば、グラフG =（V、E）があるとします。

V = {A、B、C、D}
E = {（A、B）、（A、D）、（C、D）}

このグラフは2部グラフであるため、2つの互いに素なセット{A、C}と{B、D}に分割できます。私の最初の推測は、グラフを歩き、各頂点に交互の色を割り当てることができるということです。これは事実ですか、それともこれよりも複雑/単純ですか？このための既知のアルゴリズムはありますか？

4

6 に答える 6

5

あなたの最初の推測は正しいです-グラフをトラバースして交互に。

アルゴリズムは単純でなければなりません。各色に1つずつ、訪問するノードの2つのキューを保持します。ノードをキューから交互にポップし、その色をマークし、訪問していない隣接ノードを反対の色でキューにプッシュします。訪問したノードの数+両方のキューの長さ=グラフ内のノードの数で終了します。

于 2009-10-31T18:26:45.827 に答える
2

グラフをトラバースして交互に表示します。成功しない場合は、グラフが2部グラフではないことを意味します。

于 2009-10-31T18:57:43.837 に答える
2

ウィキペディアから ( http://en.wikipedia.org/wiki/Bipartite_graph )

二部グラフが接続されている場合、その二分割は、任意に選択された頂点 v からの距離のパリティによって定義できます。一方のサブセットは、v までの距離が偶数の頂点で構成され、もう一方のサブセットは、v から奇数の距離にある頂点で構成されます。

したがって、このパリティ手法を使用して、グラフの各接続コンポーネント内で別々に 2 つのサブセット U と V に頂点を割り当てることにより、グラフが 2 部であるかどうかを効率的にテストし、次に各エッジを調べて、異なるエッジに割り当てられた端点があることを確認できます。サブセット。

于 2009-10-31T18:33:06.383 に答える
1

グラフが2分割されていることが確実な場合は、次のように、各頂点をトラバースするために色を交互に割り当てることができます。

グラフは、2色である場合に限り、2部グラフになります。

于 2009-10-31T18:30:42.113 に答える
1

グラフ描画ツールに実装しました。私のコードを JavaScript で見ることができます。

最初の頂点を左パーティとしてマークし、再帰的にその隣人を右パーティとしてマークし、再帰的にその隣人を左パーティとしてマークしました...正しくマークされたノードが見つかったら、このブランチの再帰を停止します。正しくマークされていないノードが見つかった場合、グラフは 2 部構成ではありません。

もっと簡単にできるかもしれませんが、ここ数か月、Prolog と Haskell のコーディングに苦労しました。脳に影響を与えたのかもしれませんが、今ではすべてに再帰が見られます :-D

于 2011-10-04T11:08:54.567 に答える
0

誰かが興味を持っている場合に備えて、私が思いついたコードは次のとおりです。

def dfs(root, colorings):
    to_visit1 = deque()
    to_visit2 = deque()
    to_visit1.append(root)
    while len(to_visit1) != 0 or len(to_visit2) != 0:
        dfs_color(to_visit1, to_visit2, True, colorings)
        dfs_color(to_visit2, to_visit1, False, colorings)

def dfs_color(queue, opposite_queue, color, colorings):
    while len(queue) != 0:
    v = queue.pop()
    if v in adjacency_list:
        colorings[v] = color
        neighbors = adjacency_list[v]
        del adjacency_list[v]
        for neighbor in neighbors:
        opposite_queue.append(neighbor)

確かに、これは私の最高のコードではありません。True色に/を使っているFalseのは、再帰を使うと と言いやすくなったからnot colorです。もちろん、より大きなグラフでスタックを吹き飛ばしたため、変更する必要がありました。また、当然のことながら、このコードはDFSのウィキペディア コードに基づいています。

指摘されているように、これは単に偽装された BFS である可能性があると思います。

于 2009-11-01T13:24:00.387 に答える