確定圖是否單獨連接

Question

我的疑問很小。如果一個圖形有後邊緣，它是單獨連接還是不連接？背後邊緣指的是從同一個根下的子節點到其祖先之一的連接。如果一個節點連接到一個高於它的節點，而不是它的祖先，那麼它就是一個交叉節點。 http://en.wikipedia.org/wiki/Polytree

更新：該鏈接澄清單獨連接的圖形的概念。

Answer 1

好問題。如果圖形具有後邊緣，則不會阻止其單連接。但由於其他原因，它可能不是單連接的。例如，如果圖形是無向的。

Answer 2

看來你正在試圖與鏈表（與通常的含義，其中單連接和雙連接的是常見的術語）的比喻。

然而，這並不是什麼大不了的圖形和術語連接更通常可達相關（即：有沒有從節點到另一個節點的路徑？）

Answer 3

如果我沒有理解你問題正確，你想知道Polytree是否可以包含後沿（從節點到其祖先之一的邊）。

從您鏈接到維基百科的文章，一個Polytree是DAG剩下的即使邊緣是由無向樹。如果有向圖包含後沿，則意味着圖中會出現一個循環（可以從其祖先到達該節點，然後使用後沿返回祖先）。因此它不再是一個DAG，更不用說樹了。如果不是DAG，它不能是Polytree。所以，沒有一個Polytree不能有一個後端。