Give pseudo-code for the following problems, making sure to state all the releva

Question

Give pseudo-code for the following problems, making sure to state all the relevant data structures and representations that you assume. You may assume that all the graphs are undirected. Give a linear-time algorithm for determining whether a given graph is bipartite. Give an 0(V)-time algorithm for determining whether a given graph contains a cycle. Note that your algorithm should run in the allotted time for all graphs, whether sparse or dense. Give an algorithm to find the minimum number of edges that must be removed from a given undirected graph in order to make it acyclic. The diameter of a tree T is the length of the longest path between two nodes in T. Describe an efficient algorithm for computing the diameter of T with V nodes and E edges.

Explanation / Answer

a)Algorithm for determining given graph is biparitite:

Biparitite Graph is a graph that contains two individual sets i.e For given U and V are two graphs ,vertices connected u and v are connected either u to v or v to u.The following steps for determining given graph is biparitite.

1.Assign RED color to the source vertex (putting into set U).

2. Color all the neighbors with BLUE color (putting into set V)

3. Color all neighbor’s neighbor with RED color (putting into set U)

4. As above assign color to all vertices i.e it satisfies all the constraints of m way coloring problem where m = 2

5. While assigning colors, if we find a neighbor which is colored with same color as current vertex, then the graph cannot be colored with 2 vertices.

b)Algorithm for determining given graph contains a cycle or not:

In this algorithm we used colours for visiting status in i.e colour each node white::not yet visited, grey ::visiting descendants and or black::finished visiting and It takes o(v) time.

define visit(node n):

if n.colour == grey:

    throw exception("Cycle found")

n.colour = grey //to indicate this node is being visited

for node child in n.children():

    if child.colour == white: //if the child is unexplored

      visit(child)

   n.colour = black // done visiting this node

return

c)

1.Create a graph G’  consisting of the vertices of G and the directed subset of the edges of G.

2.Topologically sort the vertices of G’ . If a cycle is found during the DFS report this and return.

3.Otherwise direct all of the undirected edges so that they are consistent with the direction given by the topological sort.

4.This can be done by running through the vertices in topologically sorted order, directing each undirected edge away from the endpoint found first. Because all of the edges (both directed and originally undirected, but now given a direction) are consistent with the topological sort the new graph is a DAG.

5.Time is O(V + E), the time for topologically sorting the vertices and then running through them (and the edges leaving them) in order.

d)

In a given graph define the distance between 2 vertices u, v to be the length of shortest path between u and v. The value of d(u, v) Define Eccentricity of a vertex v to be e(v) = max {d(u, v) | u V(G)} (V(G) is the set of vertices in graph D(G) and Diameter(G) = max{e(v) | v V(G)}

Algorithm as follows step by step

1. For each vertex v in V(G) run BFS(v) and build a 2 dimensional array of distances from each vertex to others.

2.Compute e(v) for each vertex from the 2 dimensional array created in step 1.

3. Compute diameter(G) by finding the maximum e(v) from step 2.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.