Given an undirected graph G = (V ,E) you want to color the nodes Green and YELLO
ID: 3758520 • Letter: G
Question
Given an undirected graph G = (V ,E) you want to color the nodes Green and YELLOW in such a way that two nodes connected by an edge must have a different color. Use BFS to show how to determine if such a coloring is possible, and find it if it exists. Given a directed acyclic graph G = (V, E) you want to find the length L of the longest path in the graph. Use DFS to get a topological sort of the nodes V1,... ,vn. Denote with L[i] the length of the longest path starting at Vi. Express L(i) as a function of L[j] for j >i. Use dynamic programming to fill the array L[1],..., L[n] and use these values to compute L. What is the running time of your algorithm as a function of n = |V| and m = |E|? Prove or disprove the following fact: Given a graph G, the tree generated by a DFS algorithm always has height larger or equal than the height of the tree generated by a BFS algorithm. Hint - Consider two cases: when the BFS and DFS algorithms start from the same node or from two different arbitrary nodes in GExplanation / Answer
Problem 1:
The given problem is a 2-coloring problem. That is, the graph must be colored with 2 colors, such that no two neighboring vertices have the same color.
We can use BFS (breadth first search) algorithm to find whether the given graph is 2-colorble or not. BFS is a traversing algorithm, it starts at an arbitrary node in the graph and explores the neighbors, next explores their neighbors and so on, until the leaves are explored.
Procedure to find whether a graph is 2-colorble or not:
1) Start BFS with an arbitrary node as a start node.
2) Color the start node as Green.
3) Explore the next level vertices (adjacent to start node) and color them Yellow.
4) Explore the next level vertices and color them Green.
5) Whenever the nodes are colored in the step 4 and 5, check whether the vertices and their neighbors have same color. If they have same color, return false to say the graph is not 2-colorble. Otherwise, return true to say the graph is 2-colorble.
6) Do step 3 and 4 until the leaves are explored and colored.
Note: even length nodes are colored with green, odd length vertices are colored Yellow.
Algorithm IsTwoColorble(G)
//G is the given undirected graph
//assume initially color of all vertices is null.
//initialize an empty queue Q
//arbitrarily selects v as the starting vertex
v.color=GREEN
Q.enqueue(v);
While Q is not empty do
u=Q.dequeue()
for each vertex w adjecent to u
if w.color=null do
if u.color=GREEN
w.color=YELLOW
else
w.color=GREEN
end if
Q.enqueue(w)
else if w.color=u.color
return false
end if
end for
end while
return true
The above algorithm IsTwoColorble() takes an undirected graph G as input and returns a Boolean value. If the given graph is 2-colorble, the algorithm returns true, otherwise it returns false.
The worst case time complexity of the algorithm is same as the worst case time complexity of BFS.
That is, O(|v|+|E|), because, in each iteration all nodes and all the edges are explored in the worst case.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.