Homework for Math/CS 443/543
Theory of Graphs and Networks
Fall 2006

• (13) Due Monday, December 4:
  • Read sections 28 and 29 of the text.
  • Do problems 28.5, 28.6, 29.2, 29.4, and 29.6
• (12) Due Wednesday, November 29:
  • Read sections 25, 26, and 27 of the text.
  • Do problems 25.2, 25.5, 25.7, 26.2, 26.5, and 27.3
  • (Optional/Extra credit) Do problems 26.8, 26.9, 26.11
• (11) Due Monday, November 20:
  • Read sections 20 and 21 of the text.
  • Do problems 20.2, 20.5, 20.8, 21.2, and 21.5
  • (Optional/Extra credit) Do problems 20.9, 20.10, 21.4, or 21.6
• (10) Due Friday, November 10:
  • Read sections 17, 18, and 19 of the text.
  • Do problems 17.2, 17.4, 17.6, 17.8, 19.1, and 19.4
  • (Optional/Extra credit) Do any of the starred problems in sections 17 or 19
• (9) Due Friday, November 3:
  • Read sections 14, 15, and 16 of the text.
  • Do problems 14.2, 14.6, 15.2, 15.3, 15.6, 15.10, and 16.3
  • (Optional/Extra credit) Do problems 16.4 and 16.6
• (8) Due Friday, October 27:
  • Read sections 12 and 13 of the text.
  • Do problems 12.2, 12.5, 12.6, 12.8, 12.9, 12.13, 13.4, 13.5, 13.6, and 13.7
• (7) Due Friday, October 20:
  • Read section 24 of the text.
  • Do problems 24.3 and 24.4.
  • Consider the Markov chain with 5 vertices and the following transition probabilities: p₁₂=1/2, p₁₃=1/2, p₂₄=1, p₃₄=1, p₄₁=1/2, p₄₅=1/2, p₅₂=1, and all other p_ij=0.
    • Draw the corresponding weighted digraph.
    • Is this Markov chain irreducible?
    • What is the period of vertex v₁? (Prove that your answer is correct.)
  • (Optional/Extra credit) For the same Markov chain:
    • Find a stationary distribution
    • Prove that the powers of the transition matrix P do not converge to any matrix Q
• (6) Due Friday, October 13:
  • Read sections 22 and 23 of the text.
  • Do problems 22.4, 22.5, 22.7, 23.4, 23.5, 23.6, and 23.7.
  • (Optional/extra credit) Do problem 23.8.
• (5) Due Friday, September 29:
  • Read sections 10 and 11 of the text.
  • Do problems 10.3, 10.5, 10.7, 11.2, 11.4, 11.9, and 11.11.
• (4) Due Friday, September 22:
  • Read Section 9 of the text.
  • Do Problems 9.3, 9.5, 9.7, 9.9, 9.10, 9.11.
  • Find two distinct spanning trees in K₄ and for each of them find the corresponding fundamental sets of cycles and cutsets.
  • Find two distinct spanning trees in K_3,3 and for each of them find the corresponding fundamental sets of cycles and cutsets.
• (3) Due Friday, September 15:
  • Read Sections 6-8 of the text.
  • Do Problems 6.3, 6.6, 6.7, 7.3, 7.5, 7.7, 8.2, 8.3, 8.7.
• (2) Due Friday, September 8:
  • Read Section 5 of the text.
  • Do Problems 5.3, 5.6, 5.7, 5.8, 5.9, 5.11, 5.12, and 5.13.
  • Show that for all odd n≥1 there is a simple graph with (n²-1)/4 edges without triangles and for all even n≥2 there is a simple graph with n vertices and n²/4 edges without triangles. This shows that a result in class on Friday is best possible.
• (1) Due Friday, September 1:
  • Read Chapters 1 and 2 of the text.
  • Do Problems 1.5, 1.7, 2.2, 2.5, 2.11, 2.13, 2.14, 3.5, 3.8.
  • Prove that the graphs C_n, P_n, and W_n are connected.
  • (Optional/extra credit) Do problems 2.9, 3.9, and 3.10.