サイクルがある場合とない場合がある、重み付けされていない有向グラフがあります。ノードのセットが与えられたので、与えられたノードとそれらが接続されるような最小量のノードを持つグラフを返す必要があります。新しいエッジを作成できないため、既存のエッジを使用する必要があります。
うまくいけば、これらの写真はそれを明確にします。グラフから始まり、
ノードc、f、およびgを持つグラフが必要だとしましょう。関数はこのグラフを返します
ただし、もう1つ条件があります。各エッジには、必須と呼ばれるブール変数があります。これが true に設定されている場合、このエッジと対応するノードもグラフに含める必要があります。
説明する別の図を次に示します。黒いエッジは必要ありませんが、赤いエッジは必要です。含めるノードとして a と c が与えられたとします。
したがって、A->C であるグラフを返す代わりに、これを返します。
要点をさらに明確にするために、b と c を含むグラフが必要な場合、そのエッジが必要であるため、そのグラフも返されます。
このグラフを返すにはどうすればよいでしょうか? 循環を含むグラフが返されないようにしたいのですが、循環のエッジがすべて必要としてマークされている可能性があるため、常に可能であるとは限りません。
私が最初に考えたのは、必要なエッジを維持したままグラフのコピーを作成し、ばらばらなグラフをつなぎ合わせようとすることでした。しかし、グラフをつなぎ合わせようとするすべての試みの間に、最小のグラフではないことを示す反例を見つけることができました。