15-451 Algorithms 03/18/09
* 2-coloring RECITATION NOTES
* BFS trees, DFS trees
=======================================================================
As you know, each semester the registrar schedules final exams. Can
think of this as a graph problem. Each node is a class, and
there is an edge between two if lots of students are taking both
classes. Goal is to use fewest number of different time slots such
that no two adjacent nodes are given the same time slot.
E.g., pentagon.
Graph Coloring Problem
----------------------
Given a graph, want to give each node a color such that no
two neighbors have the same color. Goal is to do this with the fewest
total number of different colors (easy to do with n colors).
In the above scheduling problem, each color is a different time slot.
Unfortunately, graph-coloring problem is NP-hard. In fact, even telling if
possible to color with <= 3 colors is NP-hard in general. But,
2-coloring problem (color with 2 colors if possible else say
"impossible") is easy. How to do it?
Turns out it's pretty simple. Pick some vertex v and give it one
color (say, red). Then all its neighbors had better be the other
color (say, blue). All their neighbors had better be red, their
neighbors blue and so forth, sweeping across the graph until
everything in v's connected component has a color. Now, we check: if
there is any bad edge (both endpoints the same color) then G is not
2-colorable: why? because all our decisions were forced. Otherwise we
have a legal 2-coloring of v's component and we run this procedure
again on any remaining components (which don't interfere with each other
since there are no edges between components).
Another term for a graph being 2-colorable is that it is bipartite.
So, this is an algorithm for testing if a graph is bipartite, and if
so, finding a bipartition.
One way to think of this is we are doing breadth-first search. (can
actually use DFS to do this too, but BFS is easier to visualize).
BFS trees and DFS trees
-----------------------
Breadth-first search: start at some vertex v. Then go to all
neighbors (call them "level 1" since they're distance 1 from v) then
to their unvisited neighbors (level 2 at distance 2 from v) and so
on, sweeping this wavefront across the graph. Operationally, we can do
this by storing current wavefront (fringe) in a queue. Something like
BFS(s):
mark s as visited and insert s into queue. level(s)=0.
while (queue not empty):
v <- queue.remove()
for all unvisited neighbors w of v:
put edge (v,w) into BFS tree T
mark w as visited, level(w)=level(v)+1
queue.insert(w)
Total time = time for BFS = O(m + n)
Note 1: There are multiple possible BFS trees from a given start s,
depending on ordering of neighbors. [example] Same with DFS.
Note 2: What do edges in G that are *not* in the BFS tree look like?
If G is undirected, then any such edge (u,v) must be between two
vertices such that |level(u)-level(w)| <= 1. In particular, no
back-edges, only cross-edges. [not true if G is *directed*]
In particular, with respect to coloring, if coloring was illegal there
must be an edge in G between two nodes at the same level i.
How about DFS trees? Let's write out DFS again since we're going to
use it later anyway. Also introduce notion of "DFS numbering" which
is just the order in which vertices are first visited by the DFS.
DFS_main(G):
count = 1.
For v=1 to n: if v is not yet visited, do DFS(v).
DFS(v):
mark v as visited. // entering node v
dfsnum(v) = count++.
for each unmarked out-neighbor w of v:
put (v,w) into DFS tree T
do DFS(w).
mark v as exited.
In an *undirected* graph, what do the non-tree edges of G look like?
Can you have cross-edges? [between u and v such that neither is an
ancestor of the other] No. Only back-edges.
In a *directed* graph, you *can* have cross-edges, but they have to
point to a node of lower dfsnum that was already exited.