0

I am not asking an algorithm, I am asking definitions.

There is this question: given a graph to detect if it is a tree or not in directed and undirected graphs? According to the selected answer, I came up with the following:

For a directed graph to be a valid tree, it must satisfy all the facts:

  1. The graph must have only 1 vertex that has purely outgoing edges.
  2. The graph is connected.
  3. The undirected version of this graph has no cycles.

I searched online for this and seems like most people agree with these points.

However I am still confused. For example, are the following graphs valid trees?:

G1:

Directed graph with 2 source vertex

G2:

Directed graph with 2 source vertex_2

If yes, why? If no, why?

Any help is appreciated! Thanks!

Community
  • 1
  • 1
HeyThere
  • 503
  • 1
  • 5
  • 19

1 Answers1

0

In case Directed graph, we start from vertex which has outgoing edge. When we have done traversal and is there any unvisited vertex then it is not tree.
For graph G1,
We can start from A, B or C.
If we start from A, then there is no chance to visit B. A->C, C->D or C->E.
If we start from B, then there is no chance to visit A. B->C, C->D or C->E.
And same for C, no chance to visit A and B.
It means there is no way to visit each vertex, so it's not a tree - graph is not connected.
For graph G2,
We can start from A or B.
If we start from A, then there is no chance to visit B and D.
Same case for B.
Therefore, this graph is also not connected.

Gaurav Sharma
  • 573
  • 1
  • 4
  • 26