A graph is a finite set of vertices (dots) connected by edges.Theorem: The sum over all vertices of the degrees = 2 * number of 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?
Euler's Theorem 1: Suppose that G is a connected graph. Equivalent:Can you draw a graph with 5 vertices where the degree of each vertex is 3?A path is a connected sequence of edges.
(Hint: What would be the sum over all the vertices of the degrees?)Give a path in the graph from A to DA 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.
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:
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
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