Testing Bipartiteness: An Application of Breadth-First Search

A bipartite graph is a graph where one node V can be partitioned into sets X and Y where X are red and Y are blue. In a bipartite graph it is possible to color all the nodes blue and red so every edge has one red end and one blue end.

(3.14) A graph is not bipartite if it contains an odd-length cycle.

How can we test for bipartiteness?

The Algorithm:

• Assume the graph is connected
• pick any node s in V and color it red
• color all neighbors of S blue
• color all of their neighbors red and so on until the graph is completely colored

The algorithm design is identical to BFS as we are moving outward from s (color odd layers blue and even layers red) The total running time is O(m+n)

(3.15) Claim Let G be a connected graph, and let L₁, L₂,… be the layers produced by BFS starting at node s. Then exactly one of the following two things must hold

1. There is no edge of G joining two nodes of the same layer. In this case G is a bipartite graph in which the nodes in even-numbered layers can be colored red, and the nodes in odd-numbered layers can be colored blue
2. There is an edge of G joining two nodes of the same layer. In this case, G contains an odd-length cycle, and so it cannot be bipartite.

The Proof

Consider case 1 where there is no edge joining two nodes of the same layer by theorem 3.4 we know every edge of G joins nodes in either the same or adjacent layer. In this case we assume they never join in the same layer, so every edge joins two nodes in adjacent layers. Because the coloring gives nodes in adjacent layers opposite colors, we know every edge has ends with opposite colors and the graph is bipartite.

Consider case 2 where G must contain an odd cycle so there is an edge that connects two nodes in the same layer. Supposed the two nodes in the same layer, x and y, are in layer L_j. Let z be the node that is in layer L_i, the lowest common ancestor, the node that is directly above x and y, and L_i > L_j. There is a cycle in the path z-x and y-z. The length of the cycle is 2(j-i)+1 which is an odd number.

Readability: 10. Very easy reading, kind of dry.

Connectivity in Directed Graphs

In this section we see what ideas we applied to undirected graphs can apply to directed graphs.

A directed graph has direction to its edges. Say an edge (u, v) has a direction that goes from u to v, its relationship is asymmetric.

How we represent Directed Graphs:

• We use the adjacency list representation but modify it so instead of each node having a single list of neighbors each node has two lists: one that has nodes that is points to and one that has nodes that point to it.

Graph Search Algorithms

BFS search in directed graphs computes the set of all nodes with the property that s has a path to t, not that t has a path to s. It is very similar to BFS of undirected graph and has the same runtime of O(m+n) DFS search also runs in linear time and compute the same set of nodes.

Strong Connectivity

A graph is strongly connected if for nodes u and v there is a path from u to v and v to u. This also means they are mutually reachable

(3.16)

If u and v are mutually reachable, and v and w are mutually reachable, then u and w are mutually reachable.

Proof The first path we take is from u to v and then from v to w. Since v is mutually reachable to w we can then go to the path w to v and then from v to u.

To test if a graph G is strongly connected we run a simple BFS starting from s and then another BFS starting from s in G reversed. If one of the searches fails to reach the node then the graph is not strongly connected.

(3.17)

For any two nodes s and t in a directed graph, their strong components are either identical or disjoint.

Proof Two nodes s and t are mutually reachable so we claim that the strong components containing s and t are identical. So for any node v if s and v are mutually reachable then t and v are mutually reachable (by 3.16). But if s and t are NOT mutually reachable then there cannot be a node v that is in the strong component of each. If there were then s and v and v and t would be mutually reachable so s and t would be.

We can compute the strong components for all nodes in O(m+n)

I thought this section was pretty dry. It was short and easy to read but not that interesting to me. Readability: 8

Directed Acyclic Graphs and Topological Ordering

A directed acyclic graph (DAG) has no cycles.

We use DAGs to represent dependencies or precedence relations for example showing a set of tasks where one is dependent on the other or one needs to be performed before the other can. Example: Course prerequisite for CS major. A DAG has a topological ordering which is an ordeing of its nodes so that for every edge (v_i, v_j), i<j. All of the edges must point forward in an ordering.

3.18 If G has a topological ordering, then G is a DAG.

An algorithm for finding a topological ordering:

3.19 In every DAG, there is a node v with no incoming edges

Proof There is a directed graph G where every node has at least one incoming edge. To show how to find a cycle, we pick a node v and follow the edges backward from v since it has at least one incoming edge we can move to node u. And from u backward to x etc. After n+1 steps we will have visited some node twice which shows there is a cycle

Having a node with no incoming edges is all that is needed to produce a topological ordering. 3.20 If G is a DAG, then G has a topological ordering.

Algorithm

   To compute a topological ordering of G:
   Find a node v with no incoming edges and order it first
   Delete v from G
   Recursively compute a topological ordering of G-{v} and append this order after v

The runtime of this algorithm is O(n²) To achieve an algorithm with O(m+n) we use the same one but iteratively delete nodes with no incoming edges.

This section was definitely more interesting to read than the last. I think DAG's are pretty cool. The readability was a 9 out of 10 even though some things felt a little vague the first time through.

Interval Scheduling: The Greedy Algorithm Stays Ahead

The idea for a greedy algorithm in the terms of the interval scheduling problem is create a rule to choose the first request then reject all other requests that are not compatible with the chosen request. Then select the next request and repeat. There are many ways we could choose a rule to pick the first request such as ordering by the earliest start time, the smallest interval time, or the job with fewest conflicts, or what we choose to use, finish time.

The Algorithm

 Initially let R be the set of all requests, and let A be empty
 While R is not yet empty 
     Choose a request i in R that has the smallest finishing time 
     Add request i to A
     Delete all requests from R that are not compatible with request i
 Endwhile
 Return the set A as the set of accepted requests

We declare that the intervals in the set returned by the algorithm are all comparable. The set is a compatible set of requests. We now want to show that the greedy solution A, is optimal. So we show that A = O. The greedy rule guarantees that f(i₁) ⇐ f(j_i) this how we show that the greedy solution “stays ahead”. It stays ahead of O: for each r, the r_th interval it selects finished at least as soon as the r_th interval in O.

4.3 The greedy algorithm returns an optimal set A.

We can make our algorithm run in O(n log n)…

• begin by sorting the n requests in order of finishing time
• assume that f(i) =< f(j) when i<j
• construct an array S[1…n] with the property that S[i] contains the value s(i).
• select requests by processing intervals in order of increasing f(i).
• This takes O(n) time!!

A Related Problem: Scheduling All Intervals In this problem we have identical resources and have to schedule all of the requests using as few resources as possible. Example: scheduling classes in the smallest number of classrooms possible. This is called the interval partitioning problem We can define the depth of a set of intervals to be the maximum number that pass over any single point on the time-line.

4.4 In any instance of Interval Partitioning, the number of resources needed is as least the depth of the set of intervals.

Algorithm

 Sort the intervals by their start times, breaking ties arbitrarily
 Let I<sub>1</sub> , I<sub>3</sub>,..., I<sub>n</sub> denote the intervals in this order
 For j = 1, 2, 3, ..., n
    For each interval I<sub>j</sub> that precedes I<sub>j</sub> in sorted order and overlaps it
        Exclude the label of I<sub>i</sub> from consideration for I<sub>j</sub>
    Endfor
    If there is any label from {1, 2, ..., d} that has not been excluded then
       Assign a nonexcluded label to I<sub>j</sub>
    Else
       Leave I<sub>j</sub> unlabeled 
    Endif
 Endfor
 

4.5 If we use the greedy algorithm above, every interval will be assigned a label, and no two overlapping intervals will receive the same label.

If you have d labels to use then as you go through the intervals from left to right you assign a label to each interval you encounter, you never reach a point where all of the labels are currently in use.

4.6 The greedy algorithm above schedules every interval on a resources, using a number of resources equal to the depth of the set of intervals. This is the optimal number of resources needed.

This section was very interesting. I like scheduling a lot because I feel like it is really applicable to a problem that needs to be solved every day and something I could make use of. The readability of this section was a 9 out of 10 especially after reading it after the class lecture.