In a graph G, there is generally no 'internal' composition of the arrows, so that it is not a category. But the graph can always be extended into a category by adding the paths of the graph.
More precisely, the category of paths of G, denoted C(G), is the category whose objects are the vertices of the graph and the links from A to B are the paths (f1,f2,...,fn) from A to B. The composition of paths is their concatenation: the composite of
(f1,f2,...,fn): A ® B and (g1,g2,...,gm) : B ® C is
(f1,f2,...,fn ,g1,g2,...,gm) : A ® C.
As any category K is firstly a graph, we can associate to it the category of its paths C(K). This category has generally more arrows than K, and K can be deduced from C(K) by identification of two paths from A to B which have the same composite in the category K.
Conversely, let us give a graph G and, on the category of its paths C(G), a set of pairs (c,c') of paths of G with the same source and target. Then there is a smallest category C containing G as a sub-graph and in which the c and c' of each given pair have the same composite. Formally, C is the 'quotient category' of C(G) by the smallest equivalence relation identifying the two paths c and c' of each pair. We say that C is deduced from the data of generators (the arrows of G), and relations on them (the pairs of paths which are identified).
Categories modeling natural systems are often constructed in this way. The graph G of generators is a labeled graph in the sense that a real number (or a vector), called its weight, is associated to each arrow; this weight represents the force and/or the propagation delay with which information are transmitted by the arrow. A path of G is weighted by the sum of the weights of its factors; and the relations identify two paths c and c' which have the same source, target and weight. The deduced category K has for links from A to B classes of paths from A to B which have the same weight. It is a weighted category in the following sense: A category is weighted if it is a labeled graph and if the weight of a composite fg is the sum of the weights of f and g.
A concrete example
The preceding construction will be illustrated by the category of possible itineraries between a set of towns. The labeled graph G has 7 vertices representing the towns: A, A1, A2, A3, A4, A5, B and 10 arrows between them, representing roads, weighted by the length of the road (indicated in the parenthesis):
(f1,2): A ® A1, (f2,3): A1 ® A2,
(f3,5): A2 ® A3, (f4,4): A3 ® B,
(f5,6): A ® A4, (f6,8): A4 ® B,
(f7,7): A ® A5, (f8,7): A5 ® B,
(f9,12): A ® B, (f10,5): A ® A2
The category of paths C(G) has the same 7 towns as its objects, but it has 20 arrows, obtained by adding to those of G the following paths:
(f1,f2): A ® A2, (f1,f2,f3): A1 ® A3,
(f1,f2,f3,f4): A ® B, (f2,f3): A1 ® A3,
(f2,f3,f4): A1 ® B, (f3,f4): A2 ® B,
(f5,f6) and (f7,f8): A ® B,
(f10,f3): A ® A3, (f10,f3,f4): A ® B.
The length of a path is the sum of its factors. The composition of successive paths is the concatenation, for instance:
f1.(f2,f3) = (f1,f2,f3), and (f1,f2).(f3,f4) = (f1,f2,f3,f4).
In this category, there exist several links with the same length between two towns.
If a traveller is only interested in the length of the road (which determines the duration of the journey), these paths should be identified. Thus we construct the category C with its generators in G and the relations identifying paths with the same length.
(f1, f2) = f10, (f1, f2, f3) = (f10, f3),
(f1, f2, f3, f4) = (f5, f6) = (f7, f8).
C has the same 7 objects, but only 15 arrows, obtained by adding to 5 arrows to G, namely the following weighted composites:
(f23,8): A1 ® A3, (f34,9): A2 ® B,
(f123,10): A ® A3,(f234,12): A1 ® B,
(f1234,14): A ® B.
The composition is defined by:
f1.f2 = f10, f1.f23 = f123, f1.f234 = f1234 f2.f3 = f23, f2.f34 = f234,
f3.f4 = f34, f5.f6 = f1234, f7.f8 = f1234, f123.f4 = f1234
f10,f3 = f123, f10.f34 = f1234, f123.f4 = f1234.
(there are no other composites). The length of a composite is the sum of the lengths of its factors. In this category, f1234 et f9 are 2 links from A to B in C with different lengths (14 and 12).
The category of neurons
The category of neurons models a neuronal system at a given time t. It is constructed by the data of generators and relations.
First we define the labeled graph G of its generators. Its vertices are the neurons; the activity of a neuron N at t is determined by its instantaneous frequency of spikes. An arrow from N to N' corresponds to a synapse such that N is the pre-synaptic neuron and N' the post-synaptic neuron. Let us remark that two neurons may be linked by one, several or no arrows. The weight of an arrow from N to N' represents the strength of the synapse, related to the probability that the activity of N be propagated to N' and to the delay of propagation. We adopt the usual convention that the activity of a neuron N is the summation of the activities of the neurons Ni to which it is linked, pondered by the weights of the synapses linking these Ni to N.
The category of path C(G) on this graph admits the neurons for its objects, the links from N to N' are the paths formed by successive synapses, and the composition of paths is their concatenation. In this category, two paths from N to N' have the same weight if the activity of N is transmitted to N' in the same way along one of the other of the paths.
The category Neur is deduced from the data of G and of the relations on C(G) identifying two paths from N to N' which have the same weight. Thus its objects are still the neurons, but the links from N to N', called multisynaptic paths, are classes of paths with the same weight. It is a weighted category.