algorithm - グラフが単結合かどうかを判断するにはどうすればよいですか?

Question

グラフにバック エッジがある場合、それは単結合かどうか? バック エッジとは、同じルートの下で、子ノードからその先祖の 1 つへの接続を意味します。ノードがそれよりも上位のノードに接続されているが、その祖先には接続されていない場合、それはクロス ノードです。

http://en.wikipedia.org/wiki/Polytree

このリンクは、単結合グラフの概念を明確にします。

Answer 1

グラフにバック エッジがある場合でも、グラフが単結合であることは妨げられません。しかし、他の理由で単独接続されていない可能性があります。たとえば、グラフが無向の場合です。

Answer 2

あなたはリンクリストとのアナロジーを作ろうとしているようです（ここで、単一接続と二重接続は通常の意味を持つ一般的な用語です）。

ただし、これはグラフにとって大きな問題ではなく、接続性という用語は通常、到達可能性に関連付けられています（つまり、ノードから別のノードへのパスはありますか？）

Answer 3

私があなたの質問を正しく理解しているなら、あなたはポリツリーがバックエッジ（ノードからその祖先の1つへのエッジ）を含むことができるかどうか知りたいです。

リンクしたウィキペディアの記事によると、ポリツリーは、エッジが無向にされてもツリーのままであるDAGです。有向グラフにバックエッジが含まれている場合は、グラフにサイクルがあることを意味します（ノードにその祖先から到達し、バックエッジを使用して祖先に戻ることができます）。したがって、ツリーは言うまでもなく、DAGではなくなります。DAGでない場合は、ポリツリーにすることはできません。したがって、ポリツリーにバックエッジを設定することはできません。