graph - Unique Topological Sort を使用したグラフの前提条件

Question

問題のグラフが DAG (有向非巡回グラフ) であると仮定しましょう。

質問: その頂点の 1 つだけに着信エッジがない場合にのみ、そのようなグラフが一意のトポロジカル ソートを持つと結論付けてよいでしょうか?

言い換えれば、一意のトポロジカル ソートを生成するために必要な (しかし十分ではない) 入ってくるエッジのない 1 つの頂点しかないのでしょうか?

Answer 1

トポロジー順序で連続する頂点の各ペアの間に有向辺がある場合 (つまり、有向グラフがハミルトン パスを持っている場合) にのみ、トポロジー ソートは一意になります。 ソース

ハミルトニアン パスは、2 つの頂点間のパスが各頂点を 1 回だけ訪れることを意味しますが、1 つの頂点に着信エッジがあってはならないという意味ではありません。実際にはサイクルであるハミルトニアン パスを持つことができます。これでも、一意のトポロジー ソートが生成されます (もちろん、それが重要な場合はサイクルでもあります)。

お役に立てれば

Answer 2

はあああああ。誤解してすみません。

この場合、私はあなたが正しいと仮定します。ここに証明のスケッチがあります:

独自のトポロジーソートがあります => 最初に配置することが合法な頂点は1つだけです => 1つを除くすべての頂点について、最初に配置することは合法ではありません => 1つを除くすべての頂点について、入力エッジがあります。

今私があなたの質問に答えたことを願っています....

Answer 3

はい、必要条件として、in-degree = 0 のノードが複数ある場合、ハミルトニアン パスは存在しないため、一意のトポロジー順序は存在しないと言えます。グラフの開始ノード (in-degree=0) のみが着信エッジを持たず、残りのすべての頂点は、トポロジーの祖先からの着信エッジを持っている必要があります。これは、トポロジー順序で現在のノードの直前のノードを意味します。トポロジー順序付けの連続するすべてのノードにエッジがない場合、DAG には一意の順序がありません。