Exam 1: Urban Services

If a graph had four vertices of odd valence, then we can duplicate two edges to eulerize the graph.

Consider the paths represented by the numbered sequence of edges on the graphs below. Which path represents an Euler circuit?

For the street network shown below, which graph would be most useful for routing a garbage truck? Assume all streets are two-way and that passing down a street once would be sufficient to collect from both sides.

Consider the path represented by the numbered sequence of edges on the graph below. Which statement is true?

A graph must have even number of vertices of odd valence.

Consider the path represented by the numbered sequence of edges of the graph below. Which statement is true?

Which of the following defines the valence of vertex A of a graph?

Consider the path represented by the sequence of numbered edges on the graph below. Explain why the path is NOT an Euler circuit.

Which of the graphs below have Euler circuits?

Can a graph with five vertices have vertices with valences 1, 2, 3, 4 and 5?

Use the following to answer Questions: Identify an Euler circuit on the following graphs by numbering the sequence of edges in the order traveled. -

For which of the two situations below is it desirable to find an Euler circuit or an efficient eulerization of a graph? I. A pizza delivery person takes pizzas to 10 houses in a neighborhood and then returns to pick up the next set to be delivered. II) A postal carrier picks up mail from six collection boxes around a city.

Suppose the edges of a graph represent streets that must be checked by a worker from the Department of Public Works. In order to eulerize the graph, we must add three edges. The real world interpretation of this is:

The map shown below illustrates part of a postal carrier's territory. The dots indicate mailboxes to which mail must be delivered. Which graph would be most useful for finding an efficient route for mail delivery?

If a graph had 16 vertices of odd valence, what is the absolute minimum number of edges that would need to be added (duplicated) to eulerize the graph?

For which of the two situations below is it desirable to find an Euler circuit or an efficient eulerization of a graph? I. Plowing the streets of a small village after a snow. II) Painting the lines down the center of the roads in a town with only two-way roads.

For the street network shown below, draw a graph that would be useful for routing a garbage truck. Assume all streets are two-way and that passing once down the street is sufficient for collecting trash from both sides.

Which of the graphs shown below gives the best eulerization of the given graph? (In the graphs below, added edges are denoted with zigzag lines.)

Consider the paths represented by the numbered sequence of edges on the graphs below. Which path represents an Euler circuit?

Which of the graphs below have Euler circuits?