nLab
graph

This page is about the notion in combinatorics. For other notions of the same name see at graph of a function and graph of a functor.


Contents

Idea

A graph is a collection of vertices and edges; each edge links a pair of vertices. There are several variations on the idea, described below.

This is the sense of graph in combinatorics; the other sense in high-school algebra, which interprets a morphism f:ABf: A \to B as a subobject of the product A×BA \times B, is unrelated; see graph of a function for more on this.

Definitions

Let VV and EE be sets; call an element of VV a vertex and an element of EE an edge. A graph is given by VV, EE, and a mapping dd that interprets edges as pairs of vertices. Exactly what this means depends on how one defines ‘mapping that interprets’ and ‘pair’; the possibilities are given below. We will need the following notation:

  • V 2V^2 is the cartesian product of VV with itself, the set of ordered pairs (x,y)(x,y) of vertices;
  • Δ V\Delta_V is the diagonal subset of VV, the set of pairs (x,x)(x,x), so that its complement V 2Δ VV^2 \setminus \Delta_V is the set of pairs as above where xyx \neq y;
  • V2\left\langle{V \atop 2}\right\rangle is the quotient set of V 2V^2 in which (x,y)(x,y) is identified with (y,x)(y,x), the set of unordered pairs {x,y}\{x,y\} of vertices;
  • (V2)\left({V \atop 2}\right) is the quotient set of V 2Δ VV^2 \setminus \Delta_V in which (x,y)(x,y) is identified with (y,x)(y,x), the set of unordered pairs where xyx \neq y.

We are now ready for the first batch of definitions.

  • For a simple graph, a pair of vertices is a subset of VV of cardinality 22, and we interpret edges as unordered pairs of vertices in a one-to-one way. Thus a simple graph is given by VV, EE, and an injective function d:E(V2)d: E \hookrightarrow \left({V \atop 2}\right). Among graph theorists, this is the standard meaning of ‘graph’ unless another is specified.

  • For a multigraph, a pair of vertices is the same as above, but we interpret edges as pairs of vertices in a many-to-one way. Thus a multigraph is given by VV, EE, and an arbitrary function d:E(V2)d: E \to \left({V \atop 2}\right).

  • For a loop graph, a pair of vertices is any subset of the form {x,y}\{x,y\}, where x=yx = y is allowed, and we interpret edges as pairs of vertices in a one-to-one way again. Thus a loop-graph is given by VV, EE, and an injective function d:EV2d: E \hookrightarrow \left\langle{V \atop 2}\right\rangle.

  • For a pseudograph, a pair of vertices is as in a loop graph, while edges are interpreted as pairs of vertices as in a multigraph. Thus a pseudograph is given by VV, EE, and a function d:EV2d: E \to \left\langle{V \atop 2}\right\rangle.

Note: While ‘simple graph’ is unambiguous, the other terms above are not. In particular, ‘multigraph’ sometimes means a pseudograph, ‘pseudograph’ sometimes means a loop graph, and ‘loop graph’ sometimes means a pseudograph. These could be made unambiguous by saying ‘simple multigraph’, ‘simple loop graph’, and ‘multipseudograph’, respectively, but we will try to keep our terminology short.

In all four of the above, edges are interpreted as unordered pairs. If we instead interpret edges as ordered pairs, then we get four new concepts:

  • A directed graph consists of VV, EE, and an injective function d:EV 2Δ Vd: E \hookrightarrow V^2 \setminus \Delta_V;
  • a directed multigraph consists of VV, EE, and a function d:EV 2Δ Vd: E \to V^2 \setminus \Delta_V;
  • a directed loop graph consists of VV, EE, and an injective function d:EV 2d: E \hookrightarrow V^2;
  • a directed pseudograph consists of VV, EE, and a function d:EV 2d: E \to V^2.

Directed pseudographs are commonly used in category theory, where they are often called ‘directed graphs’, ‘digraphs’, or (less ambiguously) ‘quivers’.

The same terminological ambiguities as above apply here as well, and they can be resolved in the same way, including using ‘simple directed graph’ for a directed graph if necessary. One can also use ‘undirected’ in place of ‘directed’ to emphasise that the previous definitions apply instead of these.

It is always possible to interpret any kind of graph as a directed pseudograph (a quiver), in which there happens to be at most one edge between a given pair of vertices, or there happen to be no loops (or alternatively exactly one of every possible kind of loop), or in which there is an edge from xx to yy if and only if there is an edge from yy to xx, or some mixture of these.

Auxiliary definitions

The term arc is often used for an ordered edge, while line is sometimes used for an unordered edge. We say that an arc ee with d(e)=(x,y)d(e) = (x,y) is an arc from xx to yy, while a line ee such that d(e)={x,y}d(e) = \{x,y\} is a line between xx and yy. In either case, a loop is an edge from a vertex to itself or between a vertex and itself; only (possibly directed) loop graphs and pseudographs can have loops.

Given any sort of graph, we can define a binary relation on VV; say that xx and yy are adjacent, written xyx \sim y, if there exists an edge ee such that d(e)=(x,y)d(e) = (x,y) or d(e)={x,y}d(e) = \{x,y\}. A directed loop graph is determined entirely by this relation; we may say that it is VV equipped with a binary relation. Then a simple directed graph is VV equipped with an irreflexive relation (or equivalently a reflexive relation), and an undirected loop graph is VV equipped with a symmetric relation.

A graph is finite if VV and EE are both finite sets. Given a linear ordering of the vertices of a finite graph, its adjacency matrix is a square matrix whose (i,j)(i,j)th entry gives the number of edges ee between the iith and jjth vertices or from the iith vertex to the jjth vertex. In the examples above where a graph is determined by a binary relation on VV, then matrix multiplication gives composition of relations.

Morphisms of graphs

An isomorphism from G=(V,E,d)G = (V,E,d) to G=(V,E,d)G' = (V',E',d') consists of a bijection f:VVf: V \to V', together with a bijection from EE to EE' (also denoted ff) such that ff commutes with dd; that is, d(f(e))=(f(x),f(y))d(f(e)) = (f(x),f(y)) or d(f(e))={f(x),f(y)}d(f(e)) = \{f(x),f(y)\} whenever d(e)=(x,y)d(e) = (x,y) or d(e)={x,y}d(e) = \{x,y\} (as appropriate). Two graphs GG and GG' are isomorphic if there exists such an isomorphism. Then finite graphs GG and GG' are isomorphic if and only if they have the same number of vertices and, for some ordering of their vertices, they have the same adjacency matrix.

A morphism from GG to GG' should consist of functions f:VVf: V \to V' and f:EEf: E \to E' such that ff commutes with dd. However, some authors allow f(e)f(e) to be undefined if d(e)=(x,y)d(e) = (x,y) or d(e)={x,y}d(e) = \{x,y\} but f(x)=f(y)f(x) = f(y) when using a notion of graph where loops are forbidden. The difference amounts to whether one interprets a simple graph as a special kind of loop graph in which no loops exist (the first kind of morphism) or in which each vertex has a unique loop (the second kind of morphism). Either way, an isomorphism (as defined above) is precisely an invertible morphism.

Mike Shulman: Isn’t there something backwards about defining “isomorphic” and then “isomorphism” and then “morphism”? Doesn’t the logic generally flow in the other direction (especially around here)?

David Roberts: well at least there’s a historical precedent: this is how Bourbaki would have done it via structures :)

Toby: That, and it's simpler to state the definition of ‘isomorphic’ than ‘isomorphism’. Not to mention that graph theorists, in my experience, tend to care much more about the property of being isomorphic than the structure of having an isomorphism. As for ‘morphism’, there's even disagreement about what that should be; I think that my definition is the obvious correct one, but it disagrees with the one at, for example, Wikipedia (although they had my definition in the past); both versions give the same notion of isomorphism, however.

Mike Shulman: Well, but we aren’t graph theorists here, are we? Isn’t it okay for us to rephrase their definitions in the more categorically sensible order?

Toby: I disagree that ‘morphism’ before ‘isomorphism’ is more categorially sensible. That's like defining \leq before ==; sometimes useful, sometimes not. Since I am getting ambiguity about morphisms in what I find online, I'd prefer to do isomorphisms first. With luck, I'll find some terminology to distinguish the two kinds of morphisms, or we can make up our own.

Mike Shulman: Okay, I’ll accept that sometimes it makes sense to have isomorphisms before morphisms. Certainly there are other situations in which the notion of isomorphism is more obvious, or less subject to debate, than the notion of morphism. But I am happy that now “isomorphism” comes before “isomorphic.”

RonnieBrown: I hope it is helpful to add the reference below, which also contains quite a few references to categorical treatments of graphs.

Under the second notion of morphism (where simple graphs are identified with sets equipped with a symmetric reflexive relation), the category of simple graphs has many desirable properties (q.v.).

Flavors of graphs

References

  • Frank Harary (1969), Graph Theory, Addison-Wesley.

  • Frank Harary and E.M. Palmer (1973), Graphical Enumeration, Academic Press.

  • Joachim Lambek and Philip Scott (1986), Introduction to Higher Order Categorical Logic, Cambridge University Press.

  • Ronnie Brown, I. Morris, J. Shrimpton, and C.D. Wensley (2008), Graphs of Morphisms of Graphs, Electronic Journal of Combinatorics, A1 of Volume 15(1), 1–28.

  • Bill Lawvere (1989), Qualitative distinctions between some toposes of generalized graphs, in Categories in computer science and logic (Boulder, CO, 1987), volume 92 of Contemporary Mathematics, 261–299. American Mathematical Society, Providence, RI.

  • E. Babson, H. Barcelo, M. de Longueville, R. Laubenbacher, A Homotopy Theory for Graphs, arXiv:math/0403146

Discussion of use of simplicial complexes in graph theory:

Revised on March 28, 2014 02:47:36 by Urs Schreiber (185.37.147.12)