Is Category Theory similar to Graph Theory?

The following author noted:

Roughly speaking, category theory is graph theory with additional structure to represent composition.

My question is: Is Category Theory similar to Graph Theory?


In fact, “Roughly speaking, category theory is graph theory with additional structure to represent composition.” is a good summary of the connection between the notion of a graph (meaning here: directed multigraph) and the notion of a category. Here is a way of how to make this precise:

Let O be a set (“set of vertices”). Then we have a category OGraph whose objects are sets M (“set of edges”) equipped with two maps s,t:M (“source” and “target”). This category is monoidal: The unit is \mathrm{id} : O \rightrightarrows O, the tensor product of s,t : M \rightrightarrows O with u,v : N \rightrightarrows O is the fiber product M \times_{t,O,u} N equipped with the maps \rightrightarrows O induced by s and v. To any monoidal category, we may associate the category of monoid objects.

Observation. A category with object set O is the same as a monoid object in O-\mathsf{Graph}.

This description is quite nice, as it really says in how far categories are “graphs with multiplication”. If O is a class, we can make the obvious adjustments; or we use ZFC + Grothendieck universes, so that we can work with sets alone. It is possible to get rid of the O in the statement (which is quite natural, because we never want to fix the object set), but then you will have to use more advanced language: A category is the same as a monad object in the bicategory of spans.

However, this connection between the notion of a category and the notion of a graph does not mean that the theories are similar. Categories have a much richer structure, namely the composition of arrows, and this structure is used in category theory all over the place, for example in the context of commutative diagrams, universal properties, adjunctions etc. In graph theory, though, we just don’t have this kind of structure. Also, many notions in graph theory only make sense for finite graphs, whereas finite categories don’t appear so often in category theory.

There are some overlappings, though. An object of a category is called initial if it admits a unique morphism to each other object. This only refers to the underlying graph of the category, and in fact, makes sense for arbitrary (directed) graphs. We may call a vertex initial if it admits a unique edge to any other vertex. Similarly, we may speak of final vertices.

A graph is connected if there is a vertex which reaches every other vertex via some zig-zag path of edges. The same notion makes sense for categories (i.e. one doesn’t refer to the composition of arrows here). Every category is a coproduct of connected categories, and this is useful sometimes.

Two vertices in a graph are called adjacent if there is an edge between them. This notion is not so important in category theory because often one wants to know more than just the existence of a morphism. Moreover, in some categories, such as the category of abelian groups, there is a zero morphism between any two objects.

PS: I don’t agree with the answer by Ove Ahlman, see my comment there.

Source : Link , Question Author : hawkeye , Answer Author : Martin Brandenburg

Leave a Comment