Riassunto
Interest in graphs and their applications has grown tremendously in recent years-largely due to the usefulness of graphs as models for computation and optimization. This comprehensive, applications-driven text provides a fresh and accessible approach suitable for several different courses in graph theory. Written for graduate and advanced undergraduate students, for self-study, and as a reference for working professionals, it covers a wide range of topics in algorithmic, combinatorial, and topological graph theory. The authors present numerous applications and examples designed to stimulate interest in and demonstrate the relevance of new concepts. With its generous use of drawings, streamlined proofs, and concise algorithms, Graph Theory and Its Applications offers a less intimidating treatment of the subject. It also includes more than 1,600 exercises-from routine to challenging-providing a rich source of problems that test your understanding. In this text, the authors succeed in presenting the subject in a cohesive framework that transforms important techniques and analytic tools into a unified mathematical methodology.
Contenuti
INTRODUCTION TO GRAPH MODELS
Graphs and Digraphs
Common Families of Graphs
Graph Modeling Applications
Walks and Distance
Paths, Cycles, and Trees
Vertex and Edge Attributes: More Applications
STRUCTURE AND REPRESENTATION
Subgraphs
Some Graphs Operations
Graph Isomorphism
Tests for Non-Isomorphism
Matrix Representations
TREES
Characterizations and Properties of Trees
Rooted Trees
Binary Trees
Counting Binary Trees-The Catalan Recursion
Traversing a Binary Tree
Binary-Search Trees
Priority Trees
SPANNING TREES
An Intuitive Tree-Growing Scheme
Depth-First and Breadth-First Search
Applications of Depth-First Search
Counting Spanning Trees: Prüfer Encoding
Minimum Spanning Trees and Shortest Paths
Cycles, Edge Cuts, and Spanning Trees
Graphs and Vector Spaces
Matroids and the Greedy Algorithm
CONNECTIVITY
Vertex- and Edge-Connectivity
Constructing Reliable Networks
Max-Min Duality and Menger's Theorems
Block Decomposition
OPTIMAL GRAPH TRAVERSALS
Eulerian Trails and Tours
DeBruijn Sequences and Postman Problems
Hamilton Paths and Cycles
Gray Codes and Traveling Salesman Problems
GRAPH OPERATIONS AND MAPPINGS
Binary Operations on Graphs
Linear Graph Mappings
Modeling Network Emulation
Subdivision and Homeomorphism
Transforming a Graph by Edge Contraction
DRAWING GRAPHS AND MAPS
The Topology of Graphs and of the Sphere
Higher-Order Surfaces
Drawing Imbeddings
Numerical Relations for Imbeddings
Regular Sphere Maps
PLANARITY OF GRAPHS
Planarity and Nonplanarity
Extending Planar Drawings
Kuratowski's Theorem
Planarity Algorithm
GRAPH COLORINGS
Vertex-Colorings
Map-Colorings
Edge-Colorings
SPECIAL DIGRAPH MODELS
Basic Properties and Some New Terminology
Selected Applications of the General Digraph
Tournaments and Project Scheduling
Finding the Strong Components of a Digraph
NETWORK FLOWS AND MATCHING
Flows and Cuts in Networks
Solving the Maximum-Flow Problem
Determining the Connectivity of a Graph
Matchings, Transversals, and Vertex Covers
GRAPHICAL ENUMERATION
Automorphisms and Symmetry
Graph Colorings and Symmetry
Cycle Index of a Permutation Group
Burnside's Lemma
Enumerating Vertex- and Edge-Colorings
Counting Simple Graphs
ALGEBRAIC SPECIFICATION OF GRAPHS
Cyclic Voltages
Cayley Graphs and Regular Voltages
Permutation Voltages
Symmetric Graphs and Parallel Architectures
Interconnection-Network Performance
NON-PLANAR LAYOUTS
Crossing Numbers and Thickness
Imbeddings in General Surfaces
Representing Imbeddings by Rotations
Genus Distribution of a Graph
Voltage-Graph Specification of Graph Layouts
Non-KVL Imbedded Voltage Graphs
Heawood Map-Coloring Problem
APPENDICES
Logic Fundamentals
Relations and Functions
Some Basic Combinatorics
Algebraic Structures
Algorithmic Complexity
Supplementary Reading
BIBLIOGRAPHY
INDICES
Index of Applications
Index of Algorithms
Index of Notations
General Index
Le informazioni nella sezione "Su questo libro" possono far riferimento a edizioni diverse di questo titolo.
