Graph Theory Modeling, Applications, and Algorithms

by Agnarsson, Geir; Greenlaw, Raymond

• ISBN13: 9780131423848
• ISBN10: 0131423843
• Edition: 1st
• Format: Paperback
• Copyright: 2006-09-22
• Publisher: Pearson

Summary

Once considered an "unimportant" branch of topology, graph theory has come into its own through many important contributions to a wide range of fields and is now one of the fastest-growing areas in discrete mathematics and computer science. This practical, intuitive book introduces basic concepts, definitions, theorems, and examples from graph theory. Presents a collection of interesting results from mathematics that involve key concepts and proof techniques. Covers design and analysis of computer algorithms for solving problems in graph theory. Discusses applications of graph theory to the sciences. Includes a collection of graph algorithms, written in Java, that are ready for compiling and running. For anyone interested in learning graph theory, discrete structures, or algorithmic design for graph problems.

Table of Contents

Preface	ix
Introduction to Graph Theory	1	(30)
Introduction	1	(1)
Why Study Graphs?	1	(5)
Mathematical Preliminaries	6	(4)
The Definition of a Graph	10	(3)
Examples of Common Graphs	13	(2)
Degrees and Regular Graphs	15	(4)
Subgraphs	19	(2)
The Definition of a Directed Graph	21	(3)
Indegrees and Outdegrees in a Digraph	24	(2)
Exercises	26	(5)
Basic Concepts in Graph Theory	31	(35)
Paths and Cycles	31	(4)
Connectivity	35	(4)
Homomorphisms and Isomorphisms of Graphs	39	(6)
More on Isomorphisms on Simple Graphs	45	(3)
Formations and Minors of Graphs	48	(7)
Homomorphisms and Isomorphisms for Digraphs	55	(3)
Digraph Connectivity	58	(3)
Exercises	61	(5)
Trees and Forests	66	(32)
Trees and Some of Their Basic Properties	66	(4)
Characterizations of Trees	70	(1)
Inductive Proofs on Trees	71	(3)
Erdos-Szekeres Theorem on Sequences	74	(3)
Centers in Threes	77	(4)
Rooted Trees	81	(2)
Binary Trees	83	(5)
Levels in Rooted and Binary Trees	88	(5)
Exercises	93	(5)
Spanning Trees	98	(34)
Spanning Trees and Forests	98	(3)
Spanning Trees of the Complete Graph	101	(3)
The Adjacency Matrix of a Graph	104	(4)
The Incidence Matrix of a Graph	108	(4)
The Matrix-Tree Theorem	112	(5)
An Application to Electrical Networks	117	(4)
Minimum Cost Spanning Trees	121	(5)
Exercises	126	(6)
Fundamental Properties of Graphs and Digraphs	132	(28)
Bipartite Graphs	132	(3)
Eulerian Graphs	135	(4)
Hamiltonian Graphs	139	(5)
Hamiltonian Cycles in Weighted Graphs	144	(1)
Eulerian and Hamiltonian Digraphs	145	(2)
Tournament Digraphs	147	(3)
On the Adjacency Matrix of a Digraph	150	(2)
Acyclic Digraphs and Posets	152	(3)
Exercises	155	(5)
Connectivity and Flow	160	(35)
Edge Cuts	160	(3)
Edge Connectivity and Connectivity	163	(5)
Blocks in Separable Graphs	168	(5)
Flows in Networks	173	(12)
The Theorems of Menger	185	(5)
Exercises	190	(5)
Planar Graphs	195	(37)
Embeddings in Surfaces	195	(4)
More on Planar Embeddings	199	(2)
Euler's Formula and Consequences	201	(4)
Characterization of Planar Graphs	205	(5)
Kuratowski and Wagner's Theorem	210	(4)
Plane Duality	214	(6)
Higher Genus	220	(4)
Generalization of Euler's Formula	224	(3)
Crossing Number	227	(1)
Exercises	228	(4)
Graph Coloring	232	(35)
The Chromatic Number of a Graph	232	(4)
Multipartite Graphs	236	(5)
Results for General Graphs	241	(4)
Planar Graphs and Other Surface Graphs	245	(7)
Edge Coloring of a Graph	252	(5)
Tait's Theorem	257	(2)
Exercises	259	(8)
Coloring Enumerations and Chordal Graphs	267	(32)
The Chromatic Polynomial of a Graph	267	(5)
Basic Properties of the Chromatic Polynomial	272	(3)
Interval and Intersection Graphs	275	(9)
Chordal Graphs	284	(6)
Powers of Graphs	290	(6)
Exercises	296	(3)
Independence, Dominance, and Matchings	299	(28)
Independence of Vertices	299	(6)
Domination of Vertices	305	(7)
Matchings in a Graph	312	(6)
Hall's Marriage Theorem	318	(5)
Exercises	323	(4)
Cover Parameters and Matching Polynomials	327	(29)
Covers and Related Parameters	327	(6)
Rook Polynomials and Bipartite Graphs	333	(7)
The Matching Defect Polynomial	340	(3)
Matching Algorithms	343	(8)
Exercises	351	(5)
Graph Counting	356	(36)
Introduction	356	(2)
Basic Counting Results	358	(7)
Generating Functions	365	(6)
Partitions of a Finite Set	371	(3)
The Labeled Counting Lemma	374	(4)
The Exponential Formula	378	(3)
The Number Two and Related Graphs	381	(5)
Two-Regular Graphs	381	(1)
Two-Colorable Graphs	382	(2)
Even Graphs	384	(2)
Exercises	386	(6)
Graph Algorithms	392	(39)
Introduction	392	(1)
Recap of Algorithms Already Presented	393	(1)
Algorithm Efficiency	394	(2)
Breadth-First Search	396	(4)
Depth-First Search	400	(3)
Connected Components	403	(4)
Dijkstra's Shortest Path Algorithm	407	(4)
Java Source Code	411	(5)
Exercises	416	(5)
APPENDICES
A. Greek Alphabet	421	(2)
B. Notation	423	(6)
C. Top Ten Online References	429	(2)
Bibliography	431	(4)
Index	435