Transitive closure of multigraphs

Question

The transitive closure of a directed graph, is another directed graph which encodes the reachability of nodes from other nodes. If $G$ is a graph, the edge $(v_1,v_2)$ is in it's transitive closure $G^{tc}$ iff there is a directed path from $v_1$ to $v_2$ in $G$.

A multigraph can have multiple edges between nodes. The question is what would be natural definitions for the transitive closure of a multigraph?

An obvious answer would be the transitive closure of the induced graph (same graph with multiple edges between verices replaced with a single edge).

Are there already interesting graphs derivable from a multigraph which could earn the title of 'transitive closure'?

Answer 1

Note that the term transitive closure comes from set theory. Every (simple) directed graph $G$ naturally defines a relation $R(G)$ on $V(G)$. The transitive closure $G'$ of $G$ is the (simple) directed graph $G'$ on $V(G)$ such that $R(G')$ is the transitive closure of $R(G)$. I am certainly not an expert, but I guess we need to generalize the notion of relation, where an element can be related to another element with multiplicity.

Anyway, after all that rambling another possible answer is for each $u, v \in V(G)$, put $n(u,v)$ directed edges from $u$ to $v$, where $n(u,v)$ is the maximum number of internally disjoint directed paths from $u$ to $v$.

Answer 2

If consider a multigraph as set of nodes and set of relations, where each number of edges between two nodes have correlated relation (i.e. $(a,b) \in R_N$ means that "a and b are connected by N edges"), we can make transitive closure for each relation and, therefore, for "entire multigraph".

If, by definition, $(a,b) \in R_N \Rightarrow (a,b) \in R_{N-1}$ (i.e. $(a,b) \in R_N$ means that a and b are connected by N or more edges), then transitive closure of the induced graph should be same as induced graph of the transitive closure.

Sorry for my english :-(

Answer 3

I'm going to suggest an approach to transitive closures which will yield the usual definition, in the special case of a 'simple' digraph having an adjacency matrix with entries in {0,1}. Namely: the transitive closure can be regarded as a maximum value over weights of walks, where we regard multi-arcs as arcs with greater weight. We can then formulate two different definitions according to how you would like to define the weight of a walk.

Throughout, A(D) denotes the adjacency matrix of a (multi-)digraph D.

A. 'Max-min' approach

If you would like the weight of a walk to be the minimum weight of any edge (according to the principle of a chain being only as strong as the weakest link), you would then define

$\begin{align} A(T)\_{a,b} \;\;=\quad \max_{\ell \in \mathbb N} \; \max_{\substack{v \in V(D)^{\ell+1} \\\\ (v_0, v_{\ell+1}) = (a,b)}} \min_{0 \le j \le \ell}\; \;\Bigl[ A(D)\_{v_j,v_{j+1}} \Bigr]\;, \end{align}$

fairly straightforwardly.

B. 'Combinatoric' approach

If you would rather concieve of walk-weifghts as a product of the constituent arc-weights, as happens in sum-over-paths descriptions of probabilistic processes, you should rather define $\begin{align} A(T)\_{a,b} \;\;=\quad \sup_{\ell \in \mathbb N} \; \max_{\substack{v \in V(D)^{\ell+1} \\\\ (v_0, v_{\ell+1}) = (a,b)}} \;\; \prod_{j=0}^\ell \Bigl[ A(D)\_{v_j,v_{j+1}} \Bigr] \;, \end{align}$

where the supremum may be replaced by a maximum in the case where (as with probabilistic mixing) all arc-weights are between −1 and 1, if the network does not contain any directed cycles, or similar conditions.

(If your digraph is not acyclic, and some vertex-pairs in some strongly-connected component contains multiple arcs between them, and you don't like the idea of digraphs with countably infinitely many arcs between vertices, you may wish to replace the maximum over tuples with a maximum over non-repeating sequences, in which case the supremum also becomes a maximum. This corresponds to taking maximum wieghts of paths, rather than walks.)