Graph Theory and Its Applications

Jonathan L. Gross, Jay Yellen, Mark Anderson

• Publisher: Chapman and Hall/CRC
• Year: 2018
• Print ISBN: 9781482249484
• eBook ISBN: 9780429757082
• Edition: 3
• Topic: Computer Science
• Subtopic: Operating Systems
• Index: Computer Science

Graph Theory and Its Applications, Third Edition is the latest edition of the international, bestselling textbook for undergraduate courses in graph theory, yet it is expansive enough to be used for graduate courses as well. The textbook takes a comprehensive, accessible approach to graph theory, integrating careful exposition of classical developments with emerging methods, models, and practical needs.

The authors' unparalleled treatment is an ideal text for a two-semester course and a variety of one-semester classes, from an introductory one-semester course to courses slanted toward classical graph theory, operations research, data structures and algorithms, or algebra and topology.

Features of the Third Edition

• Expanded coverage on several topics (e.g., applications of graph coloring and tree-decompositions)
• Provides better coverage of algorithms and algebraic and topological graph theory than any other text
• Incorporates several levels of carefully designed exercises that promote student retention and develop and sharpen problem-solving skills
• Includes supplementary exercises to develop problem-solving skills, solutions and hints, and a detailed appendix, which reviews the textbook's topics

About the Authors

Jonathan L. Gross is a professor of computer science at Columbia University. His research interests include topology and graph theory.

Jay Yellen is a professor of mathematics at Rollins College. His current areas of research include graph theory, combinatorics, and algorithms.

Mark Anderson is also a mathematics professor at Rollins College. His research interest in graph theory centers on the topological or algebraic side.

Chapter 1

INTRODUCTION TO GRAPH MODELS

Introduction

Configurations of nodes and connections occur in a great diversity of applications. They may represent physical networks, such as electrical circuits, roadways, or organic molecules. And they are also used in representing less tangible interactions as might occur in ecosystems, sociological relationships, databases, or the flow of control in a computer program.

Formally, such configurations are modeled by combinatorial structures called graphs, consisting of two sets called vertices and edges and an incidence relation between them. The vertices and edges may have additional attributes, such as color or weight, or anything else useful to a particular model. Graph models tend to fall into a handful of categories. For instance, the network of one-way streets of a city requires a model in which each edge is assigned a direction; two atoms in an organic molecule may have more than one bond between them; and a computer program is likely to have loop structures. These examples require graphs with directions on their edges, with multiple connections between vertices, or with connections from a vertex to itself.

In the past these different types of graphs were often regarded as separate entities, each with its own set of definitions and properties. We have adopted a unified approach by introducing all of these various graphs at once. This allows us to establish properties that are shared by several classes of graphs without having to repeat arguments. Moreover, this broader perspective has an added bonus: it inspires computer representations that lead to the design of fully reusable software for applications.

We begin by introducing the basic terminology needed to view graphs both as configurations in space and as combinatorial objects that lend themselves to computer representation. Pure and applied examples illustrate how different kinds of graphs arise as models.

1.1 GRAPHS AND DIGRAPHS

We think of a graph as a set of points in a plane or in 3-space and a set of line segments (possibly curved), each of which either joins two points or joins a point to itself.

Graphs are highly versatile models for analyzing a wide range of practical problems in which points and connections between them have some physical or conceptual interpretation. Placing such analysis on solid footing requires precise definitions, terminology, and notation.

DEFINITION: A graph G = (V, E) is a mathematical structure consisting of two finite sets V and E. The elements of V are called vertices (or nodes), and the elements of E are called edges. Each edge has a set of one or two vertices associated to it, which are called its endpoints.

TERMINOLOGY: An edge is said to join its endpoints. A vertex joined by an edge to a vertex v is said to be a neighbor of v.

DEFINITION: The (open) neighborhood of a vertex v in a graph G, denoted N(v), is the set of all the neighbors of v. The closed neighborhood of v is given by N[v] = N(v) ∪ {v}.

NOTATION: When G is not the only graph under consideration, the notations V_G and E_G (or V(G) and E(G)) are used for the vertex- and edge-sets of G, and the notations N_G(v) and N_G[v] are used for the neighborhoods of v.

Example 1.1.1: The vertex- and edge-sets of graph A in Figure 1.1.1 are given by

$\begin{array}{ccc}{V}_A=\left\{p,q,r,s\right\}& \text{and}& E_A=\left\{pq,pr,ps,rs,qs\right\}\end{array}$

and the vertex- and edge-sets of graph B are given by

$\begin{array}{ccc}{V}_B=\left\{u,v,w\right\}& \text{and}& E_B=\left\{a,b,c,d,f,g,h,k\right\}\end{array}$

Notice that in graph A, we are able ...

Table of contents

• Cover
• Half Title
• Series Page
• Title Page
• Copyright Page
• Dedication
• Table of Contents
• Preface
• Authors
• 1 Introduction to Graph Models
• 2 Structure and Representation
• 3 Trees
• 4 Spanning Trees
• 5 Connectivity
• 6 Optimal Graph Traversals
• 7 Planarity and Kuratowski’s Theorem
• 8 Graph Colorings
• 9 Special Digraph Models
• 10 Network Flows and Applications
• 11 Graph Colorings and Symmetry
• A Appendix
• B Bibliography
• Solutions and Hints
• Index of Applications
• Index of Algorithms
• General Index