Geometric Structures
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 4
Graphs are geometric diagrams which consist of a set of points joined by line segments (curved or straight). Here are some examples:
The points are called vertices and the lines are called edges. Some authors allow vertices to be joined to themselves by an edge (loops) or pairs of vertices joined by several edges (multiple edges). The diagram below has one loop and there are two sets of multiple edges. The authors who do not allow loops and multiple edges usually (but not always) call graphs with multiple edges but no loops multigraphs and graphs with both loops and multiple edges pseudographs.
There are pros and cons to both points of view, with regard to allowing loops and multiple edges, as part of the definition of graph. Unfortunately, there is no universally agreed on terminology in the theory of graphs, though the subject was born in the 18th century. Part of the reason for this is that interest in the theory of graphs has exploded in the last 50 years and the different goals of different practitioners has affected the evolution of the subject.
A very important idea is that of the degree or valence of a vertex in a graph. The degree of a vertex is the number of "local" line segments at the vertex. Note that this means that a loop contributes two the degree of a vertex that it is located at. The numbers near the vertices in the graph below (Figure 3) are the valences or degrees of the vertices. Note that this graph only has 9 vertices. The point in the diagram where the edges joining vertices A and G, and F and H is NOT a vertex of the graph. When we draw diagrams of graphs in the plane if edges meet at points other than vertices I will refer to such points as "accidental" crossings. Since graphs are not metrical drawings often (but not always) accidental crossings can be eliminated. In the example, one can "stretch" the edge AG beyond H and get a new drawing which avoids this accidental crossing. (Figure 4) If we write down the sequence of degrees of the vertices in non-increasing order we get the degree sequence of the give graph. For the graph which appears below, its degree sequence is:
It is possible to have two non-isomorphic graphs which have the same degree sequence. Here is an example of a graph which has multiple edge which has the same degree sequence as a graph which does not have multiple edges:
(Both of these graphs have the degree sequence: 3, 3, 2, 2.)
It is, of course, possible to have two graphs which have no multiple edges or loops (sometimes called simple graphs) which have the same degree sequence but are isomorphic.
Theorem: If G is a graph then the sum of the degrees of all of the vertices of G is equal to twice the number of edges of G.
Proof:
Each edge which is not a loop is counted twice, once at each of its endpoints. The number of edges in loops are also counted twice because a loop contributes to the degree of the vertex is it located at.
Corollary: The number of vertices of a graph which are odd-valent is even.
It is easy to take a graph and write down its degree sequence. However, suppose one is given a finite sequence of nonnegative integers in non-increasing order. (For example: 6, 5, 5, 4, 4, 4, 4, 4, 4, 2, 2.) Is there are graph with this sequence as its degree sequence? An obvious necessary condition is that the number of odd-valent vertices in the sequence must be even. However, there are now theorems available to answer this question for the case that one has no loops or multiple edges. If loops and multiple edges are allowed it is not difficult to see that the answer is that the necessary condition is also sufficient.
Traversability
Many problems in operations research can be formulated as questions about traversing the edges of a graph in way that achieves a particular goal. For example, perhaps one wishes to inspect storm sewers for flooding after a storm. One might wish to visit each vertex of a graph once and only once, returning to the vertex where one started. In other problems, where services must be provided along edges of a graph, such as garbage collection, mail delivery, street sweeping, or grass cutting along the side of a road, one may wish to traverse each edge of a graph once and only once, returning to one the vertex one started at. To formulate and discuss such problems and their solutions one needs terminology. One approach to this is to refer to a tour as "closed" if it starts and ends at the same vertex, while one thinks as other tours, where one starts and ends at different vertices as open. If open or closed is not specified than the tour might be open or closed. Closed paths will be called circuits.
walk (edges and vertices can be repeated)
trail (vertices but not edges can be repeated)
path (neither edges nor vertices are repeated)
Note: traversability terminology is definitely not standardized.
6, 4, 5, 4, 3, 0, 3 is a walk; 6, 4, 5, 3, 4, 6 is a closed walk.
3, 2, 7, 8, 2, 0 is a trail; 3, 2, 7, 8, 2, 0, 3 is a closed trail
1, 3, 4, 5 is a path; 1, 3, 2, 0, 1 is a circuit. (Note: 3, 2, 0, 1, 3 is the same circuit.)