A 2-coloring of an undirected graph with n vertices and m edges is the assignment of one of two colors (say, red or green) to each vertex of the graph, so that no two adjacent nodes have the same color. So, if there is an edge (u,v) in the graph, either node u is red and v is green or vice versa. Give an O(n + m) time algorithm (pseudocode!) to 2-colour a graph or determine that no such coloring exists. (Hint: Use BFS)
The following shows examples of graphs that are and are not 2-colourable:
Algorithm to find out whether a given graph is Birpartite or not
(2-colorable or not )using Breadth First Search (BFS).
step 1. Assign RED color to the source vertex (putting into set
U).
step 2. Color all the neighbors with GREEN color (putting into set
V).
step 3. Color all neighbor's neighbor with RED color (putting into
set U).
step 4. This way, assign color to all vertices such that it
satisfies all the constraints of m way coloring problem where m =
2.
step 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 (or graph is not
Bipartite)
As,we are using BFS, Time complexity is O(m+n) where m is number of
vertices and n is number of edges.
A 2-coloring of an undirected graph with n vertices and m edges is the assignment of one of two colors (say, red or green) to each vertex of the graph
B-1 Graph coloring Given an undirected graph G (V. E), a k-coloring of G is a function c : V → {0, 1, . . . ,k-1} such that c(u)≠c(v) for every edge (u, v) ∈ E. In other words, the numbers 0.1,... k-1 represent the k colors, and adjacent vertices different colors. must havec. Let d be the maximum degree of any vertex in a graph G. Prove that we can color G with d +1 colors.
2. Let G = (V, E) be an undirected connected graph with n vertices and with an edge-weight function w : E → Z. An edge (u, v) ∈ E is sparkling if it is contained in some minimum spanning tree (MST) of G. The computational problem is to return the set of all sparkling edges in E. Describe an efficient algorithm for this computational problem. You do not need to use pseudocode. What is the asymptotic time complexity of...
Question 1: Given an undirected connected graph so that every edge belongs to at least one simple cycle (a cycle is simple if be vertex appears more than once). Show that we can give a direction to every edge so that the graph will be strongly connected. Question 2: Given a graph G(V, E) a set I is an independent set if for every uv el, u #v, uv & E. A Matching is a collection of edges {ei} so...
(2) Recall the following fact: In any planar graph, there exists a vertex whose degree is s 5 Use this fact to prove the six-color theorem: for any planar graph there exists a coloring with six colors, i.e. an assignment of six given colors (e.g. red, orange, yellow, green, blue, purple) to the vertices such that any two vertices connected by an edge have different colors. (Hint: use induction, and in the inductive step remove some verter and all edges...
Let G (V, E) be a directed graph with n vertices and m edges. It is known that in dfsTrace of G the function dfs is called n times, once for each vertex It is also seen that dfs contains a loop whose body gets executed while visiting v once for each vertex w adjacent to v; that is the body gets executed once for each edge (v, w). In the worst case there are n adjacent vertices. What do...
Say that we have an undirected graph G(V, E) and a pair of vertices s, t and a vertex v that we call a a desired middle vertex . We wish to find out if there exists a simple path (every vertex appears at most once) from s to t that goes via v. Create a flow network by making v a source. Add a new vertex Z as a sink. Join s, t with two directed edges of capacity...
2) Let G ME) be an undirected Graph. A node cover of G is a subset U of the vertex set V such that every edge in E is incident to at least one vertex in U. A minimum node cover MNC) is one with the lowest number of vertices. For example {1,3,5,6is a node cover for the following graph, but 2,3,5} is a min node cover Consider the following Greedy algorithm for this problem: Algorithm NodeCover (V,E) Uempty While...
2. Consider the (undirected) graph G having the following vertex set Vand edge set E. V-0,1,2,3,4,5,6,7,8,9 E- 0,1,10,2), 11,2;, 12,4), 12,3), 13,4), (4,5), {5.6,, 14,6, 2,7) e) [8pts] Show the action of BFS starting at vertex 2. Show action of queue, parent array implementation of BFS spanning tree and display nodes in order they are traversed. Choose next node as it occurs in the adjacency list.
Please show work clearly. Thanks 3. (10 points) Let G be an undirected graph with nodes vi,..Vn. The adja.- cency matriz representation for G is the nx n matrix M given by: Mij-1 if there is an edge from v, to ty. and M,',-0 otherwise. A triangle is a set fvi, vjof 3 distinct vertices so that there is an edge from v, to vj, another from v to k and a third from vk to v. Give and analyze...
For a directed graph the in-degree of a vertex is the number of edges it has coming in to it, and the out- degree is the number of edges it has coming out. (a) Let G[i,j] be the adjacency matrix representation of a directed graph, write pseudocode (in the same detail as the text book) to compute the in-degree and out-degree of every vertex in the Page 1 of 2 CSC 375 Homework 3 Spring 2020 directed graph. Store results...