How do I determine whether a graph is singly connected or not?

If a graph has back edges, is it singly connected or not? By back edges I mean connections from child node to one of its ancestors, under the same root. If a node is connected 开发者_StackOverflowto a node higher than it, but not its ancestor, then it's a cross node.

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

This link clarifies the concept of singly connected graph.

---

If a graph has back edges, that doesn't prevent it from being singly-connected. But it might not be singly-connected for other reasons. For example, if the graph is undirected.

---

It seems that you are trying to make an analogy with linked lists (where singly-connected and doubly-connected are common terms with an usual meaning).

However, this isn't a big deal for graphs, and the term connectivity is more usually associated with reachability (ie.: is there a path from a node to another?)

---

If I understand you question correctly, you want to know whether a Polytree can contain back edges (edges from a node to one of its ancestors).

From the wikipedia article you linked to, a Polytree is a DAG that remains a tree even if the edges are made undirected. If a directed graph contained back edges, it would mean there would be a cycle in the graph (you can reach the node from its ancestor and then go back to the ancestor using the back edge). Thus it would no longer be a DAG, let alone a tree. If it isn;t a DAG, it cannot be a Polytree. So, no a Polytree cannot have a back edge.