Figure 1
Geometric Structures: Basic Graph Theory
Prepared by:
Joseph Malkevitch
Department of Mathematics
York College (CUNY)
Jamaica, New York 11451
email:
malkevitch@york.cuny.edu
web page:
http://york.cuny.edu/~malk/
Session 5
Having looked at some basic terminology about how to "tour" edges in a graph we have a way to distinguish between graphs that consist of one piece from those that have several pieces or components. A graph G is called connected if given any two vertices of G there is a path between these two vertices. For most problems one can work with a connected graph.
Graph theory is rich in both pure and applied problems. There is a rich literature on traversability problems for graphs. Edge traversability problems come up in operations research problems involving snow removal, mail delivery, street sweeping, and garbage collection. These problems are often referred to as Eulerian circuit or chinese postman problems. Vertex traversal problems arise in situations such as:
*picking up children and taking them to school or day camp
*airport limo pickup and drop off
*package delivery services
*pickup of coins from pay phone booths
*pickup of backup paper records from ATM machines
*meals on wheels programs for the elderly
These kinds of questions are known as traveling salesman problems. They are typically solved in weighted graphs (e.g. a cost is assigned to every edge of the graph) and involve finding a minimum cost circuit what visits each vertex of the graph once and only once.
Even at a slight abuse of language the following terminolgy is widely used:
a. Eulerian circuit: A tour of the edges of a connected graph which visits each edge once and only once and returns to the vertex where the tour started
(Euler founded graph theory in 1736 with a discussion of the Konigburg bridge problem, which involved what today are known as Eulerian circuits.)
Theorem:
A connected graph has an Eulerian circuit if and only if all its vertices are even-valent.
This lovely theorem is constructive in the sense that to find an Eulerian circuit one can piece together cirucits in the even-valent graph which share a vertex.
Since graphs typically do not always have even-valent vertices, for applications this problem is generalized to the case of weighted connected graphs.
Chinese postman problem:
Find the closed walk in a connected graph which visits each edge at least once and with minimal cost.
b. Hamiltonian circuit: A tour of the vertices of a connected graph which visits each vertex once and only once and returns to where it started.
Unfortunately, the problem of finding Hamiltonian circuits in graphs, unlike that of find Eulerian circuits, is not easy. Although Hamiltonian circuits are known to exist for a variety of special classes of graphs, the problem of finding Hamiltonian circuits in planar (graphs which can be drawn on a piece of flat paper so that edges meet only at vertices) 3-valent graphs is NP-complete. (This means that as the number of vertices of such a graph grows there is no known polynomial time algorithm for finding a Hamiltonian circuit, nor a proof that an exponential time algorithm is required to find a Hamiltonian circuit.
Special classes of graphs
Many special classes of graphs (trees, complete graphs, intersection graphs) arise both in applications and for theoretical reasons. They provide teachers with many examples of "connections" between otherwise seemingly different areas of mathematics. For example, in connection with the fundamental principle of counting (e.g. if one has 5 skirts and 4 blouses one can wear 20 different outfits) one can illustrate this result using a tree. A tree is a connected graph which has not vertices. Examples of trees appear in Figure 1 below.
Except for the (trivial) tree consisting of a single vertex any tree will have 1-valent vertices. This can be seen by noting that if a tree has at least two vertices, and one picks any vertex v, the vertex f in the tree which is farthest from v must be 1-valent. (The distance between two vertices in a connected graph is the length of the shortest path (e.g. fewest edges) between them.)
Another beautiful and important property of trees is that the number of vertices (V) in a tree is always one more than the number of edges (E) in a tree:
V= E + 1
This fact can be proved using mathematical inducation on the number of vetices in the graph. (Hint: Us the fact that a tree other than the one with a single vertex has 1-valent vertices.)
Here are some of the properties of trees that are appealing:
a. If v and w and distinct vertices of a tree there is a unique path from v to w.
b. If e is any edge of a tree T then removing e from T (removing an edge from a graph involves erasing the edge but leaving behind its endpoint vertices) disconnects the tree.
c. If v and w are vertices that are not already joined by an edge then adding the edge vw (which is the same as edge wv) to the tree creates exactly one circuit