Exercise 11.11 An undirected graph G- (V, E) is called bipartite if it contains no odd cycle, i.e., no cycle has an odd mumber of edges. Note that a graph with no cycles is also bipartite. We are going to show an important property of bipartite graphs its verter set can be partitioned into two disjoint sets A and B, ie., A UB-V and AnB = 6, such that all the edges are between vertices in A and vertices in B- in other words, there are no edges between any two vertices in A and any two vertices in B. The goal of this problem is that, given a connected bipartite graph G= (V, E), to find a partition of the vertez set into A and B such that all edges are between some verter in A and some vertez in B. (a) Do Breadth-First Search (BFS) on G from some starting vertex, say a, and compute the distance (i.e., the level in the BFS tree) of every verteze to a. Show that if G is bipartite then there are no edges betwoen vertices in the same level. (Hint: Use the odd eycde property of bipartitegraph). (b) Show that you can output the sets A and B in linenr time, ie., O(V|+|E]) time.

Exercise 11.11 An undirected graph G- (V, E) is called bipartite if it contains no odd cycle, i.e., no cycle has an odd mumber of edges. Note that a graph with no cycles is also bipartite. We are going to show an important property of bipartite graphs its verter set can be partitioned into two disjoint sets A and B, ie., A UB-V and AnB = 6, such that all the edges are between vertices in A and vertices in B- in other words, there are no edges between any two vertices in A and any two vertices in B. The goal of this problem is that, given a connected bipartite graph G= (V, E), to find a partition of the vertez set into A and B such that all edges are between some verter in A and some vertez in B. (a) Do Breadth-First Search (BFS) on G from some starting vertex, say a, and compute the distance (i.e., the level in the BFS tree) of every verteze to a. Show that if G is bipartite then there are no edges betwoen vertices in the same level. (Hint: Use the odd eycde property of bipartitegraph). (b) Show that you can output the sets A and B in linenr time, ie., O(V|+|E]) time.

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Similar questions

Java Very important: As a COMMENT IN CODE, please DO Test-Cases on how you would test your solution assumptions and hence your code explore a specific way to perform a Breadth First Search (BFS) of a given Graph [Ref : Figure 1].
Prove that the two graphs below are isomorphic.
2. Consider the graph G2(V2, E2) below. 2a. Find the MST of this graph with Kruskal’s algorithm. Draw the MST, and show the table [edge] [w(u, v)] [mark]. 2b. Find the MST of this graph with Prim’s algorithm starting at vertex 'a'. Draw the MST and list the vertices in order you added them to the MST. 2c. Would you get a different MST if you repeat 2b starting at vertex 'e'? Why or why not?
BLOCKS A connected graph with no cut-vertex need not be 2-connected, since it can be K₁ or K₂. Connected subgraphs without cut-vertices provide a useful decomposition of a graph. 4.1.16. Definition. A block of a graph G is a maximal connected subgraph of G that has no cut-vertex. If G itself is connected and has no cut-vertex, then G is a block. Now answer the question 4.1.6 4.1.6. (-) For a graph G with blocks B₁,..., Bk, prove that n(G) = (₁ n(B₁)) - k +1.
1. This question is about type of graphs. a. Construct a graph with exactly 5 nodes such that the graph is strongly connected. b. Construct a graph with exactly 5 nodes such that the graph is weakly connected. c. Construct a graph with exactly 5 nodes such that the graph is completely connected. d. Construct a graph with exactly 5 nodes such that the graph is not connected. e. Construct a graph with exactly 5 nodes such that the graph is not a simple graph.
Exercise 12.9 Given a weighted (connected) undirected graph G = (V, E, w), with m =n+ 0(1) edges (i.e., the number of edges is at most the number of vertices plus some constant), give an O(n)-time algorithm to compute the minimum spanning tree of G. Prove the correctness and the running time of your algorithm. (Hint: Think of how one can eliminate an edge from being in the MST.)
S Given the following adjacency matrix representation of a di-graph: 1 2 3 1- VE A 7 0 H ### 1. 11. 17 1 1 Show its adjacency list representation: Using draw.io, construct its graphical representation:
Java code only ExampleInput:41 1 2 2 Output:72