The Theory of Graphs

From the circuit diagrams of physics and electronics to psychology's sociograms and the communications networks employed by operational research, an extraordinary variety of disciplines rely on graphs to convey fundamentals as well as finer points. With this concise and well-written text, any reader possessing a firm grasp of general mathematics can follow the development of graph theory and learn to apply its principles in methods both formal and abstract.
The first full-length book in English on graph theory, this volume is the work of a distinguished mathematician who has made significant original contributions to the subject. His frequent use of practical examples illustrates the theory's broad range of applications, providing a versatile mathematical technique appropriate to the behavioral sciences, information theory, cybernetics, and other areas, in addition to mathematical disciplines such as set and matrix theory.
The author begins with the simplest theorems, stated in the most general terms possible for economy of thought and exposition. He gradually builds to more complex theorems, expressed in more exacting proofs and reflecting the results of extensive studies. Definitions from algebra and the theory of sets appear at the start and are supplemented as needed.
Students, teachers, and anyone interested in effective communication of research results will find this text a valuable source of instruction.

Introduction
1 General Definitions
Sets and Multivalued Functions
Paths and Circuits of a Graph
Chains and Cycles of a Graph
2 Descendance Relations
Weak Ordering Associated with a Graph
Inductive Graphs and Bases
3 The Ordinal Function and the Grundy Function on an Infinite Graph
General Remarks Concerning Infinite Graphs
Ordinal Function
Grundy Functions
Operations over Graphs
4 The Fundamental Numbers of the Theory of Graphs
Cyclomatic Number
Chromatic Number
Methods for Finding the Chromatic Number
Coefficient of Internal Stability
Coefficient of External Stability
5 Kernels of a Graph
Existence and Uniqueness Theorems
Application to Grundy Functions
6 Games on a Graph
Nim Type Games
The General Definition of a Game (with Perfect Information)
Strategies
7 The Problem of the Shortest Route
Stepwise Procedures
Various Generalizations
8 Transport Networks
The Problem of Maximum Flow
The Problem of Minimum Flow
Problems of Flow when a Set of Values is Associated with each Arc
Infinite Transport Networks
9 The Theorem of the Demi-Degrees
Inward or Outward Demi-Degree
10 Matching of a Simple Graph
The Maximum Matching Problem
Deficiency of a Simple Graph
The Hungarian Method
Extensions to the Infinite Case
Application to the Theory of Matrices
11 Factors
Hamiltonian Paths and Circuits
Factors and Methods for Determining Them
The Problem of Finding a Partial Graph with Given Demi-Degrees
12 Centres of a Graph
Centrees
Radius
13 The Diameter of a Strongly Connected Graph
General Remarks on Strongly Connected Graphs without Loops
Diameter
14 The Matrix Associated with a Graph
The Use of Standard Matrix Operations
Problems of Enumeration
The Problem of the Leader
The Use of Boolean Operations
15 Incidence Matrices
Matrices with the Unimodular Property
Systems with the Unimodular Property
Cyclomatic Matrices
16 Trees and Arborescences
Trees
Analytic Treatment
Arborescences
17 Euler's Problem
Eulerian Cycles
Eulerian Circuits
18 Matching in the General Case
The Theory of Alternating Chains
The Determination of a Partial Graph with Given Degrees
Perfect Matching
Application to the Coefficient of Internal Stability
19 Semi-Factors
Hamiltonian Cycles and Semi-Factors
A Necessary and Sufficient Condition for the Existence of a Semi-Factor
20 The Connectivity of a Graph
Articulation Points
Biconnected Graphs
h-Connected Graphs
21 Planar Graphs
General Properties
Generalization
Appendix 1 Note on the General Theory of Games
Appendix 2 Note on Transport Problems
Bibliography
List of Symbols
Index of Terms Used

What is included with this book?

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.

FREE SHIPPING

Amazon no longer offers textbook rentals. We do!

Summary

Table of Contents

Supplemental Materials