15

G = (V,E) を無向グラフとします。エッジのセット F ⊆ E は 、G のすべてのサイクルが F に少なくとも 1 つのエッジを持つ場合、フィードバック エッジ セットと呼ばれます。

(a) G が重み付けされていないと仮定します。最小サイズのフィードバック エッジ セットを見つける効率的なアルゴリズムを設計します。

(b) G が正の辺の重みを持つ重み付き無向グラフであるとします。最小重みフィードバック エッジ セットを見つけるための効率的なアルゴリズムを設計します。

私の解決策（提案が必要）：

a)最小サイズのフィードバック エッジ セット:グラフは重み付けされていないため、DFS を使用できます。通常どおり、任意の頂点から DFS を開始します。バック エッジに遭遇すると、それをフィードバック エッジのセットに挿入します。DFSが完了すると、セットが答えになります。

b)最小重みフィードバック エッジ セット:グラフが重み付けされているため、Kruskal を使用できます。しかし、クラスカルは通常、ウェイトが最も小さいエッジから始めます。すべての辺の重みを無効にしてから Kruskal を実行できれば、同じコンポーネントの頂点間の辺を取得するたびに、それをフィードバック エッジ セットに保存できます。最後に、エッジの重みを無効にします。エッジの重みを無効にすることを提案する理由は、最小の重みフィードバック セットが必要だからです。負の重みを使用すると、Kruskal は重みが最小 (実際には最大) のエッジから開始し、重みが小さい同じコンポーネントのエッジを見つけます。

この解決策が正しいかどうかを誰かが知ることができますか?

4

5 に答える 5

5

はい、あなたの解決策は正しいです。無向グラフの最小重みフィードバック エッジ セットは、最大重みスパニング フォレストを補完します。すべてのスパニング フォレストのカーディナリティは同じであるため、重み付けされていない場合は、(DFS によって検出された) 任意のスパニング フォレストで十分です。(証明スケッチ: マトロイド)

フィードバックアークセットは確かに NP 困難ですが、これは無向の場合です。

于 2012-05-30T15:14:29.537 に答える
4

正の重みを持つ重み付き有向グラフで最小重みフィードバック エッジ セットを見つけるには、次のようにします。

重みを否定することで、最大重みフィードバック エッジ セットを見つけることと同等であることに注意してください。最大重みフィードバック エッジ セットを見つけるには、Prim または Kruskal のアルゴリズムを使用して MST を構築します。次に、その MST の補数を取ります。

なぜそれが機能するのですか？これは、次の観察に基づいています。

そのエッジが、そのサイクル内の他のすべてのエッジよりも最大の重みを持つサイクルが存在する場合にのみ、そのエッジは MST に含まれません。 または、言い換えれば、そのエッジが属するすべてのサイクルについて、そのサイクルの他のすべてのエッジに対して最大の重みを持たない場合にのみ、そのエッジは MST に含まれます。

実際、最大重みのフィードバック エッジ セットがあると仮定すると、そのエッジと別のエッジを含むサイクルが存在するようなエッジが存在し、そのエッジをこの別のエッジに置き換えると、より大きな重みのフィードバック エッジ セットが提供されます。

完全を期すために、観察の証明：

<=) エッジがサイクル内で最大の重みを持つとします。ある MST にある場合、そのエッジをそのサイクルの別のエッジに置き換えると、MST の重みが小さくなります。

=>) 与えられたエッジが属するすべてのサイクルについて、そのサイクル内により大きな重みを持つエッジが存在すると仮定します。それがどの MST にもない場合、そのエッジを MST に追加すると、MST でサイクルが発生します。次に、そのサイクルから最大重みのエッジ (指定されたエッジとは異なります) を削除すると、MST の重みが小さくなります (そのエッジを構成します)。

于 2014-05-20T21:19:46.760 に答える
1

どちらの問題も NP 完全です。したがって、おおよその効率的な (多項式時間) ソリューションでさえ存在しそうにありません (http://en.wikipedia.org/wiki/Feedback_arc_set)。

アプリケーションの厳密な最小ソリューション サイズの要件を緩和できる場合は、他のヒューリスティックを使用できますが、それらを相互に比較するのは難しい場合があります。

最小の (最小ではない) ソリューションを簡単に見つけることができることに注意してください。任意の順序で設定されたフィードバック エッジのエッジを通過し、冗長な場合はすぐに削除します。すべてのエッジを 1 回掃引するだけで十分であり、DFS などを使用して冗長性テストを実行します。

于 2012-05-30T07:26:47.967 に答える
0

フィードバック エッジの場合、このグラフの補数は、元のグラフのスパニング フォレストでなければなりません。これは、補グラフにはサイクルが含まれていないことを示しており、これは非常に明白です。

問題 a):
最小サイズのフィードバック エッジ セットの場合、これはフォレストにまたがる最大サイズを見つけることと同じです。したがって、単純に DFS を使用して、グラフの各連結コンポーネントのスパニング ツリーを見つけ、補数を取ることができます。次に、最小サイズのフィードバック エッジを取得します。実際には、接続されたコンポーネントごとにスパニング ツリーを見つけることができる限り、DFS は必要ないと思います。
問題 b):
最小重みフィードバック エッジ セットを見つけることは、フォレストにまたがる最大重みを見つけることと同じです。次に、Kruskal アルゴリズムまたは Prim のアルゴリズムを使用して、各連結要素の最大スパニング ツリーを見つけることができます。次に、補数を取ると、最小の重みフィードバック セットが得られます。

于 2016-11-04T12:21:47.597 に答える
-2

ソリューション A) は機能しません。これは、エッジに「戻る」プロパティがあるかどうかを判断するロジックが提供されていないためです。

Kruskal はフィードバック セットを探すのではなく、最小加重被覆ツリーを探すため、ソリューション B) は機能しません。最小加重ツリーに必ずしもフィードバック エッジ セットが含まれない理由の良い例は、K4 グラフです。

于 2012-05-29T11:13:54.693 に答える