Question

Give a linear-time algorithm for the following task.
Input: A directed acyclic graph G

Does G contain a directed path that touches every vertex exactly once?

Short answer

Yes, a directed acyclic graph contains a directed path that touches every vertex exactly once in linear-time.

Step-by-step solution

Step 1:

DAG (directed acyclic graph) is a graph which contain directed edges between all the vertices and they are not contain any cycle in graph. This type of graph are called directed acyclic graph.

And G contain a directed path that touches every vertex exactly once, Where G is the graph with no of vertex and edges in it.

The path that touches every vertex exactly once is known as Hamiltonion path.

This algorithm is also shown by topologically ordering the vertices in which traversing the directed acyclic graph in order to get a topological order in a way that the output in decreasing order of post number.

It is also called as backtracking approach.

This is the NP hard problem.

And the theorem is proved by topological sorting

The topological sorting is the traversing of directed acyclic graph in order to get a topological order in a way that the output in decreasing order of post number.

Some properties ofTopological sorting are as follows:

1). The topological orderings is basically a linear ordering of graph if u and v are the vertices of graph there u must be comes before v.

2). It must be a DAG (directed acyclic graph).

3). The given graph should be directed acyclic graph with no cycle.4). Every directed acyclic graph must contain at least one topological ordering.

Explanation of algorithm.

As given in the question a directed acyclic graph G contain a directed path that touches every vertex exactly once. In first step check whether the graph has cycle or not. If not then proceed for topological ordering.in the above graph it does not contain any cycle in it then proceed it to the next step.

Now find out the node with indegree zero and consider it as source vertex.

Indegree of any node is the number of edges which directs towards it.

So, here has indegree zero and also contain zero as its indegree. Now select anyone from these vertices.

Fig: Directed acyclic graph

Let as its source vertex.After selection ofselect as its next node because its indegree is. Andremoves source nodes from the graph.

So, after removing both of the vertices, it seems thathas degree and has indegree. Than select, up to here the sequence of graph is .

Than eliminate . now the degree of D and E again. Select any one from them. Select D and after that select E. Now the degree of is zero and the degree of G and H is . After selecting eliminate and again look for degree and the degree of both G and H is 0because no other edge is coming on these nodes let select G and after that select H. Similarly apply this method on each and every vertex.

By this it is clear that it traverses all the vertices exactly once and the sequence is $ABCDEFGH$.

Hence, A linear-time algorithm for which a directed acyclic graph and that graph contain a directed path that touches every vertex exactly once is proved.