Graphs (bipartite)
Graphs (traversals & bipartite) - bipartite
In-class activity
At the board:
Draw a graph with 7 vertices and 9 edges
Rotate clockwise so you are looking at a different group's graph
Try to decide if the graph is bipartite
Mini-lesson on algorithm
Rotate so you are looking at a different group's graph
Run the algorithm
As you work on deciding if a graph is bipartite, we will take some time to discuss a brute force approach and analyze correctness/runtime.
To set this up, we'll first think about a brute force approach to checking if a graph is bipartite.
Consider this algorithm design process:
Step 1: Articulate the problem
Given a graph G = (V,E), is there a partition of the vertex set into two disjoint subsets such that every edge has an endpoint in each of the two subsets?
Step 2: Propose a solution
Let's try a "brute force" approach, where we consider every possible way of partitioning the vertex set, then check if any verify that the graph is bipartite.
For every partition of the vertex set into two subsets
Check if there is an edge with both endpoints in the same subset. If so, move on to the next partition.
If there were no such edges, return yes.
If every partition had an edge with both endpoints in the same subset, return no.
Step 3: Prove correctness
With a brute force approach, correctness typically is straightforward. Here, we directly test the definition of a bipartite graph: does there exists a partition with edges only going between endpoints in the different sets. (Or, if we think of it as a 2-coloring, edges have different colors on their endpoints.)
Here is a more formal proof:
Claim: The brute force approach returns "yes" if and only if the input graph is bipartite.
Proof:
(=>) Assume the approach returns "yes"; this happens precisely when it finds a partition of the vertices such that no edges have endpoints in the same vertex set. Therefore, we have satisfied the definition of a bipartite graph.
(<=) Assume the graph is bipartite. Then, by definition, there exists a partition such that no edges have endpoints in the same vertex set. There are a finite number of partitions, so the process enumerates them all. At some point, it will find this partition and return the correct answer "yes".
Step 4: Analyze complexity
We'll analyze the time complexity of the approach. First, observe that there are 2n ways to partition the vertex set of n vertices into vertex sets X and Y. To see this, pick an arbitrary ordering of the vertices v1,...,vn. Each vi can either be in X or Y (2 choices), so there are 2n total ways to partition into X and Y. Let's assume that we mark each vertex with its partition label. The body of the loop checks every edge to see if both endpoints are marked with the same label. Therefore, we must walk over each edge; the time for this depends on the graph representation that we use. If we use an adjacency list, we take O(m+n) time to walk the edges; even with the assumption that we can find the endpoint marks in constant time, this will lead to an overall running time of O((m+n)2n). We can do slightly better if we use a set representation for the graph and assume that each edge has a pointer to its endpoints. In this case, we can walk the edges in O(m) time, leading to an overall running time of O(m2n).
No matter which representation we use, though, this is a terrible running time! The brute force approach gives us an upper bound on how to solve the problem, so any algorithm that does (asymptotically "a lot") better must have used deeper problem solving.
Logistics
New pods!
Status flags
Each team has a status flag that you can use to help me focus where to go:
green: working, no questions
yellow: have a question, but not blocked from doing work
red: have a question, blocked from doing work
blue: done, just hanging out
Articulation practice
Remember: this is an opportunity to practice clear, concise and precise communication while working through the material!
Throughout the course, each of you must volunteer at least once to serve as the facilitator, who will:
Make sure everyone has a chance for their voice to be heard. For example, saying:
“X, we haven’t heard from you in a while. Do you have thoughts on this problem or is there another one you’d like to shift to?”Keep track of time to cover as much of each problem as possible
Post a clearly articulated report with a summary and/or questions to the corresponding Ed Discussion category
Please be sure to also post your pod # and other team members, as in “Report for Pod 2 (Audrey St. John, Mary Lyon, …)”
If you’d prefer to use a doc, post the link or turn it into an image to attach
If you have work from the board, you can take a photo and post it
![](https://www.google.com/images/icons/product/drive-32.png)