|
Study Guide
Tucker: Applied Combinatorics
§1.2 Isomorphism
Dr. Lee Eimers
revised 9-5-07 |
|
|
Introduction: The question in this section is: When are two graphs
equivalent? We will learn some conditions that must be satisfied
for this to be true.
Concepts and Vocabulary:
The following boldfaced (or italic) terms and phrases introduced
in this section.
Complement graph
Complete graph on n vertices
Degree of a vertex |
In-degree
Isolated vertices
Isomorphic |
Isomorphism
Out-degree
Subgraph |
Points of Interest:
1. Basically, each time you consider the question of
whether two graphs are isomorphic, you must start from scratch and consider
the unique features of whatever graphs you are looking at.
2. Simple things that must match include number of vertices, number
of edges, number of vertices of each degree, and (for directed graphs only)
in-degree and out-degree.
3. Sometimes it is simpler to consider the complement graphs.
Usually this will help only if the complement graph has fewer edges than the original.
4. You have to be careful how you pair up the vertices.
The graphs may appear non-isomorphic with one pairing, but actually be
isomorphic with a different pairing of the vertices.
Homework Assignment:
Required Reading:
Chapter 1, Section 2 of text
Graph Theory Lessons, Lesson 3: Isomorphism
Graph Theory Lessons, Lesson 4: Complete Graphs, Subgraphs
Graph Theory Lessons, Lesson 15: Complements
Bondy and Murty, pp. 4-7;
Do to hand in:#5a,c,e,g,i only, 6, 7, 9, 10, 13, 14 (from text)
Enrichment problems: Anything from #8 to the end not assigned or
already done in class.
Thought for the Day
If you have run with the footmen,
and they have wearied you,
Then how can you contend with horses?
(Jer. 12:4a, NKJV)
References:
Graph Theory with Applications, by J. A. Bondy and U. S. R. Murty,
Online text found at http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html
Graph Theory Lessons, by Christopher Mawata,
found at http://www.utc.edu/Faculty/Christopher-Mawata/petersen/index.htm