0

無向かつ無加重 (またはすべてのエッジの加重が 1) の非巡回グラフ (G=VxE) があります。このグラフのノードのいくつかは sV (sV は V のサブセット) として選択されます。問題は、選択したすべてのノードをカバーするサブグラフを見つけたいということです。当然ながら、選択されていないノードをカバーすることもできます。ただし、目的のサブグラフにないノードは制限されます。これらの制限されたノードは、選択した 2 つのノード間の 1 つのパス上にある場合を除き、ソリューション サブグラフに含めるべきではありません。例：

  A B C D
A - + + -
B + - + -
C + + - +
D - - + -

A、B、C、D はノード、+ はエッジの包含を表します。このグラフでは、B と D が選択されたノードです。この例に必要なソリューションは次のとおりです。サブグラフは、ノード B、C、D とエッジ (B、C)、(C、D) * で構成されます。A は意図したとおりにサブグラフに含まれていないことに注意してください。このタイプのサブグラフを見つけるには、どのようなアプローチが役立ちますか? アイデアをありがとう。

*(X,Y) は、ノード X と Y の間のエッジを表します。

4

2 に答える 2

0

問題を誤解しているような気がしますが、やってみようと思います。

まず、グラフが連結成分http://en.wikipedia.org/wiki/Connected_component_(graph_theory）であると想定/確認する必要があります。次に、次の手順を開始できます。

solution = sV
foreach n1 in sv
    foreach n2 in sv, n2!=n1
        path = findPath(G,n1,n2)  
        // this should return at least one path because of connectivity
        // and no more than one
        for each n3 in path
            solution += n3

それはあなたがやりたいことを実行しますか？

于 2012-01-11T12:15:06.567 に答える
0

もう 1 つのアプローチは、よりツリー指向です (ツリーは非循環接続グラフであるため)。

グラフをツリーとして構造化したとしましょう。

  • ルート r
  • ノードから、その息子とその親 (存在する場合) を取得する方法

また、利便性を高めるために、ノード (ノード/グラフ/ツリー自体または側面の別の構造) にマーカーを追加できると仮定しました。

次に、次のことが簡単にできます。

  • sv にある子孫の数を示すすべてのノードにマーカーを追加します (これは、sv のさまざまな要素から開始してツリーを上ることによって実行できます (ツリーのルートに遭遇すると中断します))

  • ノード n から開始:

    retrieve the sons with a number greater or equal to 1 # other sons are useless

if there's no son with this property :
        stop
else if there's only son s with this property :
        if n is in nv
                add s to sv # s is needed to go to n
else if there's many sons with this property :
        add n to sv # n is needed to join descendant of different branches
foreach each son s
        start again from s

あまり考えたことがありませんが、これならいけそうな気がします。

于 2012-01-11T14:46:49.553 に答える