21

G (U u V, E) を加重有向 2 部グラフとする (つまり、U と V は 2 部グラフのノードの 2 つのセットであり、E は U から V または V から U への有向加重エッジを含む)。以下に例を示します。

二部有向加重グラフ

この場合：

U = {A,B,C} 
V = {D,E,F} 
E = {(A->E,7), (B->D,1), (C->E,3), (F->A,9)}

定義: DirectionalMatching (わかりやすくするためにこの用語を作りました): 開始頂点または終了頂点を共有する有向エッジのセット。つまり、U->V と U'->V' の両方がDirectionalMatchingに属している場合、V /= U' および V' /= U ですが、U = U' または V = V' である可能性があります。

私の質問:上記で定義したように、エッジの重みの合計を最大化する二部方向加重グラフのDirectionalMatchingを効率的に見つける方法は?

効率的とは、多項式の複雑さまたはより高速であることを意味し、単純なブルートフォースアプローチを実装する方法をすでに知っています。

上記の例では、重み付けされた最大のDirectionalMatchingは {F->A,C->E,B->D} で、値は 13 です。

この問題がグラフ理論の他のよく知られている問題と同等であることを正式に示すことも価値があります。

ありがとう！

注 1: この質問は、最大加重二部マッチング _with_ 有向エッジに基づいていますが、マッチングのエッジが出発地または目的地を共有することが許可されているという特別な緩和があります。そのリラックスが大きな違いを生むので、私は独立した質問を作成しました.

注2：最大重量合わせです。カーディナリティ (いくつのエッジが存在するか) とマッチングによってカバーされる頂点の数は、正しい結果には関係ありません。最大重量のみが重要です。

注2：この論文を見つけた問題を解決するための私の研究中に、解決策を見つけようとしている他の人に役立つと思います：エッジカラーのマルチグラフの交互のサイクルとパス：調査

注 3: 参考になる場合は、グラフを 2 辺の色付きの無向二部マルチグラフと見なすこともできます。問題の定式化は次のようになります。最大の重みの合計を持つ、色が変わるパスまたはサイクルのないエッジのセットを見つけます。

注 4:問題は NP 困難である可能性があると思われますが、還元の経験があまりないため、まだ証明できていません。

さらに別の例:

あなたが持っていたと想像してください

4 つの頂点:{u1, u2} {v1, v2}

4 つのエッジ:{u1->v1, u1->v2, u2->v1, v2->u2}

次に、それらの重みに関係なく、u1->v2とをv2->u2同じDirectionalMatchingにすることはできません。ただし、 およびも可能であり、 および も可能です。v2->u2u2->v1u1->v1u1->v2u1->v1u2->v1

4

2 に答える 2

10

次のように新しい無向グラフG'を定義Gします。

  1. G'重みのある有向辺ごとに(A, B)重みのあるノードを持つw(A, B)wG
  2. G'((A, B),(B, C))(A, B) と (B, C) が両方とも G の有向辺である場合、無向辺を持つ

http://en.wikipedia.org/wiki/Line_graph#Line_digraphs

で最大の (重み付けされた) 独立頂点セットを見つけますG'。

http://en.wikipedia.org/wiki/Vertex_independent_set

編集：この時点以降のものは、すべてのエッジの重みが同じ場合にのみ機能します-エッジの重みが異なる値を持つ場合、より困難な問題になります（可能なアルゴリズムについては、「最大重みに依存しない頂点セット」をグーグルで検索してください）

通常、これは NP 困難な問題になります。ただし、G'これは 2 部グラフです。偶数サイクルのみが含まれます。二部グラフで最大の (重み付けされた) 独立した頂点セットを見つけることは、NP 困難ではありません。

実行するアルゴリズムG'は次のとおりです。

  1. の連結成分を見つけますG'。たとえば、H_1, H_2, ..., H_k
  2. それぞれに対してH_i、ノードの 2 色 (赤と青など) を行います。ここでのクックブックのアプローチは、H_i交互の色に対して深さ優先検索を行うことです。簡単なアプローチは、対応するエッジがto から(赤) またはto から(青)に移動H_iするかどうかに基づいて、各頂点に色を付けることです。GUVVU
  3. 選択するノードの 2 つのオプションH_iは、すべて赤のノードまたはすべて青のノードです。重みの高い色付きのノード セットを選択します。たとえば、赤いノード セットの重みはH_i.nodes.where(node => node.color == red).sum(node => node.w)です。重みの高いノード セットを呼び出しますN_i。
  4. 最大加重独立頂点セットは現在union(N_1, N_2, ..., N_k)です。

の各頂点G'は の有向辺の 1 つに対応するため、GDirectionalMatching は最大になります。

于 2013-02-20T22:13:11.600 に答える
-2

この問題は、ハンガリーのアルゴリズムを使用して多項式時間で解決できます。上記のVorによる「証明」は間違っています。

上記の例の問題を構造化する方法は次のとおりです。

   D E F
A  # 7 9  
B  1 # #
C  # 3 #

ここで、「＃」は負の無限大を意味します。次に、ハンガリーのアルゴリズムを使用して行列を解決し、最大一致を決定します。最小の一致を見つけたい場合は、数値に-1を掛けることができます。

于 2013-02-19T19:02:25.697 に答える