graph theory


Graph theoryMathworldPlanetmath is the branch of mathematics that concerns itself with graphs.

The concept of graph is extraordinarily simple, which explains the wide applicability of graph theory. It is usually agreed upon that graph theory proper was born in 1736, when Euler formalized the now-famous “http://planetmath.org/node/2810bridges of Königsberg” problem. Graph theory has now grown to touch almost every mathematical discipline, in one form or another, and it likewise borrows from elsewhere tools for its own problems. Anyone who delves into the topic will quickly see that the lifeblood of graph theory is the abundancy of tricky questions and clever answers. There are, of course, general results that systematize the subject, but we also find an emphasis on the solutions of substantial problems over building machinery for its own sake.

Graph theory representation of Königsberg bridges problem

For quite a long time graph theory was regarded as a branch of topologyMathworldPlanetmath concerned with 1-dimensional simplices, however this view has faded away. The only remainder of the topological past is the topological graph theory, a branch of graph theory that primarily deals with drawing of graphs on surfaces. The most famous achievement of topological graph theory is the proof of the four-color conjecture (every political map on the surface of a plane or a sphere can be colored into four colors given that each country consists of only one piece).

Now, a (finite) graph is usually thought of as a subset of pairs of elements of a finite setMathworldPlanetmath (called vertices), or more generally as a family of arbitrary sets in the case of hypergraphsMathworldPlanetmath. For instance, Ramsey theory as applied to graph theory deals with determining how disordered can graphs be. The central result here is the Ramsey’s theorem (http://planetmath.org/RamseysTheorem2) which states that one can always find many vertices that are either all connectedPlanetmathPlanetmath or disconnected from each other, given that the graph is sufficiently large. The other result is Szemerédi regularity lemma.

The four-color conjecture mentioned above is one of the problems in graph coloringMathworldPlanetmath. There are many ways one can color a graph, but the most common are vertex coloring and edge coloringMathworldPlanetmath. In these type of coloringsMathworldPlanetmath, one colors vertices (edges) of a graph so that no two vertices of the same color are adjacentPlanetmathPlanetmathPlanetmath (resp. no edges of the same color share a common vertex). The most common problem is to find a coloring using the fewest number of colors possible. Such problems often arise in scheduling problems.

Graph theory benefits greatly from interaction with other fields of mathematics. For example, probabilistic methods have become the standard tool in the arsenal of graph theorists, and random graphMathworldPlanetmath theory has grown into a full-fledged branch of its own. There are close, mathematical links between the foundation of category theoryMathworldPlanetmathPlanetmathPlanetmathPlanetmath and graph theory, as a categoryMathworldPlanetmath can be defined as a special type of meta-graph, and a supercategoryPlanetmathPlanetmath may also have a meta-graph representation as a meta-category ([1]). Moreover, a graph can be regarded as a one-dimensional CW complex. Free groupoids can be employed to generate graphs using highly efficient computer programming; thus, the Cayley graphMathworldPlanetmath allows one to form a graph from a group, and the transformationMathworldPlanetmathPlanetmath groupoidPlanetmathPlanetmathPlanetmath is a way to form a groupoid from a group. On the other hand, the underlying graph of a transformation groupoid is a way to form a graph from a groupoid. Moreover, an isomorphismMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath graph theorem proves that the underlying graph of a transformation groupoid is isomorphic to the Cayley graph of the group whose action on itself forms the transformation groupoid. Graphs also have several applications in theoretical physics, as for example in the case of Feynman diagrams (that are graphs). Furthermore, there are several extensionsPlanetmathPlanetmath of the graph concept such as the hypergraph; thus, many of the definitions of types of graphs carry over to hypergraphs, even though a hypergraph is a simple incidence structure. Examples are presented under the hypergraph entry of k-uniform and k-regular hypergraphs, and the connection is made to matrices via the incidence matrix associated with a hypergraph.

There is an alternative approach to defining abstract graphs in terms of graph morphisms in the category of graphs.

Definition 1.1 A graph morphism f from graph A to graph B can be defined as a pair of functions fE:AEBE, and fV:AVBV, preserving the source and target maps s,t:AEAV, as well as the dual map ϵ:AVAE , where AE is the set of graph edges in graph A, and AV is the set of graph vertices in graph A; BE, and BV are, respectively, the set of edges and the set of vertices of graph B.

References

  • 1 S. Mac Lane and I. Moerdijk. Sheaves in Geometry and Logic., Springer-Verlag: New York, Berlin and Heidelberg (2000).
Title graph theory
Canonical name GraphTheory
Date of creation 2013-05-16 20:59:21
Last modified on 2013-05-16 20:59:21
Owner karteef (1114)
Last modified by unlord (1)
Numerical id 50
Author karteef (1)
Entry type Topic
Classification msc 81Q30
Classification msc 18G30
Classification msc 05C50
Classification msc 55U10
Classification msc 18-00
Classification msc 05C25
Classification msc 05C99
Synonym category theory
Related topic Graph
Related topic Hypergraph
Related topic Category
Related topic CategoryTheory
Related topic EulersPolyhedronTheorem
Related topic DigraphMathworldPlanetmath
Related topic Tree
Related topic BinaryTree
Related topic ProbabilisticMethod
Related topic HamiltonianCycle
Related topic TournamentMathworldPlanetmath
Related topic RamseysTheorem
Related topic Coloring
Related topic GraphTopology
Related topic DirectedGraph
Related topic DepthFirstSearch
Related topic DijkstrasAlgorithm
Defines graph morphism
Defines abstract graph
Defines category of graphs