|
Study Guide
Tucker: Applied Combinatorics
§1.1 Elements of Graph Theory
Dr. Lee Eimers
Revised 8/31/07 |
|
|
Introduction: In this section, we begin our study of one of the two
main topics of discrete math, that of graph theory. We meet some of
the basic concepts and look at some of the types of problems that can be
posed and solved by using graphs. (The other main topic of discrete math
is combinatorics, which is the other half of the text and has its own course.)
Concepts and Vocabulary:
The following boldfaced (or italic) terms and phrases introduced in
this section.
(* indicates not defined in text)
Adjacent vertices
Bipartite graph
Chordal graph*
Circuit |
Directed edges
Edges
Graph
Indifference graph*
Path |
Tree
Unit-interval graph*
Vertex basis
Vertices |
Points of Interest:
1. The first couple of pages contain the basic definitions.
The remainder of the section consists of examples, although additional new
concepts are introduced in the examples, too, so don't skip over them.
2. There are some interesting issues related to indifference
graphs and preferences. We will talk about some of them in class.
3. There are many more examples of uses of graphs found in the problems.
It would be good if you would read through the problems that we don't work
just to get a better idea of some of these applications.
Homework Assignment:
Required Reading:
Chapter 1, Section 1 of text
Bondy and Murty, pp. 1-4;
Diestel, pp. 1-4;
Graph Theory Lessons, Lesson 9: Bipartite Graphs
Do to hand in: #1, 4, 7, 10, 15, 16, 23, 25, 27 (from text)
Enrichment problems: Anything not previously done in class, but ask me
first. Some of the problems are not really worth counting for enrichment
credit. If you happen to choose to do one of them to work, it will
not receive extra credit.
Thought for the Day
Definitions:
College professor: A man who is paid to study sleeping conditions
among students.
College English department: A chamber of commas.
College education: A form of training which does not hurt you
provided you study and work hard after graduation.
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, 3rd Ed., by R. Diestel,
Online text found at http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/