The Theory of Graphs

Concise, well-written text illustrates development of graph theory and application of its principles in methods both formal and abstract. Practical examples explain theory's broad range, from behavioral sciences, information theory, cybernetics, and other areas, to mathematical disciplines such as set and matrix theory. 1966 edition. Includes 109 black-and-white illustrations.

Introduction

vii

General Definitions

Sets and Multivalued Functions

1

(4)

Paths and Circuits of a Graph

5

(3)

Chains and Cycles of a Graph

8

(3)

Descendance Relations

Weak Ordering Associated with a Graph

11

(2)

Inductive Graphs and Bases

13

(3)

The Ordinal Function and the Grundy Function on an Infinite Graph

General Remarks Concerning Infinite Graphs

16

(3)

Ordinal Function

19

(3)

Grundy Functions

22

(1)

Operations over Graphs

23

(4)

The Fundamental Numbers of the Theory of Graphs

Cyclomatic Number

27

(3)

Chromatic Number

30

(3)

Methods for Finding the Chromatic Number

33

(2)

Coefficient of Internal Stability

35

(5)

Coefficient of External Stability

40

(5)

Kernels of a Graph

Existence and Uniqueness Theorems

45

(5)

Application to Grundy Functions

50

(2)

Games on a Graph

Nim Type Games

52

(6)

The General Definition of a Game (with Perfect Information)

58

(2)

Strategies

60

(5)

The Problem of the Shortest Route

Stepwise Procedures

65

(3)

Various Generalizations

68

(3)

Transport Networks

The Problem of Maximum Flow

71

(6)

The Problem of Minimum Flow

77

(1)

Problems of Flow when a Set of Values is Associated with each Arc

77

(7)

Infinite Transport Networks

84

(2)

The Theorem of the Demi-Degrees

Inward or Outward Demi-Degree

86

(6)

Matching of a Simple Graph

The Maximum Matching Problem

92

(4)

Deficiency of a Simple Graph

96

(3)

The Hungarian Method

99

(3)

Extensions to the Infinite Case

102

(3)

Application to the Theory of Matrices

105

(2)

Factors

Hamiltonian Paths and Circuits

107

(4)

Factors and Methods for Determining Them

111

(6)

The Problem of Finding a Partial Graph with Given Demi-Degrees

117

(2)

Centres of a Graph

Centres

119

(1)

Radius

120

(3)

The Diameter of a Strongly Connected Graph

General Remarks on Strongly Connected Graphs without Loops

123

(3)

Diameter

126

(4)

The Matrix Associated with a Graph

The Use of Standard Matrix Operations

130

(2)

Problems of Enumeration

132

(3)

The Problem of the Leader

135

(3)

The Use of Boolean Operations

138

(3)

Incidence Matrices

Matrices with the Unimodular Property

141

(5)

Systems with the Unimodular Property

146

(3)

Cyclomatic Matrices

149

(3)

Trees and Arborescences

Trees

152

(4)

Analytic Treatment

156

(4)

Arborescences

160

(5)

Euler's Problem

Eulerian Cycles

165

(2)

Eulerian Circuits

167

(4)

Matching in the General Case

The Theory of Alternating Chains

171

(3)

The Determination of a Partial Graph with Given Degrees

174

(4)

Perfect Matching

178

(6)

Application to the Coefficient of Internal Stability

184

(3)

Semi-Factors

Hamiltonian Cycles and Semi-Factors

187

(5)

A Necessary and Sufficient Condition for the Existence of a Semi-Factor

192

(4)

The Connectivity of a Graph

Articulation Points

196

(2)

Biconnected Graphs

198

(5)

h-Connected Graphs

203

(4)

Planar Graphs

General Properties

207

(11)

Generalization

218

(2)

Appendix 1 Note on the General Theory of Games

220

(7)

Appendix 2 Note on Transport Problems

227

(11)

Bibliography

238

(7)

List of Symbols

245

(1)

Index of Terms Used

246

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