A Beginner's Guide to Graph Theory

Front Cover
Springer Science & Business Media, Jun 15, 2000 - Mathematics - 230 pages
1 Review
Because of its wide applicability, graph theory is one of the fast-growing areas of modern mathematics. Graphs arise as mathematical models in areas as diverse as management science, chemistry, resource planning, and computing. Moreover, the theory of graphs provides a spectrum of methods of proof and is a good train ing ground for pure mathematics. Thus, many colleges and universities provide a first course in graph theory that is intended primarily for mathematics majors but accessible to other students at the senior Ievel. This text is intended for such a course. I have presented this course many times. Over the years classes have included mainly mathematics and computer science majors, but there have been several engineers and occasional psychologists as weil. Often undergraduate and graduate students are in the same dass. Many instructors will no doubt find themselves with similar mixed groups. lt is to be expected that anyone enrolling in a senior Ievel mathematics course will be comfortable with mathematical ideas and notation. In particular, I assume the reader is familiar with the basic concepts of set theory, has seen mathematical induction, and has a passing acquaintance with matrices and algebra. However, one cannot assume that the students in a first graph theory course will have a good knowledge of any specific advanced area. My reaction to this is to avoid too many specific prerequisites. The main requirement, namely a little mathematical maturity, may have been acquired in a variety of ways.
 

What people are saying - Write a review

User Review - Flag as inappropriate

goodprvs

Contents

Graphs
1
12 Some Definitions
4
13 Degree
11
Walks Paths and Cycles
15
22 Weights and Shortest Paths
19
23 Euler Walks
23
24 Hamilton Cycles
26
25 The Traveling Salesman Problem
31
Planarity
105
82 Eulers Formula
108
83 Maps Graphs and Planarity
111
Ramsey Theory
115
92 Ramsey Multiplicity
120
93 Application of SumFree Sets
123
94 Bounds on Classical Ramsey Numbers
125
95 The General Case of Ramseys Theorem
129

Cuts and Connectivity
35
32 Blocks
37
33 Connectivity
40
Trees
43
42 Spanning Trees
46
43 Minimal Spanning Trees
51
Linear Spaces Associated with Graphs
55
52 The Power Set as a Vector Space
56
53 The Vector Spaces Associated with a Graph
58
54 The Cutset Subspace
60
55 Bases and Spanning Trees
63
Factorizations
69
62 Tournament Applications of OneFactorizations
75
63 A General Existence Theorem
77
64 Graphs Without OneFactors
81
Graph Colorings
85
72 Brooks Theorem
89
73 Counting Vertex Colorings
91
74 EdgeColorings
96
75 Class 2 Graphs
99
Digraphs
131
102 Orientations and Tournaments
135
103 Directed Euler Walks
139
Critical Paths
143
112 Critical Path Analysis
146
113 Critical Paths Under Uncertainty
153
Flows in Networks
159
122 Maximal Flows
165
123 The Max Flow Min Cut Theorem
171
124 The Max Flow Min Cut Algorithm
173
125 Supply and Demand Problems
179
Computational Considerations
185
132 Data Structures
188
133 Some Graph Algorithms
190
134 Intractability
194
References
197
Hints
205
Answers and Solutions
207
Index
225
Copyright

Other editions - View all

Common terms and phrases

Popular passages

Page 203 - TW HAYNES, ST HEDETNIEMI, AND PJ SLATER. Fundamentals of domination in graphs.
Page 203 - JW Moon, Topics on Tournaments (Holt, Rinehart and Winston, New York, 1968).
Page 204 - Roberts, FS, Graph Theory and its Applications to Problems of Society, CBMS-NSF Monograph 29, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1978.

References to this book

Magic Graphs
W. D. Wallis
Limited preview - 2001
All Book Search results »

Bibliographic information