I really do find these interesting - they are like puzzles in a way. It is amazing that some people's brains can see the paths very easily and others (like me) have to work a little harder. I think people with good spatial skills (or who are gifted in the "non-verbal" area) tend to solve these quite quickly. Good thing that my kids took after their dad in this area. ;)
Here are a few links to help explain Euler Circuits and Paths -
An Introduction to Euler Circuits and Paths
The Seven Bridges of Konigsberg (extension idea - try eliminating a bridge to see if you can make a Euler Path or Circuit)
There are lots of ways to apply Euler Circuits and Paths in real life. This website looked at the game Ticket to Ride to examine if there were any Euler Circuits and Paths (spoiler alert - there are none).
Leonhard Euler lived from 1707 to 1783 and was a Swiss mathematician (one of the greatest of all time). Euler spend a lot of his career working at the Berlin Academy in Germany. He became famous when he was given "The Seven Bridge of Konigsberg" question to solve.
Here's some information from my study sheet:
EULER’S THEOREMS
Euler’s Theorem 1 - If a graph has any
vertices of odd degree, then it CANNOT have an EULER CIRCUIT AND If a graph is connected
and every vertex has even degree, then it has AT LEAST ONE EULER CIRCUIT
(usually more).
Euler’s Theorem 2 - If a graph has more than
2 vertices of odd degree, then it CANNOT have an EULER PATH AND If a graph is connected
and has exactly 2 vertices of odd degree, then it has AT LEAST ONE EULER PATH
(usually more). Any such path must start at one of the odd-degree vertices and
end at the other.
Euler’s Theorem 3 - The sum of the degrees of
all the vertices of a graph is an even number (exactly twice the number of
edges).
In every graph, the
number of vertices of odd degree must be even.
Keep in
mind:
*An Euler Circuit IS a type of Euler Path
but an Euler Path is not necessarily an Euler Circuit.
*The sum of the degrees of all the vertices of a graph is
twice the number of edges.
*The number of vertices of odd degree must be even.
Connected Graph:
-A vertex-edge graph is connected if there is a path
between all pairs of vertices.-If a path does NOT exist between all pairs of vertices, then the graph is disconnected.
-The # of edges that meet at a vertex in a vertex-edge graph
- If there are an even # of edges that meet at a vertex, then the degree of the vertex is even.
-If there are an odd # of edges that meet at a vertex, then the degree of the vertex is odd.
Degree of a Vertex:
-The # of edges that meet at a vertex in a vertex-edge
graph
- If there are an even # of edges that meet at a vertex,
then the degree of the vertex is even.
-If there are an odd # of edges that meet at a vertex,
then the degree of the vertex is odd.
My double bubble map (yes, I know I am nerdy to do this at home but it is how I think)...
Here's a simple chart to remember if something is an Euler Path or an Euler Circuit...
As a high school math teacher who is currently teaching this unit, I would say you did a great job on your "cheat sheet." :-)
ReplyDelete