Corrections
In Figure 11.6, the right-hand graph needs an extra vertex and edge. You should put a vertex in the middle of one of the edges. It doesn't matter which one (Question: why not?).
In the DF algorithm of Section 11.7, there ought also to be a computation of D(y), the tree distance to the root, just as in the BF algorithm. (There's no reason to do it in one and not the other.) I will not expect this from the students, but it is an oversight in the book.
What I would add to the DF algorithm is two steps:
in the initialization part (1), set D(u) = 0; and
in the recursive step (2), add substep (v) Set D(y) = D(x) + 1.
In Theorem 11.7.6, G should also be connected.
Definitions
- A transitive tournament is a tournament whose vertices can be listed, e.g. v1, v2, ..., vn, so that every arc goes from an earlier vertex in the list (that is, with a lower number) to a later vertex (that is, with a higher number). In other words: every arc (vi,vj) has i < j.
- A coloring of a graph G in k colors is a function f : V --> {1,2,...,k} such that, for each edge vw, f(v) /= f(w).
- The wheel with k spokes, Wk, is the graph consisting of a cycle of k vertices and one more vertex adjacent to all the vertices of the cycle. This is defined for k >= 3. (W3 is the same as K4, by coincidence.)
- A clique in a graph G is a set of vertices that are all adjacent to each other.
- An independent set in G is a set of vertices of which none is adjacent to any other.
- The clique number, omega(G), is the largest size of a clique in G.
- The independent set number, alpha(G), is the largest size of an independent set of vertices in G.
Go to homework | course information.