Return to the graph theory seminar page or to mygeneral index/classroom page; other information at my home(ly) page.
Intuitively, a graph is a collection of lines (also called edges) and points (also called vertices), where each line joins two points. Technical definitions involve restrictions. Must the two endpoints of a line need to be distinct? (If not, the edge is called a loop.) Can more than one line have the same pair of endpoints? (If so, these lines are called parallel edges.) Pairs can be taken in the unordered sense or with a direction (first to last), that is, as an arrow.
We shall consider (usually) a simple graph G = (V,E) consisting of a nonempty set V of vertices and a set E of edges, where E is a subset of C(V,2), the family of all two-element subsets of V. This excludes loops and parallel edges. An edge e = {i,j} is said to join the vertices i and j, and i and j are said to be G-adjacent if they are joined by an edge of G. For now, we assume that V and W are finite. The degree of a vertex is the number of vertices to which it is adjacent.
By definition of a simple graph G, the relation of G-adjacency it induces is symmetric and irreflexive. Conversely, such a relation is induced by the graph it defines. Some graphs are more naturally thought of in terms of the relations they define while others seem more conveniently expressed as the union of their edges.
Two graphs G = (V,E) and G' = (V',E') are called isomorphic if there is a function f: V --> V' so that f is 1-1 and onto and f(v) is G'-adjacent to f(w) if and only if v is G-adjacent to w. The function is called an isomorphism, and the properties of composition of functions imply that isomorphism of graphs is an equivalence relation. Accordingly, we may speak of ``the'' graph satisfying some property, when in fact we mean an equivalence class of graphs.
The simplest graph is a single point, and it can be denoted K_1, P_1, Q_0, v, or *, depending on context, as it is an example of various graph-theoretic families. Next comes a line, which can be denoted K_2, P_2, K_1,1, Q_1, x, {v,w}, or I. All graphs can be constructed using these two components through various methods - algebraic, combinatorial, and topological.
As we build them up, it will be apparent that graphs are a natural structure in which to express the concepts of physical and computational science. Indeed, we begin with the graphical basics: path, cycle, and tree.
Physical phenomena, and certainly mechanistic ones such as in transport networks, can be seen as employing paths to transmit flow or information. Mathematically, we model such paths as finite-length sequences of vertices, or of edges, or of vertices and edges.
Paths are defined recursively: A path of length 0 is K_1, the graph with one vertex and no edges; a path of length 1 is K_2, the graph with two vertices and one edge. A path of length r+1 is obtained from one of length r by appending a new edge to one of the two endpoints. Any two paths of length $r$ are isomorphic and two paths which are isomorphic must have the same length. The path of length zero is sometimes called the trivial path, and we denote by P_n the path of length n.
As a graph, a path of positive length has exactly two endpoints, which it is said to join. A graph is said to be connected if any distinct pair of vertices is joined by a path.
The endpoints of a path are both of degree 1, while the other (interior) vertices are of degree 2. Any connected graph with two vertices of degree 1 and all other vertices of degree 2 is itself a path, of length one more than the number of interior vertices.
The pairs of vertices of any graph can be related by the existence of a path joining them, and this is clearly an equivalence relation: that is, v ~ w if and only if there is a path (in G) from v to w. The equivalence classes are called the connected components of the graph, and a connected graph has just one component.
A connected graph in which every vertex has degree 2 is called a cycle . Cycles are also well-represented in physical models - and here in addition to flow and information, one often imagines influence. There are prominent cycles in biochemistry, neuroscience, and the nuclear physics of solar radiation. As with paths, length is defined as the number of edges. Two paths are isomorphic if and only if they have the same length. and two cycles are isomorphic if and only if they have the same length. We denote a path of length n by P_{n+1} so P_n has n vertices and n-1 edges. This graph is defined for n at least 1. Let C_n denote the cycle of length n; this graph has n vertices and n edges and is defined for n at least 3.
Metaphorically, a path can ``die'' if it becomes a cycle or if it is deleted. It can ``give birth'' if, after having arrived at some vertex, it branches to more than one next neighbor. In this case, what results cannot be a path. However, it may still preserve the property of not having any cycles, and we shall find this sort of branching path in trees. In fact, the technical definition of tree which follows includes paths as a special case.
Recursively, K_1 is the only tree with one vertex, and it is termed the trivial tree. Given any tree, T = (V,E), with n vertices, we can form a tree T' = (V',E') by adding to T one new vertex w adjacent to exactly one vertex v in V. That is, V' - V is {w} and E' - E is {v,w}, where v is in V. We call this process ``adding a tail'' to T.
It is easy to see that every nontrivial tree has at least two endpoints, that no tree contains a cycle, and that every tree is connected. There are many characterizations of trees: for example, a graph is a tree if and only if it is connected and has one more vertex than edge if and only if it is connected and contains no cycle.
One can check that beginning with P_3, there are two distinct isomorphism classes of graphs which can be produced by adding a tail, depending on whether we add it to the interior point or two one of the two (indistinguishable) endpoints. Starting with P_5, on the other hand, we could produce three different graphs by adding a tail. If tails are added sequentially with all of them being attached to the same vertex, then the tree is called a ``star'' and consists of one vertex of positive degree and all remaining vertices of degree one.
Stars are the trees which are most unlike paths; stars represent breadth-first search, while paths correspond to depth-first search.
Misprints corrected up to here (8/8/05)
The idea of attaching a tail can be generalized. Suppose instead of choosing one vertex in T we choose two distinct vertices which are not adjacent. (Hence, such a choice is not possible for P_2.) If the vertices are v and w, then we add a new edge {v,w} to the graph. We refer to this as attaching an edge to at v and w, and the previous notion of tail is attaching an edge at only one vertex. Notice that for P_n (n at least 3) if we attach an edge to the two endpoints, we produce C_n.
Now we can go a step further and topologize our graphs.
Points have only one topology, while edges can be naturally topologized using the topology of the unit interval I = [0,1], inherited as a subset of the real numbers. That is, a subset U of [0,1] is open provided that for any u in U there exists a positive number h = h(u) such that
u in U and for all u' in [0,1], |u - u'| < h implies u' in U.
For instance, [0,1/4) is an open subset of I since if u is in [0,1/4), then u is less than 1/4 so for h = 1/4 - r suffices.
A graph G can be viewed as an abstract space in which each edge is topologically identical to I. Take as many identical copies of I as there are edges but identify two endpoints if the two edges share a common endpoint. It is this set of points which we topologize by requiring that a subset is open if and only if its intersection with every edge is open.
There is an interesting ambiguity here. While graphs are combinatorial objects, consisting of a finite family of vertices and their two-element subsets (edges), we can simultaneously utilize continuous representations. Every graph is homeomorphic to a subset of 3-dimensional euclidean space in which two vertices are adjacent if and only if the corresponding points are joined by a straight-line segment.
More generally, we can embed the points of a graph G in some topological space X and try to find topological embeddings of I in X corresponding to each edge of G. A graph is called planar if it has an embedding in X = the euclidean plane. It is interesting to note that a graph is planar if and only if it has a straight-line segment embedding in the plane, and I have asked you to prove this for trees.