A graph is a defined by G=(NG, AG, sG, tG) (subscripts are omitted whenever they are clear from the context) where N is a set of nodes, A is a set of arcs, s: A → N is a function assigning a source node to every arc, and t: A → N is a function assigning a target node to every arc.
This is pretty much like a normal directed graph (or digraph, or network, as you like) with the only difference that you may have many arcs between the same source/target pair. Graphs of this kind are sometimes called multigraphs, but since in our context this is what we need we prefer to stick to the simpler term graph.
Given two graphs G and H, a (graph) morphism φ: G → H is a pair of maps φN: NG → NH and φA: AG → AH_ (again, the subscripts will be omitted when they are clear), such that t(φ(a))=φ(t(a)) and s(φ(a))=φ(s(a)) for every arc a of G.
We say that the morphism is an epimorphism if both maps are surjective, and an isomorphism if both maps are bijective. An isomorphism from a graph to itself is called an automorphism. Automorphisms form a group under function composition.
Let ξ: G → B be a graph morphism. For every node x of B, the set of nodes of G that are mapped to x are called the fibre of ξ over x. The fibres of ξ form a partition of the set of nodes (i.e., an equivalence relation between the nodes) of G.
Let ξ: G → B be a graph morphism, a be an arc of B and y be a node of G such that ξ(y)=t(a) (that is, y is in the fibre of the target of a). Consider the set X(a,x) of arcs of G that have target y and that are mapped by ξ to a. We say that this pair (a,x) has a
- deficiency of 1 if the set X(a,x) is empty
- excess of k if the set X(a,x) has cardinality k+1≥2.
The sum of all deficiencies/excesses is called the global deficiency/excess of the morphism ξ. The sum of the global deficiency and excess of ξ is called the total error of ξ.
A fibration is a morphism with total error 0. Formally (and equivalently) it can be defined as a morphism such that for every arc a of the base and every node y in the fibre of its target, there is precisely one arc of the upper graph that has target y and image a. Any morphism with small total error may be called quasi-fibration. Since there is no bound on how large the total error can be, in fact the word quasi-fibration can be used as a synonym of morphism, but when we say "quasi-fibration" we somehow imply that we want its total error to be small.
Given a graph G, an equivalence relation ≅ between its nodes is called a local in-isomorphism iff for any two nodes x,x' such that x≅x' there is a bijection between the arcs a with target x and the arcs a' with target x' such that s(a)≅s(a').
The following holds:
THEOREM: ≅ is a local in-isomorphism for the nodes of G iff there is a graph B and a fibration ξ: G → B whose fibres are ≅.
So, local in-isomorphism is a concept that is strictly related to that of fibration, although, a fibration is richer in the sense that it also describes an equivalence relation between arcs (something that the local in-isomorphism concept does not include).
We think of a fibration φ: G → B as a way to "squeeze" G. It is natural to think if there is a somehow maximal way to squeeze G, in the precise sense that its associated equivalence relation is the coarsest possible (i.e., one that puts together as many pairs of nodes as possible). The answer is positive:
THEOREM: Given a graph G there exists a graph B (called the minimum base of G) and an epimorphic fibration μ: G → B such that:
- every epimorphic fibration from B is an isomorphism (i.e., B cannot be nontrivially fibred);
- any other μ': G → B' with the same property induces the same local in-isomorphism as μ on the nodes of G.
What the above theorem says, essentially, is that there is a unique coarsest local in-isomorphism. And, a unique (up-to isomorphism) minimum epimorphic-fibration base. The fibration μ is not unique, though, albeit only the arc-component can change.
The last theorem can be turned into a construction, that is, into an algorithm that in fact builds the minimum base for a given graph. The simplest (although not particularly effective) way to build the minimum base uses the concept of universal total graph (a.k.a., view): given a graph G and a node x, consider the following rooted in-tree VIEW(G,x):
- its nodes are the paths in G ending at x (by this we mean "all the paths", including the non-simple ones); a path is a finite sequence of arcs such that the target of every arc is the source of the following arc; this set of paths is typically infinite;
- a path (a1,a2,...,ak) is a child of (a2,...,ak) (the root being the empty path, which has no parent).
Define now an equivalence relation ≡ on the nodes of G where two nodes x and y are equivalent iff they have isomorphic views (i.e., if the two trees VIEW(G,x) and VIEW(G,y) are isomorphic trees).
The minimum base B can be built explicitly as follows:
- its nodes are the equivalence classes of ≡
- between class X and class Y there are as many arcs as there are arcs from nodes of X to any specific node of Y (by definition, this number is independent on the way you choose that specific node in Y).
As we said, this algorithm is not especially efficient; you may even wonder that it is in fact an algorithm because it requires to decide if two (potentially infinite) trees are isomorphic. It can be proven, though, that two views are isomorphic if and only if they are isomorphic when truncated after n levels (where n is the number of nodes of G), which makes the decision algorithmically sound.
There are other and more efficient ways to accomplish the same job; the best known is Cardon-Crochemore's algorithm [Cardon, Alain, and Maxime Crochemore. Partitioning a graph in O (¦ A¦ log2¦ V¦). Theoretical Computer Science 19.1 (1982): 85-98]. We shall often use Cardon-Crochemore to refer to the relation ≡ defined above, albeit, in principle, there is no need to use Cardon-Crochemore's algorithm to obtain it.