A simple graph consists of a finite set V of vertices, along with a set E of edges, where edges are unordered pairs of vertices. A simple example might be a set of five people {Alexus, Bernard, Chloe, Dazi, Emily} on Facebook; the set of edges here would represent (Facebook) friendship, so that if Alexus and Bernard were friends, {Alexus, Bernard} would be an "edge."
Finite graphs are the building blocks of discrete structures and their study has applications to modern technology, computer algorithms, discrete systems, ... any finite structures in the modern computer age. Anyone working with computer algorithms must have some understanding of graph theory!
"Simple" graphs have undirected edges (there is no direction to "friendship", it is presumably a symmetric relations) and there are no multiple edges (one can't be "friends" twice on Facebook!) and there are no loops (one is a "friend" of someone else, not oneself.) Since these simple graphs were first systematically studied and promoted by Frank Harary at the University of Michigan, they are sometimes called Michigan graphs.
Here are the four different graphs with three vertices:
And here are the graphs on four vertices.
What makes two graphs "the same"? This is a mathematical question about functions. A graph on vertex set V_1 with edge set E_1 is isomorphic to ("the same as") another graph on vertex set V_2 with edge set E_2 if there is a one-to-one onto function (bijection) from V_1 to V_2 which maps the edge set E_1 onto the edge set E_2.
Given a single graph with vertex set V and edge set E, a one-to-one function from V onto V is a permutation. If the permutation maps E onto E, is is an automorphism of the graph. Given a fixed graph G(V,E), the collection of automorphisms of the graph form a group of permutations.
There are a large number of interesting questions which can be posed about graphs, many of them surprisingly difficult. A very old problem, dating from the 1800's, is the four coloring problem for planar graphs solved only by exhaustive computer search in 1976. A more difficult problem (involving lots of active research) asks for an algorithm which distinguishes between different (non-isomorphic) graphs. At this time there is no known list of graph invariants that is guaranteed to always separate two non-isomorphic graphs.
A graph has a collection of symmetries, that is, a group of automorphisms, which permute the vertices of the graph without changing the collection of edges. The structure of this automorphism group says a lot about the structure of the graph; in a similar way, every finite group may be viewed as the automorphism group of some graph. Many questions in finite group theory can be phrased in terms of interesting combinatorial structures such as finite graphs. And, conversely, many interesting questions in graph theory lead to interesting questions in algebra, in group theory, ring theory and linear algebra.
Since graphs are finite and since it is relatively easy to create a list of examples, this is a fertile area in which to engage undergraduates in mathematical exploration. Future posts will attempt to lay out some interesting research problems.
[Mathematical prerequisites: This article requires no mathematics beyond high school.]
Follow Ken W. Smith on Twitter @kenwsmith54
No comments:
Post a Comment