The definition of a graph, 2

A few years ago, three consecutive speakers in the pure maths seminar at Queen Mary gave three entirely different definitions of a graph. The next speaker to appear was talking on a topic completely unconnected with graphs, but someone in the audience couldn’t resist asking for his definition of a graph.

There are many definitions of a graph, which are easily seen to be equivalent; but there are also some unexpected byways. Part of the difficulty is that we have to cope with several different kinds of graphs: multiple edges may be allowed or forbidden, loops may be allowed or forbidden, and edges may be undirected or directed. Also, just around the next bend, there are hypergraphs.

So here are a few definitions, all of which are in common use, with indications of how to modify them to take account of the different kinds of graph.

  1. A graph consists of a set V of vertices, with an irreflexive and symmetric binary relation called adjacency on V. To allow loops, remove the word “irreflexive”; to allow directed edges, remove the word “symmetric”. Multiple edges require a reformulation where “relation” is replaced by “multirelation”, a multiset of ordered pairs.
  2. A graph consists of a set V of vertices, with a set E of unordered pairs (2-element subsets) of V called edges. To allow loops, replace “2-element sets” by “1- or 2-element sets”; to allow directed edges, replace “unordered pairs” by “ordered pairs”. To allow multiple edges, take a multiset of pairs rather than a set.
  3. A multigraph is an incidence structure consisting of a set V of vertices and a set E of edges, with a relation of incidence between V and E, having the property that each element of E is incident with exactly two elements of V. To allow loops, replace “exactly two” by “one or two”. This naturally extends to hypergraphs: for k-uniform hypergraphs, replace “exactly two” by “exactly k“; and for general hypergraphs, say “at least one”. It is slightly more difficult to define simple graphs in this picture. We have to impose the condition which is known in design theory as “no repeated blocks”, that is, two edges incident with the same set of vertices are equal.
  4. Closely related is the statisticians’ definition: a multigraph is a block design with blocks of size 2. Then “regular” means “equireplicate”. Forbidding repeated blocks is not a natural thing to do in this context. Also, loops are unhelpful: if a block contains only one experimental unit, then we have no way of separating treatment effects from block effects for this unit.
  5. A multigraph is a set F of flags with two partitions V and E of F satisfying the conditions that all parts of E have size 2, and a part of V and a part of E intersect in at most one flag. (Think of a flag as an incident vertex-edge pair; two flags lie in the same part of V, resp. E, if they share a vertex, resp.  an edge.) Loops are included by allowing E to have parts of sizes 1 and 2.
  6. The last definition has the feature that it fits well with the case where the graph is a map, that is, drawn on an orientable surface. Then instead of partitions, we can take permutations υ and ε whose cycle partitions are V and E respectively (so that, in particular, ε is a fixed-point-free involution). Then ε corresponds to swapping the two flags on a given edge, and υ corresponds to traversing in the positive sense the flags on a given vertex.

    If our interest is in directed graphs, another approach is possible. A digraph consists of a set V of vertices and a set E of edges, with two functions ι and τ from E to V (so that ι(e) and τ(e) are the initial and termimal vertices of e). This model naturally allows loops and multiple arcs. Forbidding loops means requiring that ι(e) ≠ τ(e) for all edges e.

    Some special kinds of digraphs allow further options for the definition. For example, a tournament is an algebra (in the sense of universal algebra) with a single binary operation • satisfying the condition that vw ∈ {v,w} for all elements v,w. The interpretation is that vw is the terminal vertex of the arc joining v and w if the two are distinct, and vv = v for all v.

    Reflexive and transitive digraphs have two interpretations. On the one hand, they are categories in which for any two objects v,w there is at most one morphism from v to w. A more surprising interpretation is that these (if finite) are just finite topological spaces in disguise! In a finite topological space, draw an arc from v to w if every open set which contains w also contains v: this is a reflexive and transitive digraph. The digraph determines the topology, since any open set S is the union of the sets R(v) consisting of all points that can be reached by directed paths from v. Moreover, every reflexive and transitive digraph arises in this way: the sets R(v) are basic open sets for the corresponding topology.

    Previous | Next

    Advertisements

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition and tagged , , , , , , , , , . Bookmark the permalink.

8 Responses to The definition of a graph, 2

  1. Stefan says:

    A most helpful overview! Of course, I would almost always call number 3 a graph, and numbers 1 and 2 simple graphs.

  2. Jon Awbrey says:

    Re: To allow multiple edges, remove the word “irreflexive” …

    Did you mean “loops” here? Or “slings” as the Bard would have it …

  3. Walter Sinclair says:

    An additional definition of an (unoriented) graph which is occasionally useful is that of a partial order of height 2 where the elements of height 2 (edges) cover at most two elements of height 1 (vertices). An edge that covers 2 vertices is a link, and 1 a loop. If 0 it is of height 1 and a vertex. Viewing it as a partial order (despite the lack of transitivity) emphasizes the distributive structure of the lattice of subgraphs and the connection of graph connectivity with topological connectivity.

  4. D. Eppstein says:

    In your definitions of a graph listed above, you say that the vertices are a set. Do you care what they are a set of? Must they be ordinals, or themselves sets, or points in a geometric space, or special vertex objects? No? Then why do you care whether the edges are unordered pairs of vertices, or special edge objects, or elements of a binary relation? A graph is a thing that behaves like a graph — the low-level implementation details aren’t relevant, in the same way that Chrome and Safari and Firefox are all web browsers even though their underlying code is completely different from each other, or in the same way that a permutation group and a group given by a presentation are both groups. It is true that the distinction between a graph and a multigraph is meaningful and useful, but in the same way we have a distinction between e.g. the finitely presentable groups and more general groups.

    • Walter Sinclair says:

      Usage governs, but divergent usages may require careful distinctions. It is far easier to say vertices are a set, and leave it at that, than to do the same with edges. You can have an edgeless graph, but not (unless we are failing to agree on definitions) a vertex-less graph.

  5. I like to define a graph as a structure G = (V,A,i,r) where V and A are disjoint sets, V being
    the set of vertices, A being the set of arcs; i: A -> V is the mapping associating to each arc its initial vertex and r: A -> A is a fixed-point free involution assigning to each arc its reverse. The edges of G are orbits of r.

    If we relax the condition on r and allow r to have fixed-points, we obtain a structure that has
    semi-edges, or pending edges. I call such a structure a pre-graph. Pre-graphs appear sometimes as quotients under covering projections.

  6. Pingback: Definition and Determination : 10 | Inquiry Into Inquiry

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s