Print bookPrint book

Try It Now

Site: Saylor Academy
Course: CS202: Discrete Structures
Book: Try It Now
Printed by: Guest user
Date: Friday, April 19, 2024, 7:30 AM

Description

Work these exercises to see how well you understand this material.

Table of contents

Exercises

  1. Locate a map of New York City and draw a graph that represents its landmasses, bridges, and tunnels. Is there an Eulerian path through New York? You can do the same with any other city that has at least two landmasses.

  2. Write out the Gray Code for the 4-cube.

  3. The Euler Construction Company has been contracted to construct an extra bridge in Koenigsberg so that an Eulerian path through the town exists. Can this be done, and if so, where should the bridge be built?

  4. Formulate Euler's theorem for directed graphs.

  5. Prove that the number of vertices in an undirected graph with odd degree must be even. Hint. Prove by induction on the number of edges.

    1. Under what conditions will a round-robin tournament graph be Eulerian?
    2. Prove that every round-robin tournament graph is Hamiltonian.

 

Source: Al Doerr and Ken Levasseur, http://faculty.uml.edu/klevasseur/ads-latex/ads.pdf
Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.

Solutions

  1. Answer: Using a recent road map, it appears that an Eulerian circuit exists in New York City, not including the small islands that belong to the city. Lowell, Massachusetts, is located at the confluence of the Merrimack and Concord rivers and has several canals flowing through it. No Eulerian path exists for Lowell.

  2. Answer: Gray Code for the 4-cube:

    G_4 = \begin{pmatrix} 0000\\  0001\\  0011\\  0010\\  0110\\  0111\\  0101\\  0100\\ 1100\\ 1101\\  1111\\  1110\\  1010\\ 1011\\ 1001\\ 1000 \end{pmatrix}

  3. Answer: Any bridge between two landmasses will be sufficient. To get an Eulerian circuit, you must add a second bridge that connects the two landmasses that were not connected by the first bridge.

  4. Answer: Let G = (V, E ) be a directed graph. G has an Eulerian circuit if and only if G is connected and indeg(v) = outdeg(v) for all v ∈ V. There exists an Eulerian path from v1 to v2 if and only if G is connected, indeg(v1) = outdeg(v1) − 1, indeg(v2) = outdeg(v2) + 1, and for all other vertices in V the indegree and outdegree are equal.

  5. Hint: Prove by induction on the number of edges.

  6. Answer: A round-robin tournament graph is rarely Eulerian. It will be Eulerian if it has an odd number of vertices and each vertex (team) wins exactly as many times as it loses. Every round-robin tournament graph has a Hamiltonian path. This can be proven by induction on the number of vertices.