|
|
GRAPH THEORY |
|
| Instructor: Gábor Hetyei | Last update: November 30, 2001 | |
| Disclaimer: The information below comes with no warranty. If, due to typocraphical error, there is a discrepancy between the exercise numbers announced in class and the numbers below, or this page is not completely up to date, the required homework consists of those exercises which were announced in class. Check for the time of last update above. If, by my mistake, a wrong exercise number shows up below, I will allow you extra time to hand in the exercise whose number was announced in class. If, however, exercise numbers are missing because this page is not up to date, it is your responsability to contact me before the due date. (No extra time will be allowed in that case.) This page is up to date if the last update happened after the last class before the next due date. |
| Date due | Problems: | Monday December 3, 2001 |
Draw the line graph of an octahedron, 4.2.7, 4.2.20 (for k=3
only, get bonus points for the general solution). Bonus: 4.3.2. |
| Date due | Problems: | Monday November 26, 2001 | only bonus problems were assigned this week, due to Thanksgivig. They are 4.2.4, 4.2.5, 4.2.17, and drawing the line graph of the cube. |
| Monday November 19, 2001 | 4.2.2, 4.2.3, 4.2.6, prove that the (vertex-)connectivity of the second graph is 4 in 4.1.8. |
| Monday November 12, 2001 | 4.1.8, 4.1.13/a,b, 4.2.1. |
| Monday November 5, 2001 | 4.1.1, 4.1.2, 4.1.3. |
| Monday October 29, 2001 |
3.2.1, 3.2.2, 3.2.5, 3.2.6
Bonus: 3.2.3, 3.2.4. |
| Monday October 22, 2001 |
2.3.7 (use 2.1.37), 3.1.3 (hint: how does M-saturation change when we
use an augmenting path?), 3.1.8 (hint: start matching the leaves),
3.1.4 (for betas only), 3.1.6 (hint: trees are bipartite).
Bonus: Describe a linear programming problem aimed to fined a minimum edge cover for a graph. |
| Monday October 15, 2001 |
2.3.5, 2.3.7, 3.1.1, 3.1.2.
Bonus: 2.3.18, 2.3.29. |
| Monday October 8, 2001 |
Answer 1.4.7 for an undirected graph. (=Is there a simple graph on 10 vertices
such that all the degrees ar different?) Compute the Prüfer code for the path 1-5-2-4-3, and find the tree whose Prüfer code is 24431. 2.3.1, 2.3.3. Bonus: 2.3.6 (you may use 2.3.1). |
| Monday October 1, 2001 | 2.1.1, 2.1.6, 2.1.11, 2.1.14 |
| Monday September 24, 2001 |
1.4.1, 1.4.7, 1.4.37.
Bonus: 1.4.38 |
| Monday September 17, 2001 |
1.4.6 (draw D3 instead of D4 since that one is on
p. 61 !) 1.4.19. How can you use the adjacency matrix to determine the indegree and the outdegree of a vertex? Bonus: Describe the meaning of the entries in the square of the adjacency matrix. [Expires Monday, September 17] Draw the de Bruijn graph D5. |
| Monday September 10, 2001 |
1.3.2,1.3.4, 1.3.9
Bonus: Assume a boatman (B) wants to take a cabbage (C), a goat (G) and a wolf (W) to the other side of the river. There is place only for one item in his boat, and he can not leave unattended the wolf with the goat, or the goat with the cabbage on the same side of the river. Represent all possible situations as vertices of a graph, and connect a pair if they are reachable from each other in one step. Find the shortest "safe" method to transport everything and everyone on the other side of the river. Bonus: Using the Degree-Sum Formula, give a formula for the number of edges of a k-dimensional hypercube. |
| Wednesday September 5, 2001 |
1.2.2, 1.2.3, 1.2.6, 1.2.8.
Bonus: Conclude the proof of Proposition 1.2.28. (Why is the cycle mentioned in the last sentence of the proof "sufficiently long"?)[expired] |
| Monday August 27, 2001 |
1.1.2, 1.1.11, 1.1.12, 1.1.15 (B intersction D only). Bonus: 1.1.7 (looking at 1.1.6 may help) |