Homework Help is Here – Start Your Trial Now!
Engineering
Computer Science
Writeup  Prove Theorem 1 Using Theorem 1, describe an algorithm

Writeup  Prove Theorem 1 Using Theorem 1, describe an algorithm

Database System Concepts
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
icon
Related questions
Question

(a) Writeup 

Prove Theorem 1

Using Theorem 1, describe an algorithm in words to check bipartiteness and analyze its run time.

 

b da di Figure 1: Example 1 b2 da Figure 2: Example 2
Transcribed Image Text:b da di Figure 1: Example 1 b2 da Figure 2: Example 2
Problem 1 Is Graph Bipartite? There is an undirected graph with n nodes, where each node is numbered between 0 and n- 1. You are given a 2D array graph, where graphlu] is an array of nodes that node u is adjacent to. More formally, for each v in graphlu), there is an undirected edge between node u and node v. The graph has the following properties: • There are no self-edges (graphlu] does not contain u). There are no parallel edges (graphlu] does not contain duplicate values). • If v is in graph[u), then u is in graph[u} (the graph is undirected). • The graph may not be connected, meaning there may be two nodes u and v such that there is no path between them. A graph is bipartite if the nodes can be partitioned into two disjoint sets A and B such that every edge in the graph connects a node in set A and a node in set B. There are other equivalent definitions of a bipartite graph. A graph is bipartite if and only if it has no odd length cycle, i.e., no cycle in the graph has an odd mumber of edges. Note that if a graph has no cycles it is bipartite (hence trees are bipartite graphs). It is an interesting exercise for you to show that the above two definitions are equivalent (highly recommended if you want to get a taste of graph theory). But that is not the goal of this exercise. Using the odd cycle definition one can use DFS or BFS to elegantly check whether a graph is bipartite in linear time, ie., O(m + n) time. Such solutions are discussed in leetcode (note that some of these may not be fully correct). This is also not the goal of this exercise. accepted and will receive O points. The goal of this exercise is to explore yet another approach to check bipartiteness and is based on the following ides. You have to argue that the idea is correct (as mentioned below) and implement the idea as an algorithm that checks for bipartiteness of a graph. Let G = (V,E) be the input graph that you want to check for bipartiteness. We first transform G into a new graph G' = (V', E') as follows. For each esch node v e V, construct two nodes v1, v2 € V' and for each edge (u, v) € E, create two edges (u1, 12) and (u2, v1) in E'. This completes the description of constructing G' from G. See Figure 1 for an illustration. The idea of this construction is that we reduce the problem of checking bipartiteness of G to checking the number of connected components of G as stated in the following theorem. you give such a solution, this will not be Theorem 1 Let C be the mumber of connected components in G. Then the mumber of connected components in G' is 20 if and only if the graph G is bipartite. Your first goal is to give a proof of the above theorem (soe the submissions instruetions below). To get an idea of why the above theorem might be true, see the two examples given in Figures 1 and 2. The graph in Example 1 is bipartite (no cycle) and the number of connected components is 1; it is 2 in G'. The graph in Example 2 is not bipartite (odd cycle of length 3) and the number of connected components is 1; it is 1 also in G'. Your second goal is to use the theorem above to give an efficient algorithm for checking bipartiteness.
Transcribed Image Text:Problem 1 Is Graph Bipartite? There is an undirected graph with n nodes, where each node is numbered between 0 and n- 1. You are given a 2D array graph, where graphlu] is an array of nodes that node u is adjacent to. More formally, for each v in graphlu), there is an undirected edge between node u and node v. The graph has the following properties: • There are no self-edges (graphlu] does not contain u). There are no parallel edges (graphlu] does not contain duplicate values). • If v is in graph[u), then u is in graph[u} (the graph is undirected). • The graph may not be connected, meaning there may be two nodes u and v such that there is no path between them. A graph is bipartite if the nodes can be partitioned into two disjoint sets A and B such that every edge in the graph connects a node in set A and a node in set B. There are other equivalent definitions of a bipartite graph. A graph is bipartite if and only if it has no odd length cycle, i.e., no cycle in the graph has an odd mumber of edges. Note that if a graph has no cycles it is bipartite (hence trees are bipartite graphs). It is an interesting exercise for you to show that the above two definitions are equivalent (highly recommended if you want to get a taste of graph theory). But that is not the goal of this exercise. Using the odd cycle definition one can use DFS or BFS to elegantly check whether a graph is bipartite in linear time, ie., O(m + n) time. Such solutions are discussed in leetcode (note that some of these may not be fully correct). This is also not the goal of this exercise. accepted and will receive O points. The goal of this exercise is to explore yet another approach to check bipartiteness and is based on the following ides. You have to argue that the idea is correct (as mentioned below) and implement the idea as an algorithm that checks for bipartiteness of a graph. Let G = (V,E) be the input graph that you want to check for bipartiteness. We first transform G into a new graph G' = (V', E') as follows. For each esch node v e V, construct two nodes v1, v2 € V' and for each edge (u, v) € E, create two edges (u1, 12) and (u2, v1) in E'. This completes the description of constructing G' from G. See Figure 1 for an illustration. The idea of this construction is that we reduce the problem of checking bipartiteness of G to checking the number of connected components of G as stated in the following theorem. you give such a solution, this will not be Theorem 1 Let C be the mumber of connected components in G. Then the mumber of connected components in G' is 20 if and only if the graph G is bipartite. Your first goal is to give a proof of the above theorem (soe the submissions instruetions below). To get an idea of why the above theorem might be true, see the two examples given in Figures 1 and 2. The graph in Example 1 is bipartite (no cycle) and the number of connected components is 1; it is 2 in G'. The graph in Example 2 is not bipartite (odd cycle of length 3) and the number of connected components is 1; it is 1 also in G'. Your second goal is to use the theorem above to give an efficient algorithm for checking bipartiteness.
Expert Solution
steps

Step by step

Solved in 2 steps

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer
Knowledge Booster
Fundamentals of Boolean Algebra and Digital Logics
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.
Similar questions
Recommended textbooks for you
Database System Concepts
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education
SEE MORE TEXTBOOKS