I Number of edges in a tree digraph

[CGandC]

I know that if an undirected graph is a tree then its number of edges satisfies $|E| = |V| - 1$.
If a directed graph ( digraph ) is a tree, is the result also true? ( I can imagine just taking an undirected tree and making its edges directed but this is specious since it's a little bit more delicate - the digraph that will result will not necessarily be connected, the direction of the edges matter and the definition of what is a 'tree' for digraph needs to be clearly defined )

I haven't seen any discussion about this in discrete mathematics books I have nor directly written on the web ( tree digraph is called 'polytree' from what I've read )

 

[FactChecker]

I have no reason to think that there is a difference in the edge count just because some edges are directed.

 

[Office_Shredder]

What exactly is the definition of a tree for a directed graph? For an undirected graph there are several equivalent definitions (no loops, unique path between vertices) that are not equivalent for directed graphs (e.g. it's easy to make a triangle with no loops but two paths between a pair of vertices)

 

[CGandC]

Well, the reason I'm asking is because I've been reading about Breadth-first trees from CLRS ( a book about algorithms ) in chapter 20 where they're define as:

where $\pi$ is a function ( whose definition depends on the given graph and source vertex for the BFS algorithm ) "attaching" attributes for the vertices of the graph and $v.\pi$ means the predecessor ( parent ) node of $v$

( Source: Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. )According to the definition of BFS tree $E_\pi$ is composed of directed edges if the graph $G$ itself is directed, but I don't understand how he applies theorem $B.2$ ( which is for undirected graphs ) for $G_\pi$ ( which can be directed ) since a tree for a directed graph is not defined anywhere.

How to solve this predicament in definitions?

 

[SSequence]

If we have a finite directed or non-directed graph, then here is one way to proceed I think. If the number of nodes is $n$ then we can label them from $1$ to $n-1$. The node $1$ is essentially the "base node" so to speak (the node at the top of the tree). Next we check whether we can reach all possible points from the base node [this is assuming we necessarily want a single tree as a result]. After that we can use breadth first search starting from node $1$.

There are no loops in the resulting tree. And also, starting from the base node, there is always a unique path to every other node. However, one thing here that isn't clear to me is that if we don't have a number attached to the nodes [that is, a way of giving priority one node over the other] then how could we get a unique tree. If all the nodes are numbered then we definitely seem to get a unique tree.

=================================================

The above I wrote before the last post, but didn't post it since I thought it might not be relevant to the topic. Since it seems relevant to some extent, I am posting it. What I was trying to say was that as long as:
(1) All the nodes in our directed graph are reachable from source node.
(2) We number all all the nodes from $1$ to $n$, with $1$ being number of the source node.

Then given the above two conditions there definitely seems to be a way to form a unique tree using breadth-first search.

=================================================

Regarding what has been quoted from the book, it would be a bit difficult to comment (without reading/understanding it in detail) since I only know the very basic of this particular topic.

 

[CGandC]

If we have a finite directed or non-directed graph, then here is one way to proceed I think. If the number of nodes is $n$ then we can label them from $1$ to $n-1$. The node $1$ is essentially the "base node" so to speak (the node at the top of the tree). Next we check whether we can reach all possible points from the base node [this is assuming we necessarily want a single tree as a result]. After that we can use breadth first search starting from node $1$.

There are no loops in the resulting tree. And also, starting from the base node, there is always a unique path to every other node. However, one thing here that isn't clear to me is that if we don't have a number attached to the nodes [that is, a way of giving priority one node over the other] then how could we get a unique tree. If all the nodes are numbered then we definitely seem to get a unique tree.

=================================================

The above I wrote before the last post, but didn't post it since I thought it might not be relevant to the topic. Since it seems relevant to some extent, I am posting it. What I was trying to say was that as long as:
(1) All the nodes in our directed graph are reachable from source node.
(2) We number all all the nodes from $1$ to $n$, with $1$ being number of the source node.

Then given the above two conditions there definitely seems to be a way to form a unique tree using breadth-first search.

=================================================

Regarding what has been quoted from the book, it would be a bit difficult to comment (without reading/understanding it in detail) since I only know the very basic of this particular topic.

Thanks! makes sense now. And you're right, if you give some priority for some nodes to be scanned before others then the resulting BFS tree will be different; I think the authors meant that for a specific scan over all the vertices in the graph given a source vertex, then there will be a corresponding predecessor subgraph $G_\pi$ and for that graph itself there is a unique simple path from the source vertex to every other vertex in the graph