Graph Theory and Its Applications ()

Cover
Half Title
Textbooks in Mathematics
Title
Copyright
Dedication
CONTENTS
PREFACE
AUTHORS
Chapter 1 INTRODUCTION TO GRAPH MODELS
	1.1 GRAPHS AND DIGRAPHS
	1.2 COMMON FAMILIES OF GRAPHS
	1.3 GRAPH MODELING APPLICATIONS
	1.4 WALKS AND DISTANCE
	1.5 PATHS, CYCLES, AND TREES
	1.6 VERTEX AND EDGE ATTRIBUTES: MORE APPLICATIONS
	1.7 SUPPLEMENTARY EXERCISES
	GLOSSARY
Chapter 2 STRUCTURE AND REPRESENTATION
	2.1 GRAPH ISOMORPHISM
	2.2 AUTOMORPHISMS AND SYMMETRY
	2.3 SUBGRAPHS
	2.4 SOME GRAPH OPERATIONS
	2.5 TESTS FOR NON-ISOMORPHISM
	2.6 MATRIX REPRESENTATIONS
	2.7 MORE GRAPH OPERATIONS
	2.8 SUPPLEMENTARY EXERCISES
	GLOSSARY
Chapter 3 TREES
	3.1 CHARACTERIZATIONS AND PROPERTIES OF TREES
	3.2 ROOTED TREES, ORDERED TREES, AND BINARY TREES
	3.3 BINARY-TREE TRAVERSALS
	3.4 BINARY-SEARCH TREES
	3.5 HU MAN TREES AND OPTIMAL PRE X CODES
	3.6 PRIORITY TREES
	3.7 COUNTING LABELED TREES: PR UFER ENCODING
	3.8 COUNTING BINARY TREES: CATALAN RECURSION
	3.9 SUPPLEMENTARY EXERCISES
	GLOSSARY
Chapter 4 SPANNING TREES
	4.1 TREE GROWING
	4.2 DEPTH-FIRST AND BREADTH-FIRST SEARCH
	4.3 MINIMUM SPANNING TREES AND SHORTEST PATHS
	4.4 APPLICATIONS OF DEPTH-FIRST SEARCH
	4.5 CYCLES, EDGE-CUTS, AND SPANNING TREES
	4.6 GRAPHS AND VECTOR SPACES
	4.7 MATROIDS AND THE GREEDY ALGORITHM
	4.8 SUPPLEMENTARY EXERCISES
	GLOSSARY
Chapter 5 CONNECTIVITY
	5.1 VERTEX- AND EDGE-CONNECTIVITY
	5.2 CONSTRUCTING RELIABLE NETWORKS
	5.3 MAX-MIN DUALITY AND MENGER'S THEOREMS
	5.4 BLOCK DECOMPOSITIONS
	5.5 SUPPLEMENTARY EXERCISES
	GLOSSARY
Chapter 6 OPTIMAL GRAPH TRAVERSALS
	6.1 EULERIAN TRAILS AND TOURS
	6.2 DEBRUIJN SEQUENCES AND POSTMAN PROBLEMS
	6.3 HAMILTONIAN PATHS AND CYCLES
	6.4 GRAY CODES AND TRAVELING SALESMAN PROBLEMS
	6.5 SUPPLEMENTARY EXERCISES
	GLOSSARY
Chapter 7 PLANARITY AND KURATOWSKI'S THEOREM
	7.1 PLANAR DRAWINGS AND SOME BASIC SURFACES
	7.2 SUBDIVISION AND HOMEOMORPHISM
	7.3 EXTENDING PLANAR DRAWINGS
	7.4 KURATOWSKI'S THEOREM
	7.5 ALGEBRAIC TESTS FOR PLANARITY
	7.6 PLANARITY ALGORITHM
	7.7 CROSSING NUMBERS AND THICKNESS
	7.8 SUPPLEMENTARY EXERCISES
	GLOSSARY
Chapter 8 GRAPH COLORINGS
	8.1 VERTEX-COLORINGS
	8.2 MAP-COLORINGS
	8.3 EDGE-COLORINGS
	8.4 FACTORIZATION
	8.5 SUPPLEMENTARY EXERCISES
	GLOSSARY
Chapter 9 SPECIAL DIGRAPH MODELS
	9.1 DIRECTED PATHS AND MUTUAL REACHABILITY
	9.2 DIGRAPHS AS MODELS FOR RELATIONS
	9.3 TOURNAMENTS
	9.4 PROJECT SCHEDULING
	9.5 FINDING THE STRONG COMPONENTS OF A DIGRAPH
	9.6 SUPPLEMENTARY EXERCISES
	GLOSSARY
Chapter 10 NETWORK FLOWS AND APPLICATIONS
	10.1 FLOWS AND CUTS IN NETWORKS
	10.2 SOLVING THE MAXIMUM-FLOW PROBLEM
	10.3 FLOWS AND CONNECTIVITY
	10.4 MATCHINGS, TRANSVERSALS, AND VERTEX COVERS
	10.5 SUPPLEMENTARY EXERCISES
	GLOSSARY
Chapter 11 GRAPH COLORINGS AND SYMMETRY
	11.1 AUTOMORPHISMS OF SIMPLE GRAPHS
	11.2 EQUIVALENCE CLASSES OF COLORINGS
	11.3 SUPPLEMENTARY EXERCISES
	GLOSSARY
A APPENDIX
	A.1 LOGIC FUNDAMENTALS
	A.2 RELATIONS AND FUNCTIONS
	A.3 SOME BASIC COMBINATORICS
	A.4 ALGEBRAIC STRUCTURES
	A.5 ALGORITHMIC COMPLEXITY
	A.6 SUPPLEMENTARY READING
B BIBLIOGRAPHY
	B.1 GENERAL READING
	B.2 REFERENCES
SOLUTIONS AND HINTS
INDEX OF APPLICATIONS
INDEX OF ALGORITHMS
GENERAL INDEX