|
Study Guide
Tucker: Applied Combinatorics
§2.1 Euler Cycles
Dr. Lee Eimers
Revised 9-26-07 |
|
|
Introduction: Historically the subject of graph theory has its
origins in the popular problem known as the Spaziergangen problem of the
Seven Bridges of Konigsberg. This inspired Euler to develop the beginnings
of the subject of graph theory. This section gives this history and
an introduction to one of the questions considered in graph theory.
Concepts and Vocabulary:
The following boldfaced (or italic) terms and phrases introduced
in this section.
Euler cycle
Euler trail |
Multigraph
Seven Bridges of Konigsberg |
Points of Interest:
1. There is one theorem for Euler cycles in this section that
is quite obvious, but still is very useful. Know how to prove it,
by both of the ways given in the section.
2. The corollary given on the last page follows fairly directly
from the definition of trail.
Homework Assignment:
Do to hand in: #1, 2, 7, 10, 12, 14, 17, 19.
Enrichment problems: If you are into computers, you might want
to consider problems 20 and 21.
Otherwise anything from #13 to 19 would be okay.
Thought for the Day
"If Lincoln were alive today, he'd roll over in his grave."
-Gerald Ford-
"Look, son, I cannot conceive of any circumstances
that could draw out of me permission to consider me
for any political post from dogcatcher
to Grand High Supreme King of the Universe"
-Dwight D. Eisenhower, press conference, 1948