A Friendly Introduction to Graph Theory - Hardcover

Buckley, Fred; Lewinter, Marty

9780130669490: A Friendly Introduction to Graph Theory

Hardcover

ISBN 10: 0130669490 ISBN 13: 9780130669490

Publisher: Pearson College Div, 2002

This book introduces graph theory, a subject with a wide range of applications in real-work situations. This book is designed to be easily accessible to the novice, assuming no more than a good grasp of algebra to understand and relate to the concepts presented. Using many examples, illustrations, and figures, it provides an excellent foundation for the basic knowledge of graphs and their applications. This book includes an introductory chapter that reviews the tools necessary to understand the concepts of graphs, and then goes on to cover such topics as trees and bipartite graphs, distance and connectivity, Eulerian and Hamiltonian graphs, graph coloring, matrices, algorithms, planar graphs, and digraphs and networks. Graph theory has a wide range of applications; this book is useful for those in the fields of anthropology, computer science, chemistry, environmental conservation, fluid dynamics, psychology, sociology, traffic management, telecommunications, and business managers and strategists.

"synopsis" may belong to another edition of this title.

Graph theory is a delightful subject with a host of applications in such fields as anthropology, computer science, chemistry, environmental conservation, fluid dynamics, psychology, sociology, traffic management, and telecommunications, among others. With the advent of operations research in the twentieth century, graph theory has risen several notches in the esteem in which it is held. Formally a branch of combinatorics, graph theory intersects topology, group theory, and number theory, to name just a few fields. While its theorems and proofs range from easy to almost incomprehensible, graph theory is, after all, the study of dots and lines!

Because of its wide range of applications, it is important that students in many diverse fields, not just mathematics and computer science, gain a foundation in the basics of graph theory. By doing so, they will have additional powerful tools at their disposal to analyze problems within their own area of study. We have written this text mainly with those students in mind and designed it to be easily accessible to undergraduate students as early as the sophomore level. We assume nothing more than a good grasp of algebra. Thus, A Friendly Introduction to Graph Theory provides early access to this wonderful and useful area of study for students in mathematics, computer science, the social sciences, business, engineering—wherever graph theory is needed.

The student will find this text quite readable. This book should be read with pencil and paper nearby—it is not bedtime reading. The exercises reflect the contents of the chapter and range from easy to hard. Answers, solutions, or hints are supplied in the back of the book for a wide selection of the exercises. It is important to realize that mathematics is not a spectator sport (although it can be fascinating to watch someone present a surprisingly simple proof of an interesting result). Do the exercises, or you will not retain the material of the nth chapter as you attempt the (n+l)-st. A bonus to the diligent students who work through the more challenging exercises is that those students will develop a strong foundation for research in graph theory and an ability to apply the concepts learned to a wide range of real-world problems.

Content

In Chapter 1, we discuss basic prerequisite concepts and ideas that the reader should be familiar with. Although it is meant as a review, a somewhat thorough treatment is given to provide the necessary tools for understanding the material that will be examined throughout the rest of the book. Thus we discuss topics such as sets, functions, parity, mathematical induction, proof techniques, counting techniques, permutations and combinations, Pascal's triangle, and combinatorial identities. For those readers unfamiliar with proof techniques, this introductory chapter will be particularly helpful. In a class of better-prepared students, the instructor may choose to skip some or all of the contents of Chapter 1.

As mentioned earlier, graphs have a wide variety of applications. In Chapter 2, we introduce the most basic concepts of graph theory and illustrate some of the areas where graphs are used. We will see many other applications throughout the book.

One class of graphs is so important that it deserves treatment in its own chapter. Because of their simple structure, trees are often used as a testing ground for possible new theorems. Trees arise in many applications, such as analyzing business hierarchies and determining minimum cost transportation networks, and are the basis of important data structures in computer science. A tree is a special type of graph in a larger class called bipartite graphs. In Chapter 3, we examine trees, bipartite graphs, and their uses. The chapter concludes with an application to job assignment problems.

The concept of distance is widely used throughout graph theory and its applications. Distance is used in various graph operations, in isomorphism testing, and in convexity problems, and is the basis of several graph symmetry concepts. Distance is used to define many graph centrality concepts, which in turn are useful in facility location problems. Numerous graph algorithms are distance related in that they search for paths of various lengths within the graph. Distance is an important factor in extremal problems in graph connectivity. Graph connectivity is important in its own right because of its strong relation to the reliability and vulnerability of computer networks. In Chapter 4, we discuss some of the many important concepts and results concerning distance and connectivity in graphs. We conclude with a discussion of a facility location problem and an introduction to the concept of reliability of computer networks.

Numerous theoretical and applied problems in graph theory require one to traverse a graph in a particular way. In some problems, the goal is to find a trail or circuit in order to pass through each edge exactly once. In other problems, one must find a path or cycle that includes each vertex exactly once. We discuss such problems in Chapter 5. We conclude with a discussion of two well-known related problems, namely, the Chinese postman problem, and the Traveling salesman problem.

Various real-world problems that can be modeled by graphs require that the vertex set or edge set be partitioned into disjoint sets such that items within a given set are mutually nonadjacent. Common problems include scheduling meetings or exams to avoid conflicts and storage of chemicals to prevent adverse interactions. These problems are related to graph coloring, the subject of Chapter 6.

A matrix is a rectangular table of numbers. One of the simplest ways of storing a graph in a computer is by using a matrix or its computer science counterpart, an array. Graph theory makes effective use of matrices as a tool in examining structural and other properties of graphs. In Chapter 7, we first review some basic properties of matrices and then examine some uses of matrices within graph theory.

There are many connections between graph theory and computer science. Thus it should not be surprising that algorithms have played a strong role in recent graph theory research, so much so that several books have been devoted to algorithmic graph theory. In Chapter 8, we give an introduction to graph algorithms and indicate some of their uses. We discuss the important breadth-first search and depth-first search algorithms and examine algorithms for graph coloring as well as for coding trees. Several other algorithms are presented throughout the text. We shall not examine efficiency of algorithms or NP-completeness here, but refer the interested reader to appropriate sources for discussions of those topics.

A graph is planar if it can be drawn in the plane with no crossing edges. Planar graphs have received a great deal of attention over the years because of a long-standing problem, the four-color conjecture, that took over one hundred years to prove. Planar graphs remain important today because of their applications. Planar graphs are important in facility layout problems within operations research, and they are crucial in the design of printed circuit boards in computer science. We discuss planar graphs and their properties in Chapter 9.

To model certain real-world problems, a structure more complex than a graph is needed. In Chapter 10, we consider some additional structures. Digraphs are similar to graphs except there are directions on the edges. Digraphs are used to model problems where the direction of flow of some quantity (information, traffic, liquid, electrons, and so on) is of importance. When limits are placed on how much of that quantity can flow through a given directed edge, we obtain a network. A special type of digraph with no directed cycles, called an activity digraph, has weights on the directed edges indicating the duration of a given activity. These weighted digraphs are used to aid in scheduling individual activities that compose a complex project. In Chapter 10, we explore various types of digraphs and their properties, study network flows, and present an algorithm to maximize total flow. We conclude the chapter with a discussion of activity digraphs and their uses.

In Chapter 11, we consider two additional topics, Ramsey theory and graph domination. The first is related to edge colorings in graphs, and the second is related to both distance and independence and has a wide range of applications. The one thing that these last two topics have in common is that they are lots of fun to work on.

We hope this book is as much fun for you to read and learn from as it was for us to write.

"About this title" may belong to another edition of this title.