Urban Services

Definitions:

A graph is a finite set of vertices (dots) connected by edges.
The degree (valence) of a vertex is the number of edges incident to the vertex.
can you have a graph with these vertex degrees:     5, 4, 3, 2, 1, 0?
or with these                                                          5, 3, 3, 3, 3, 3?
        What is the sum over all the vertices of the degrees? What is the total number of edges in the graph?
Can you draw a graph with 6 vertices where the degree of each vertex is 5?
        What is the sum over all the vertices of the degrees? What is the total number of edges in the graph?

Theorem: The sum over all vertices of the degrees = 2 * number of edges.

Can you draw a graph with 5 vertices where the degree of each vertex is 3?
(Hint: What would be the sum over all the vertices of the degrees?)
A path is a connected sequence of edges.
Give a path in the graph from A to D
A graph is connected if and only if for every pair of vertices there is a path in the graph between them.
A circuit (cycle) is a path that starts and ends at the same point.
An Eulercircuit is a circuit that traverses each edge exactly once.

Koenigsberg Bridge Problem: take a walk that traces every edge exactly once.

Euler's Theorem 1: Suppose that G is a connected graph. Equivalent:

All vertices in G have even degree.
G has an Eulercircuit.

Does the graph in the military example have an Euler circuit?

How to find an Eulercircuit for this graph?

Algorithm idea: never use an edge that is the only link between two parts of the graph that still need to be traversed.

Mail delivery: Each line represents a street, each dot represents a house. Deliver mail to each house.
Mathematically equivalent question: Does this graph have an Eulercircuit?

An Eulerpath is a path that traverses each edge exactly once, and is not a circuit.

Euler's Theorem 2: Suppose G is a connected graph. Equivalent:

All but two vertices in G P, Q have even degree.
G has an Eulerpath starting at P and ending at Q.

Example: You snow plow the neighborhood where the street map looks like this:

Apparently you have to go through certain streets twice. Find a way that would minimize the number of streets that you have to pass through more than once.

To Eulerize a graph is to add edges to a graph so that it then has an Eulercircuit.

Eulerize the Graph to Solve Chinese Postman Problem

For graphs that are connected but have vertices with odd valence, we will want to reuse (duplicate) the minimum number of edges until all vertices appear to have even valence.
Only existing edges can be duplicated (or added).
Each edge that is duplicated (added) will later be the edge that will be reused during eulerization.

Example: A snow plowing company has a contact for clearing the following street grid. The length of the roads in the middle section are 400m, whereas all the other road segments are 100m. Find a good Eulerization of this grid.

Real life scenarios involving EulerCircuits, Eulerpaths, Eulerizations:
- whenever you have to check every segment, such as:

roads
powerlines
water pipes
sewer system
telephone landlines
transportation systems