Massachusetts Institute of Technology Handout 17 6.042J/18.062J: Mathematics for Computer Science September 29, 2000 Professors Nancy Lynch and Shlomi Dolev

Tutorial 4 Problems

Problem 1 Scheduling Courses

We consider a simple kind of scheduling problem — for MIT courses with prerequisites. The problem is to determine how a student could complete all of the courses in the fewest terms, under the simplifying, if unlikely, assumption that there is no limit on the number of courses a student can take in a term as long as their prerequisites have all been met. We model this problem with a digraph. An example is shown in the figure below.

Figure 1: This is a picture of a directed acyclic graph. Vertices are labeled with course names. An edge from u to v indicates that course u is a prerequisite for course v.

(a) What’s the length of a critical path? find such a path.

(b) How many terms are necessary and sufficient to complete all of the courses shown in the Figure, assuming prerequisites are observed, but course load is no issue? Prove your answer (both necessary and sufficient).

(c) Show that there is a schedule for taking courses which achieves the minimum number of terms, t. the previous question includes this direction Problem 2 Digraphs

Show that every tournament graph has a Hamiltonian path.

Problem 3 Let L_{n} be the n + 1-vertex simple “line” graph consisting of a single simple path of length n. For example, L_{4} is shown in the figure below:

[figure]

The line graph L_{4}

Let’s say a simple graph has “two ends” if it has exactly two vertices of degree one, and all its other vertices have degree two. In particular, for n ≥ 1, the graph L_{n} has two ends.

(a) Draw a diagram of the smallest simple graph with two ends which is not isomorphic to any line graph. Hint: See part (d).

(b) Explain briefly, but clearly, what is wrong with the following argument:

False theorem: Every simple graph with two ends is isomorphic to L_{n} for some n ≥ 1.

False proof: We prove by induction on the number, n ≥ 1, of edges in a simple graph, that every two-ended graph with n edges is isomorphic to L_{n}.

(Base case n = 1): A simple graph with one edge can only consist of the two vertices connected by that edge and some number of vertices not attached to any edge, i.e., vertices of degree zero. Since a two-ended graph cannot have vertices of degree zero, the only twoended graph with one edge must consist solely of the two vertices connected by the edge, which makes it isomorphic to L_{1}.

(Induction case): Assume that n ≥ 1 and every two-ended graph with n edges is isomorphic to L_{n}. Now let G_{n} be any two-ended graph with n ≥ 1 edges. By hypothesis, G_{n} is isomorphic to L_{n}. Suppose an edge is added to G_{n} to form a two-ended graph G_{n+1}.

Since G_{n} is isomorphic to L_{n}, it consists of a simple path of length n. The only way to add an edge to the path and preserve two-endedness is to have that edge go from one end—that is, one of the degree-one vertices—to a new vertex, lengthening the path by one. That is, the resulting n + 1-edge graph must be a simple path of length n + 1, so it is isomorphic to L_{n+1}. Q.E.D.

(c) Here is another argument for the same False Theorem as in part (b).Explain exactly where it goes wrong.

False proof 2: Same induction hypothesis and base case as in part (b).

(Induction case): For any n ≥ 1, let G_{n+1} be any two-ended graph with n + 1 edges. Let G_{n} be the graph which results from removing one of the degree-one vertices v of G_{n+1} and the edge {v, w} attached to it. So G_{n} no longer has the vertex, v, of degree one. But the degree of w is one less in G_{n} than it was in G_{n+1}, so G_{n} still has two vertices of degree one and one fewer vertex of degree two. Therefore G_{n} is also two-ended. By induction G_{n} consists of a simple path of length n. But G_{n+1} is obtained by attaching an edge from one end of the path to a vertex v not on the path, thereby lengthening the path by one. So G_{n+1} is isomorphic to a simple path of length n + 1; that is, it is isomorphic to L_{n+1}. Q.E.D.

(d) Describe how to make a small revision to one of the false proofs above so that it becomes a correct proof of the theorem “Every connected simple graph with two ends is isomorphic to L_{n} for some n ≥ 1.”

Problem 4 The diagram below depicts a weighted graph G, with integer weights on the edges as shown. Try to find a spanning tree of G with the smallest possible total edge weight (that is, a Minimum Spanning Tree).