3

次の宿題の質問があります: DAG: 線形時間アルゴリズム ( O(|E|+|V|)) を設計して、DAG に他のすべての頂点から到達可能な頂点があるかどうかを判断し、ある場合はそれを見つけます。

この問題を解決するための私のアプローチは次のとおりです。 -> まず、トポロジー順序で最後に来る頂点を見つけます (V と呼びます)。

->次に、逆グラフのすべての頂点がこの頂点 V から到達可能かどうかを判断します。

-> すべての頂点に到達可能な場合、頂点 V が必要な頂点です。それ以外の場合、他のすべての頂点から到達可能なグラフ内の頂点はありません。

このアプローチは正しいですか？

PS。この質問の解決策のヒントは、各頂点の出次数を計算する必要があることを示しています。しかし、出次数の計算がどのように役立つか理解できません。

4

3 に答える 3

2

解決策は、すべての頂点の出力次数を計算して、1 つのシンク頂点 (出力次数が 0 の頂点) があるかどうかを確認することです。これが証明です。

ステートメント: DAG には、出角度が 0 の単一の頂点が 1 つある場合にのみ、他のすべての頂点から到達可能な頂点があります。

このステートメントは、2 つのステップで証明できます。

必要性の証明: DAG に他のすべての頂点から到達可能な頂点 u が含まれている場合、それは唯一のシンク頂点 (出次数が 0 の頂点) でなければなりません。

  • u は出次数が 0 であり、それ以外の場合は循環形式であり、DAG に矛盾します。
  • 出次数が 0 の別のシンク頂点 v は存在できません。そうでない場合、v から u に到達できません。

証明された。

十分性の証明: DAG に 1 つのシンク頂点 u が含まれている場合、u は他のすべての頂点から到達可能である必要があります。

u に到達できない頂点が DAG に存在すると仮定します。DAG 内のすべての頂点を、u に到達できる頂点のセット ($V_y$) と u に到達できない頂点のセット ($V_n$) に分割すると、$V_n$ の頂点からのエッジは存在しません。 $V_y$。

補題: どの DAG にも、少なくとも 1 つのシンク頂点が含まれている必要があります。

これは矛盾によって簡単に証明できます。DAG 内のすべての頂点の出度がゼロでないと仮定すると、1 つの頂点から始めて、各頂点の出て行くエッジに沿って移動し続けることができます。DAG には有限数の頂点が含まれているため、最終的には以前に訪れた頂点に戻ります。つまり、サイクルが検出され、DAG の定義に反します。

$V_n$ の頂点とそれらの間のエッジによって形成されるグラフを考えてみましょう。これも DAG である必要があります。そうでない場合、元のグラフは DAG になることはできません。v がこのサブ DAG のシンク頂点であると仮定すると、v には $V_n$ の頂点を指す出力エッジがありません。

前述のように、v から $V_y$ 内の頂点を指すエッジも存在できません。そうでない場合、v は u に到達できます。

したがって、元の DAG の v の全体的な出次数も 0 であり、DAG に単一のシンク頂点が含まれるという仮定に矛盾します。証明された。

于 2019-10-29T20:43:08.970 に答える
1

ヒントとして、通常の定義を使用して、DAG をソース ノード (indegree 0)、中間ノード、およびシンク ノード (outdegree 0) に分割できることを考慮してください。

DAG にそのようなノード (他のすべての頂点から到達可能) が含まれている場合、どのタイプのノードになりますか?

出次数 0 の 2 つのノードを持ち、すべての頂点から 1 つの頂点に到達できるグラフの例を描画します。

于 2013-03-30T08:09:54.653 に答える