Graph Theory

Graph Theory

2.0 1
by Ronald Gould
     
 

View All Available Formats & Editions

An introductory text in graph theory, this treatment covers primary techniques and includes both algorithmic and theoretical problems. Algorithms are presented with a minimum of advanced data structures and programming details. This thoroughly corrected 1988 edition provides insights to computer scientists as well as mathematicians studying topology, algebra, and… See more details below

Overview

An introductory text in graph theory, this treatment covers primary techniques and includes both algorithmic and theoretical problems. Algorithms are presented with a minimum of advanced data structures and programming details. This thoroughly corrected 1988 edition provides insights to computer scientists as well as mathematicians studying topology, algebra, and matrix theory.

Product Details

ISBN-13:
9780486320366
Publisher:
Dover Publications
Publication date:
08/30/2013
Sold by:
Barnes & Noble
Format:
NOOK Book
Pages:
352
Sales rank:
1,285,250
File size:
12 MB
Note:
This product may take a few minutes to download.

Read an Excerpt

Graph Theory


By Ronald Gould

Dover Publications, Inc.

Copyright © 2012 Ronald Gould
All rights reserved.
ISBN: 978-0-486-32036-6



CHAPTER 1

Graphs


Section 1.0 Introduction

For years, mathematicians have affected the growth and development of computer science. In the beginning they helped design computers for the express purpose of simplifying large mathematical computations. However, as the role of computers in our society changed, the needs of computer scientists began affecting the kind of mathematics being done.

Graph theory is a prime example of this change in thinking. Mathematicians study graphs because of their natural mathematical beauty, with relations to topology, algebra and matrix theory spurring their interest. Computer scientists also study graphs because of their many applications to computing, such as in data representation and network design. These applications have generated considerable interest in algorithms dealing with graphs and graph properties by both mathematicians and computer scientists.

Today, a study of graphs is not complete without at least an introduction to both theory and algorithms. This text will attempt to convince you that this is simply the nature of the subject and, in fact, the way it was meant to be treated.


Section 1.1 Fundamental Concepts and Notation

Graphs arise in many settings and are used to model a wide variety of situations. Perhaps the easiest way to adjust to this variety is to see several very different uses immediately. Initially, let's consider several problems and concentrate on finding models representing these problems, rather than worrying about their solutions.

Suppose that we are given a collection of intervals on the real line, say C = {I1, I2, ..., Ik}. Any two of these intervals may or may not have a nonempty intersection. Suppose that we want a way to display the intersection relationship among these intervals. What form of model will easily display these intersections?

One possible model for representing these intersections is the following: Let each interval be represented by a circle and draw a line between two circles if, and only if, the intervals that correspond to these circles intersect. For example, consider the set

C = {[-4, 2], [0, 1], (-8, 2], [2, 4], [4, 10)}.


The model for these intervals is shown in Figure 1.1.1.

Next, we consider the following old puzzle. Suppose there are three houses (call them h1, h2 and h3) and three utility companies (say gas (g), water (w) and electricity (e)). Our problem is to determine if it is possible to connect each of the three houses to each of the three utilities without crossing the service lines that run from the utilities to the houses. We model this puzzle by representing each house and each utility as a circle and drawing a line between two circles if there is a service line between the corresponding house and utility. We picture this situation in Figure 1.1.2. A solution to this problem would be a drawing in which no lines crossed. The drawing of Figure 1.1.2 is not a solution to the problem, but merely an attempt at modeling the problem.

In our third problem, suppose you are the manager of a company that has four job openings (say j1, j2, j3 and j4) and five applicants a1, ..., a5 and that some of these applicants are qualified for more than one of your jobs. How do you go about choosing people to fill the jobs so that you will fill as many openings as possible? We picture such a situation in Figure 1.1.3. Again, each job and each applicant can be represented as a circle. This time, a line is drawn from a circle representing an applicant to each of the circles representing the jobs for which the applicant is qualified. A solution to this problem would be a set of four lines joining distinct jobs to distinct applicants, that is, one line joins each job to a distinct applicant. For example, the lines joining j1 and a2, j2 and a1, j3 and a4 and j4 and a5 constitute a solution to this problem. Since lines only join jobs to applicants, this is clearly the maximum number of lines possible. Can you find another solution? The real problem is how can we find solutions in general?

Despite the fact that these problems seem very different, we have used a similar type of diagram to model them. Such a diagram is called a graph. Formally, a graph G = (V, E) is a finite nonempty set V of elements called vertices, together with a set E of two element subsets of V called edges. In our example diagrams, each circle is a vertex and each line joining two vertices is an edge. If the context is not clear, we will denote V or E by V (G) or E (G), respectively, to show they come from the graph G. In Figure 1.1.2, the vertices are h1, h2, h3, g, w, e and the edges are

{h1, g}, {h1, e}, {h1, w}, {h2, g} {h2, e}, {h2, w}, {h3, e}, {h3, g}, {h3, w}.


For simplicity, we will usually denote edges by consecutively listing the vertices at either end. For example, the edge {h1, g} would be denoted h1g or gh1.

One of the beauties of graphs is that they may be thought of in many ways: formally as set systems, geometrically as the diagrams we have presented and algebraically, as we shall see later. Such diverse representations afford us an opportunity to use many tools in studying graphs and to apply graph models in many ways. To do this effectively, of course, we need to build more terminology and mathematical machinery.

Given a graph G = (V, E), the number of vertices in V is called the order of G and the number of edges in E is called the size of G. They shall be denoted as | V | and | E |, respectively. The interval graph of Figure 1.1.1 has order 5 and size 6. If a graph G has order p and size q, we say G is a (p, q) graph. Two vertices that are joined by an edge are said to be adjacent, as are two edges that meet at a vertex. If two vertices are not joined by an edge, we say they are nonadjacent or independent. Similarly, two edges that do not share a common vertex are said to be independent. The set of all vertices adjacent to a vertex v is called the neighborhood of v and is denoted N (v). An edge between vertices u and v is said to have u (or v) as an end vertex. Further, the edge is said to be incident with v (or with u) and v is said to dominate u (also, u dominates v). The number of edges incident with a vertex v is called the degree of v and is denoted deg v or by degG v if we wish to emphasize that this occurs in the graph G. The minimum degree and maximum degree of a vertex in the graph G are denoted by δ(G) and Δ(G), respectively. A graph in which each vertex has degree r is called an r-regular graph (or simply regular). We now present the theorem traditionally called The First Theorem of Graph Theory.

Theorem 1.1.1 Let G be a (p, q) graph and let V = {v1, v2, ..., vp}. Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Consequently, any graph contains an even number of vertices of odd degree.

Proof. Since each edge has exactly two end vertices, the sum of the degrees counts each edge exactly twice. Thus, the sum is obtained. Since 2q is even, an even number of vertices of odd degree must then be present in the sum.


We have considered three problems thus far. The drawing of Figure 1.1.1 is a solution to the first problem, and we have an idea of what a solution for one example of the third problem looks like. But the drawing given for the utilities problem does not provide a solution to that problem. This does not mean there is no solution, only that our drawing fails to provide one. What if we try other drawings (see Figure 1.1.4)? One of the interesting features of these drawings is the freedom we have to shape them. There are no restrictions on the size of the vertices or on the length or even the shape of the edges. These drawings are very much free-form. We are also free to choose an entirely different representation for our graph, for example the set representation we used in defining graphs. But this freedom also presents us with some difficulties. If a graph is presented in different ways, how can we determine if the presentations really represent the same graph?

Mathematicians use the term isomorphism to mean the "fundamental equality" of two objects or systems. That is, the objects really have the same mathematical structure, only nonessential features like object names might be different. For graphs, "fundamentally equal" means the graphs have essentially the same adjacencies and nonadjacencies. To formalize this concept further, we say two graphs G1 and G2 are isomorphic if there exists a 1-1 and onto function f: V (G1) ->V (G2) such that xy [member of] E (G1) if, and only if, f (x) f (y) [member of] E (G2) (that is, f preserves adjacency and nonadjacency). We use the function f to express the correspondence between vertices that are "essentially the same" in the two graphs. The function f is called an isomorphism.

Example 1.1.1 The two drawings of the house-utilities graph are again shown in Figure 1.1.5. An isomorphism between G1 and G2 is determined by the function f: V (G1) ->V(G2) where:

f(a) = x, f(b) = r, f(c) = y, f(d) = s, f(e) = z, f(g) = t.


An isomorphism from G2 to G1 is given by f-1, the inverse of f.

Can you find other isomorphisms from G1 to G2?


A subgraph of G is any graph H such that V (H) [subset or equal to] V (G) and E (H) [subset or equal to] E (G); we also say G contains H. If H is a subgraph of G and V (H) = V (G), we say that H is a spanning subgraph of G. A more restricted but often very useful idea is the following: Given a subset S of V (G), the subgraph induced by S, denoted , is that graph with vertex set S and edge set consisting of those edges of G incident with two vertices of S.

The graphs in Figure 1.1.6 illustrate these ideas. Since V (H) = V (G), H is a spanning subgraph of G. Also, I is an induced subgraph of G since all edges of G with both end vertices in V (I) are contained in I. However, J is not an induced subgraph of G since the edge from 1 to 5 is in G, but is not in J.

Several natural and useful variations on graphs will be helpful. The first is the idea of a multigraph, that is, a graph with (possibly) multiple edges between vertices. A pseudograph allows edges that begin and end at the same vertex (called a loop). If we think of the edge between two vertices as an ordered pair rather than a set, a natural direction from the first vertex of the pair to the second can be associated with the edge. Such edges will be called arcs (to maintain the historical terminology), and graphs in which each edge has such a direction will be called directed graphs or digraphs. For digraphs, the number of arcs directed away from a vertex v is called the outdegree of v (denoted od v) and the number of arcs directed into a vertex v is the indegree of v (denoted id v). Often, for emphasis, we denote the arc directed from u to v as u ->v. In a digraph, we define the degree of a vertex v to be deg v = id v + od v. If u ->v is an arc of the digraph, we say that u dominates v and that v is dominated by u. Sometimes we say u is adjacent to v or v is adjacent from u.

Clearly, we can produce even more variations such as pseudodigraphs, multidigraphs and pseudomultidigraphs. Although these will not play as significant a role in our study of graphs, at times they will be useful. In this text we will be sure the reader understands the kind of graph under consideration, and the term graph will always be as we defined it: finite order, without loops, multiple edges or directed edges.


Section 1.2 Elementary Properties and Operations

A quick inspection of a road map of the southern states shows several important cities and the interstates that connect them. We model a portion of this map in Figure 1.2.1.

It seems natural to think of a graph (or digraph) when trying to model a road system. Vertices represent cities, and edges (or arcs) represent the roads between the cities. In tracing the route from one location to another, we would traverse some sequence of roads, beginning at some starting point, and finally reaching our destination. For example, we could travel from Atlanta to Nashville by first leaving Atlanta and traveling along I75 to Chattanooga, then following I24 to Nashville. Such a model leads us naturally to formally define the following concepts.

Let x and y be two vertices of a graph G (not necessarily distinct vertices). An x - y walk in G is a finite alternating sequence of vertices and edges that begins with the vertex x and ends with the vertex y and in which each edge in the sequence joins the vertex that precedes it in the sequence to the vertex that follows it in the sequence. For example, in the graph of Figure 1.2.1, one b - n walk is

b, I59, c2, I75, a, I20, b, I59, c2, I24, n


while another is

b, I20, a, I85, c1, I85, a, I75, c2, I24, n.


The number of edges in a walk is called the length of the walk. Note that repetition of vertices and edges is allowed. Ordinarily, we will use a more compact notation for a walk by merely listing the vertices involved, noting that the edge between consecutive vertices (at least in a graph or digraph) is then implied. We will only use the full notation for walks in multigraphs, where there is a choice of edges and this choice is important, or for emphasis of the edges involved. An x - y walk is closed if x = y and open otherwise. Two walks are equal if the sequences of vertices and edges are identical.

Several stronger types of walks are also important. An x - y trail is an x - y walk in which no edge is repeated, and an x - y path is an x - y walk in which no vertex is repeated, except possibly the first and the last (if the path is closed). Clearly, a path is also a trail. We consider a single vertex as a trivial path (walk or trail). In the graph of Figure 1.2.1, we see that a, b, a, c2, b, is an a - b walk of length 4, while a, b, c2, a, c1 is an a - c1 trail of length 4, and a, c2, n, m is an a - m path of length 3.


(Continues...)

Excerpted from Graph Theory by Ronald Gould. Copyright © 2012 Ronald Gould. Excerpted by permission of Dover Publications, Inc..
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.

Read More

Customer Reviews

Average Review:

Write a Review

and post it to your social network

     

Most Helpful Customer Reviews

See all customer reviews >