The Fascinating World of Graph Theory
344
The Fascinating World of Graph Theory
344eBookCourse Book (Course Book)
Available on Compatible NOOK devices, the free NOOK App and in My Digital Library.
Related collections and offers
Overview
The history, formulas, and most famous puzzles of graph theory
Graph theory goes back several centuries and revolves around the study of graphs—mathematical structures showing relations between objects. With applications in biology, computer science, transportation science, and other areas, graph theory encompasses some of the most beautiful formulas in mathematics—and some of its most famous problems. The Fascinating World of Graph Theory explores the questions and puzzles that have been studied, and often solved, through graph theory. This book looks at graph theory's development and the vibrant individuals responsible for the field's growth. Introducing fundamental concepts, the authors explore a diverse plethora of classic problems such as the Lights Out Puzzle, and each chapter contains math exercises for readers to savor. An eye-opening journey into the world of graphs, The Fascinating World of Graph Theory offers exciting problem-solving possibilities for mathematics and beyond.
Product Details
| ISBN-13: | 9781400852000 |
|---|---|
| Publisher: | Princeton University Press |
| Publication date: | 01/18/2015 |
| Sold by: | Barnes & Noble |
| Format: | eBook |
| Pages: | 344 |
| Sales rank: | 543,450 |
| File size: | 10 MB |
About the Author
Read an Excerpt
The Fascinating World of Graph Theory
By Arthur Benjamin, Gary Chartrand, Ping Zhang
PRINCETON UNIVERSITY PRESS
Copyright © 2015 Princeton University PressAll rights reserved.
ISBN: 978-1-4008-5200-0
CHAPTER 1
Introducing Graphs
The mathematical structure known as a graph has the valuable feature of helping us to visualize, to analyze, to generalize a situation or problem we may encounter and, in many cases, assisting us to understand it better and possibly find a solution. Let's begin by seeing how this might happen and what these structures look like.
FIRST, ... FOUR PROBLEMS
We begin with four problems that have a distinct mathematical flavor. Yet any attempt to solve these problems doesn't appear to use any mathematics you may have previously encountered. However, all of the problems can be analyzed and eventually solved with the aid of a relatively new sort of mathematical object and that object is a graph. The graph we're referring to is not the kind of graph you've seen before. For example, Figure 1.1 shows the graph of the function y = sin x. That is not the kind of graph we're referring to.
The Problem of the Five Princes
Once upon a time, there was a kingdom ruled by a king who had five sons. It was his wish that upon his death, this kingdom should be divided into five regions, one region for each son, such that each region would have a common boundary with each of the other four regions. Can this be done?
Figure 1.2 illustrates an unsuccessful attempt to satisfy the king's wishes. Every two of the five regions, numbered 1, 2, 3, 4, 5, share some common boundary, except regions 4 and 5.
If the kingdom can be divided into five regions in the manner desired by the king, then something else would have to be true. Place a point in each region and join two points by a line or curve if the regions containing these points have a common boundary. If A and B are two adjacent regions in the kingdom and C and D are two other adjacent regions, then it's always possible to connect each pair of points by a line in such a way that these two lines don't cross.
What we have just encountered is a graph (our type of graph) for the first time. A graph G is a collection of points (called vertices) and lines (called edges) where two vertices are joined by an edge if they are related in some way. In particular, the division of the kingdom into the five regions shown in Figure 1.2 gives rise to the graph G shown in Figure 1.3.
In order to have a solution to the king's wishes, the resulting graph must have five vertices, every two joined by an edge. Such a graph is called a complete graph of order 5 and expressed as K5. Furthermore, it must be possible to draw K5 without any of its edges crossing. Since there is no edge joining vertices 4 and 5 in Figure 1.3, the division of the kingdom into regions shown in Figure 1.2 does not represent a solution. In Chapter 10 we will visit the Problem of the Five Princes again when we will be able to give a complete solution to this problem.
The Three Houses and Three Utilities Problem
Three houses are under construction and each house must be provided with connections to each of three utilities, namely water, electricity and natural gas. Each utility provider needs a direct line from the utility terminal to each house without passing through another provider's terminal or another house along the way. Furthermore, all three utility providers need to bury their lines at the same depth underground without any lines crossing. Can this be done?
Figure 1.4 shows a failed attempt to solve this problem, where the three houses are labeled A, B and C. Not only can this problem be looked at in terms of graphs, but in terms of graphs this problem is extremely similar to the Problem of the Five Princes. We can represent this situation by a graph with six vertices, three representing the three houses A, B and C and three representing the three utilities water (W), electricity (E) and natural gas (NG). Two vertices are joined by an edge when one vertex represents a house and the other represents a utility. This graph then has nine edges. This graph is denoted by K3,3, indicating that there are two sets of three vertices each where each vertex in one set is joined to all vertices in the other set. To solve the Three Houses and Three Utilities Problem, we need to know whether K3,3 can be drawn without any edges crossing. The attempted solution of the Three Houses and Three Utilities Problem in Figure 1.4 gives rise to the graph shown in Figure 1.5.
We will visit the Three Houses and Three Utilities Problem as well in Chapter 10 and explain how to solve the problem.
In our next problem a graph will be introduced whose vertices represent people. Here we assume every two people are friends or strangers.
The Three Friends or Three Strangers Problem
What is the smallest number of people that must be present at a gathering to be certain that among them three are mutual friends or three are mutual strangers?
Here too the situation can be represented by a graph, in fact by a complete graph. Suppose that four people are present at a gathering. Then we have a graph with four vertices, corresponding to the four people. We join every two vertices by an edge to indicate that these two people are friends or are strangers, resulting in the complete graph K4 with four vertices and six edges. To indicate whether two people are friends or are strangers, we color the edge red (r) if the two people are friends and color the edge blue (b) if the two people are strangers. Thus three mutual friends would be represented by a red triangle in our graph and three mutual strangers would be represented by a blue triangle. The situation shown in Figure 1.6a shows that with four people it is possible to avoid having three mutual friends or three mutual strangers. Likewise, when we color the complete graph K5 as in Figure 1.6b, we see that this situation can even be avoided with five people.
It turns out that the answer to the Three Friends or Three Strangers Problem is six, however. In fact, we believe that we can convince you of this, even so early in our discussion. We state this as a theorem.
Theorem 1.1: The answer to the Three Friends or Three Strangers Problem is six. That is, among any six people, there must be three mutual friends or three mutual strangers.
Proof: We've already seen that the answer is not five. So what we must do is consider the complete graph K6 with six vertices where each edge is colored red or blue and show that there are three vertices where all three edges joining them have the same color.
Let's denote the vertices of K6 by u,v,w, x, y, z and look at u, say. Then there are five edges leading from u to the other five vertices. At least three of these five edges must be colored the same, say red. Suppose that three red edges lead to v,w and x as shown in Figure 1.7a. It's not important what the colors are of the edges leading u to y and z.
There are three edges joining the pairs of vertices among v, w and x. If even one of these edges is red—say the edge between v and w is red—then u, v and w represent three friends at the gathering, represented by the red triangle uvw. On the other hand, if no edge joining any two of the vertices v, w and x is red, then all three of these edges are blue, implying that v, w and x are mutual strangers at the gathering, represented by the blue triangle vwx, which is shown in Figure 1.7b where the edges of the blue triangle vwx are drawn with dashed lines.
Although the next problem is not well known historically, it is a practical problem and shows how graphs can be used to analyze a problem that we all might encounter.
A Job-Hunters Problem
A counselor in a high school has contacted a number of business executives she knows for the purpose of finding summer jobs for six hard-working students: Harry, Jack, Ken, Linda, Maureen, Nancy. She found six companies, each of which is willing to offer a summer position to a qualified student who is interested in the business. The six business areas are architecture, banking, construction, design, electronics, financial. The six students apply for these positions as follows:
Harry: architecture, banking, construction;
Jack: design, electronics, financial;
Ken: architecture, banking, construction, design;
Linda: architecture, banking, construction;
Maureen: design, electronics, financial;
Nancy: architecture, banking, construction.
(a) How can this situation be represented by a graph?
(b) Can each student obtain a job for which he or she has applied?
SOLUTION:
(a) We construct a graph G with 12 vertices, 6 of which represent the 6 students, which we denote by H, J, K, L, M, N (the first letters of their first names), and the other 6 vertices represent the 6 positions a, b, c, d, e, f, representing architecture, banking, construction, design, electronics, financial. An edge joins two vertices if one vertex represents a business and the other represents a student who applied for a position in that business area. (See Figure 1.8.)
(b) Yes. The edges Ha, Je, Kd, Lb, Mf, Nc within the graph G show that this is possible. (See Figure 1.9.) In this situation, Ken will have a summer job in the area of design. If this business decides that they would rather hire someone other than Ken, will all six students still be able to have a summer job for which they applied?
We'll see more about these kinds of "matching" problems in Chapter 7.
NEXT, ... FOUR FAMOUS PROBLEMS
We now look at four problems that are not only important in the history of graph theory (which we will describe later in the book) but which led to new areas within graph theory.
In 1736 the city of Königsberg was located in Prussia (in Europe). The River Pregel flowed through the city dividing it into four land areas. Seven bridges crossed the river at various locations. Figure 1.10 shows a map of Königsberg where the four land regions are A, B, C, D and the bridges are a, b, ..., g.
The Königsberg Bridge Problem
Is it possible to walk about Königsberg crossing each of its seven bridges exactly once?
Königsberg and this problem can be represented by a graph G—well, not exactly a graph. There are four vertices in G, one for each land region and two vertices are joined by a number of edges equal to the number of bridges joining these two land regions. What we get here is called a multigraph because more than one edge can join the same pair of vertices. This multigraph G is shown in Figure 1.11. In terms of this multigraph, solving the Königsberg Bridge Problem is the same as determining whether it is possible to walk about G and use each edge exactly once. Actually, there are two problems here, depending on whether we are asking whether there is a walk in Königsberg that ends where it began or whether there is a walk that ends in a land region different from the one where it began. A solution to both problems will be provided in Chapter 5.
In 1852 it was observed that in a map of England, the counties could be colored with four colors in such a way that every two counties sharing a common boundary are colored differently. This led to a much more general problem.
The Four Color Problem
In a map consisting of regions, can the regions be colored with four or fewer colors in such a way that every two regions sharing a common boundary are colored differently?
The map in Figure 1.12 is divided into 10 regions. These regions are colored with four colors, where the colors are 1, 2, 3, 4. It turns out that the regions of this map cannot be colored with three colors so that every two regions sharing a common boundary are colored differently, however.
This example, and the Four Color Problem in general, can be looked at in terms of graphs. A point is placed in each region and, like the Problem of the Five Princes, two points are joined by a line if the regions have a common boundary. Every graph constructed in this way can be drawn without any edges crossing. Instead of coloring regions, we can color the vertices of the resulting graph so that every two vertices joined by an edge are colored differently. This is illustrated in Figure 1.13 for the map in Figure 1.12. The Four Color Problem will be discussed in more detail in Chapter 11.
In geometry, a polyhedron (the plural is polyhedra) is a three-dimensional solid where the boundary of each face is a polygon. Figure 1.14 shows two polyhedra: the cube and the octahedron. It is common to represent the number of vertices of a polyhedron by V, the number of edges by E and the number of faces by F. These numbers for the cube and the octahedron are also given in Figure 1.14. In both cases, V - E + F = 2.
In 1750 the problem occurred as to whether V - E + F = 2 was a formula for every polyhedron.
The Polyhedron Problem
For a polyhedron with V vertices, E edges and F faces, is V - E + F = 2?
Every polyhedron can be represented by a graph whose edges do not cross. The graphs corresponding to the cube and the octahedron are shown in Figure 1.15. Here the number n of vertices of the graph is the number V of vertices of the polyhedron, the number m of edges of the graph is the number E of edges of the polyhedron and the number r of regions of the graph (including the outside region) is the number F of faces of the polyhedron. If it could be shown that n - m + r = 2 for all such graphs, then the Polyhedron Problem would be solved. This too will be discussed in Chapter 10.
Another polyhedron is the dodecahedron, shown in Figure 1.16. For this polyhedron, V = 20, E = 30 and F = 12 and, once again, V - E + F = 2. It was observed in 1856 that a round-trip can be made along edges of the dodecahedron passing through each vertex exactly once. Determining such a round-trip is known as an Around the World Problem. Consequently, a round-trip can be made along edges of the graph of the dodecahedron passing through each vertex exactly once. The graph corresponding to the dodecahedron is shown in Figure 1.17 where a trip around the world on this graph can be found by following the edges drawn in bold. The question occurs then as to which graphs have this property.
The Around the World Problem
Which graphs have the property that there is a round-trip along edges of the graph that passes through each vertex of the graph exactly once?
This problem will be discussed in Chapter 6.
GRAPHS, GAMES, GALLERIES AND GRIDLOCK
The game of chess has always been considered to be a mathematical game. Perhaps then it comes as no surprise that there are puzzles and problems involving chess that have connections to graph theory. The first of these has been traced back to the year 840.
A knight is a chess piece that can move from one square to another square that is two squares forward, backward, left or right and one square perpendicular to it. A knight therefore always moves to a square whose color is different from the square where it started.
The Knight's Tour Puzzle
Following the rules of chess, is it possible for a knight to tour an 8 × 8 chessboard, visiting each square exactly once, and return to the starting square?
Figure 1.18 shows (1) a chessboard, (2) the solution of the Knight's Tour Puzzle given in 840, where the numbers on the squares indicate the order in which the squares are visited and (3) this solution given in terms of a graph, where each square of the chessboard is a vertex and where two vertices are joined by an edge if this indicates a move of the knight. This problem therefore has a great deal of similarity to the Around the World Problem mentioned in the preceding section.
(Continues...)
Excerpted from The Fascinating World of Graph Theory by Arthur Benjamin, Gary Chartrand, Ping Zhang. Copyright © 2015 Princeton University Press. Excerpted by permission of PRINCETON UNIVERSITY PRESS.
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.
Table of Contents
Preface viiPrologue xiii
1 Introducing Graphs 1
2 Classifying Graphs 22
3 Analyzing Distance 45
4 Constructing Trees 67
5 Traversing Graphs 91
6 Encircling Graphs 108
7 Factoring Graphs 125
8 Decomposing Graphs 143
9 Orienting Graphs 164
10 Drawing Graphs 183
11 Coloring Graphs 206
12 Synchronizing Graphs 226
Epilogue Graph Theory: A Look Back—The Road Ahead 251
Exercises 255
Selected References 309
Index of Names 317
Index of Mathematical Terms 319
What People are Saying About This
"In this attractive introduction to the world of graphs, the authors entice and enthuse readers through a number of fun problems which present various aspects of the subject. Many of these problems are familiar—the four-color problem, the Königsberg Bridge problem, and 'instant insanity'—while others are less well known or of a more serious nature. This book can be used in different ways—as an entertaining book on recreational mathematics or as an accessible textbook on graph theory. I warmly recommend it."—Robin J. Wilson, author of Introduction to Graph Theory"This is a beautiful introduction to graph theory! It is filled with fun material, clear explanations, and a nice collection of exercises. A great book."—William J. Cook, author of In Pursuit of the Traveling Salesman"The Fascinating World of Graph Theory is wonderfully written. Entertaining applications appear first and the stories that accompany the examples go well beyond what most other books provide. This book is sure to gain a following."—Jonathan L. Gross, Columbia University