Question

There are many variants of Rudrata’s problem, depending on whether the graph is undirected or directed, and whether a cycle or path is sought. Reduce the DIRECTED RUDRATA PATH problem to each of the following.(a)The (undirected) RUDRATA PATH problem.(b) The undirected RUDRATA PATH problem, which is just like RUDRATA PATH except that the endpoints of the path are specified in the input.

Short answer

2. Enumerating the source and destination solves the given problem.

Step-by-step solution

Explain the RUDTATA PATH problem

Consider a directed or undirected graph, In which there exists a path that visits each vertex exactly once. The path is known as RUDRATA PATH.

Reduce undirected RUDTATA PATH problem

Consider the directed graph $G$, in which each vertex v is categorized into new and old vertices $i+o$. In-degree vertices are represented as i and the out-degree vertices are represented as o. Consider that every directed edge is connected to the vertex that is transformed into$i+o$new undirected edge of the vertex.

Assume that the vertex connected to the incoming edges is called the incoming vertex and the vertex connected to the outgoing edges is called the outgoing vertex. Connect each incoming vertex to undirected edges.

Thus, the graph G is transformed into G'. Consider the following example,

Therefore, the undirected graph is reduced to RUDATA PATH.

The undirected RUDRATA (s,t)− PATH problem.

Consider the directed graph $G$, in which each vertex is categorized into new and old vertices . In-degree vertices are represented as and the out-degree vertices are represented as . Consider that every directed edge is connected to the vertex that is transformed into new undirected edge of the vertex.

Based on the above graph information, enumerate the path as . Consider the vertex source as , and the vertex that ends the cycle is t.

Therefore, enumerating the source and destination solves the given problem.