頂点被覆と支配集合の違いを理解しようとしています。
理解していることから、支配集合では、集合Dには、Dにない他の頂点に隣接する頂点が含まれます（Vのすべてのvについて、vはDにあるか、Dの頂点に隣接しています）。
頂点被覆では、Dのすべての頂点がすべてのエッジをカバーしますが、それを行うことにより、それらはDにない他の頂点に隣接します-では、なぜそれが支配集合ではないのですか？
質問する
20621 次
9 に答える
38
ウィキペディアの支配集合の記事で、この違いを説明するグラフをいくつか見つけました。
これらの例は、頂点被覆ではない支配集合（赤）を示しています。これは、後で質問したものとは逆です。（VD）のエッジは、それらが頂点被覆になるのを防ぎます。
于 2013-01-30T00:52:21.947 に答える
36
以前の回答は良いですが、最も単純な例はまだここに書かれていないので:
于 2016-01-28T14:56:16.237 に答える
3
2 つの概念を区別するには、4 つの頂点上のパスを考慮する必要があるだけです。a、b、c、d をそのようなパスの連続する頂点とします。その場合、{a,d} は支配集合ですが、頂点カバーではありません (エッジ bc をカバーできないため)。
于 2013-11-08T21:59:40.930 に答える
1
すべての頂点カバーは支配的なセットですが、その逆は当てはまりません。たとえば、グラフ G=(V,E) G={a,b,c,d,e} および E={(a,b),(b,c),(c,d),( e,a),(e,b)} の場合、支配集合 DS={b,e} は G の頂点カバーではありません。エッジ (c,d) はカバーされていません。
于 2013-12-04T17:39:10.983 に答える
0
頂点カバー:任意の通路 (エッジ) に目を向けるポリシーと考えることができます。これにより、ノードは関係ないため、孤立したノードを除くすべてのノードに目を向けることができます。それらはすべての節をカバーする必要があります。
支配的なセット:これらは、任意のノードに目を向けるポリシーです。パッセージは重要ではないため、それらの 1 つがエッジを介してノードを監視する場合、パッセージはこれらのポリシーの対象ではないため、そのノードに接続されている他のエッジはカバーされない可能性があります。
この回答の画像を確認してください https://stackoverflow.com/a/14594930/2651073
于 2018-12-02T19:33:19.967 に答える