Graph Theory
Library Home 
Full Table of Contents 
Suggest a Link 
Library Help
http://www.math.niu.edu/~rusin/knownmath/index/05CXX.html  


Dave Rusin; The Mathematical Atlas  
A short article designed to provide an introduction to graph theory. A graph is a set V of vertices and a set E of edges  pairs of elements of V. This simple definition makes Graph Theory the appropriate language for discussing (binary) relations on sets. Among the topics of interest are topological properties such as connectivity and planarity (can the graph be drawn in the plane?); counting problems (how many graphs of a certain type?); coloring problems (recognizing bipartite graphs, the FourColor Theorem); paths, cycles, and distances in graphs (can one cross the Königsberg bridges exactly once each?). Many graphtheoretic topics are the object of complexity studies in computation (e.g. the Travelling Salesman problem, sorting algorithms, the graphisomorphism problem). The theory also extends to directed, labelled, or multiplyconnected graphs. History; applications and related fields and subfields; textbooks, reference works, and tutorials; software and tables; other web sites with this focus.  


Levels:  College 
Languages:  English 
Resource Types:  Articles 
Math Topics:  Group Theory, Graph Theory, Operations Research, Algebraic Topology 
[Privacy Policy] [Terms of Use]
© 1994 The Math Forum at NCTM. All rights reserved.
http://mathforum.org/