Biggs Theorem for Directed Cycles and Topological Invariants of Digraphs

Michael Hecht^1,2,3, Ivo F. Sbalzarini^1,2,3

¹Technische Universität Dresden, Faculty of Computer Science, Dresden, Germany.
²Max Planck Institute of Molecular Cell Biology and Genetics, Dresden, Germany.
³Center for Systems Biology Dresden, Dresden, Germany.

DOI: 10.4236/apm.2021.116037                

Abstract

We generalize Biggs Theorem to the case of directed cycles of multi-digraphs allowing to compute the dimension of the directed cycle space independently of the graph representation with linear runtime complexity. By considering two-dimensional CW complex of elementary cycles and deriving formulas for the Betti numbers of the associated cellular homology groups, we extend the list of representation independent topological inavariants measuring the graph structure. We prove the computation of the 2nd Betti number to be sharp #P hard in general and present specific representation invariant sub-fillings yielding efficiently computable homology groups. Finally, we suggest how to use the provided structural measures to shed new light on graph theoretical problems as graph embeddings, discrete Morse theory and graph clustering.

Keywords

Biggs Theorem, Elementary and Simple Cycles, CW Complexes of Graphs, Cellular and Singular Homology, Betti Numbers

1. Introduction

Graphs are widely used abstractions to model systems and interactions, e.g., in molecular chemistry [1], biochemistry [2], systems biology [3] [4], neuroscience [5], and social sciences [6]. Therefore, graph theoretical problems play a pivotal role across all disciplines of sciences. However, the combinatorical complexity of graph theoretical problems often hampers practical applications. Despite trees, planar graphs are a graph class for which most optimization or decision problems can efficiently be solved or closely be approximated. This is notably the case for the graph isomorphism problem [7], graph-coloring problems [8] and detection of Hamilton cycles [9], i.e., solving the traveling salesman problem [10]. These facts are reflected in Whitney’s theorem [11] that proves planar embeddings of 3-connected graphs to be unique up to isomorphism. However, planarity is a very strong condition on the graph G, which often does not match to instances occurring in practice. Extending considerations to graphs of higher genus allow to relax the conditions on the graph structure, which, by itself, is generated by the cycles the graph G contains. However, as counting all elementary cycles is already a #P-hard [12] problem finding an embedding of minimum genus is NP-hard [13]. In addition, the number of possible embeddings increases exponentially with the graph genus [13], which in contrast to Whitney’s Theorem makes it hard to efficiently represent G independently of its automorphism class.

Here, we address the question of whether efficiently computable invariants of graphs exist and how they can be used to measure the structural complexity of graphs independently of their representation. Biggs Theorem [14] is a classic result in graph theory that, similarly to the Euler characteristic of surfaces [15], provides such an invariant for simple digraphs.

Theorem (Biggs Theorem). The set of connected cycles $\bar{O}\left(G\right)$ of a simple digraph G generates a free R-module or vector space $\Lambda \left(G\mathrm{,}R\right)$ of dimension

${\dim }_R\Lambda \left(G\mathrm{,}R\right)=\left|E\right|-\left|V\right|+\mathrm{<mo>\; \#\; </mo>}G\mathrm{,}R=\mathbb{Z}\mathrm{,}{\mathbb{Z}}_2\mathrm{,}$ (1)

where #G denotes the connected components of G.

However, Biggs Theorem is only known to hold for the space generated by connected cycles of a simple digraph. Here we generalize the statement to the case of the directed cycle space ${\langle O\left(G\right)\rangle }_R$, $R=\mathbb{Z},{\mathbb{Z}}_2$ spanned by all directed cycles $O\left(G\right)$ of a multi-digraph G.

1.1. Statement of Contribution

We denote by $O_{\text{el}}\left(G\right)\mathrm{,}{\bar{O}}_{\text{el}}\left(G\right)$ the set of all directed or connected elementary cycles (passing no vertex twice) of a multi-digraph G and by $\mathcal{G}\left(O_{\text{el}}\left(G\right)\right)\mathrm{,}\mathcal{G}\left({\bar{O}}_{\text{el}}\left(G\right)\right)$ the induced subgraphs, respectively. Then we prove the following generalization of Biggs Theorem.

Theorem 1 (Biggs Theorem for directed cycles).Let $G=\left(V\mathrm{,}E\mathrm{,}\text{head}\mathrm{,}\text{tail}\right)$ be a multi-digraph and $\Lambda \left(G\mathrm{,}R\right)={\langle {\bar{O}}_{\text{el}}\left(G\right)\rangle }_R$ its connected cycle space with respect to $R=\mathbb{Z},{\mathbb{Z}}_2$ . Then

$\mathcal{G}\left(O_{\text{el}}\left(G\right)\right)=\mathcal{G}\left({\bar{O}}_{\text{el}}\left(G\right)\right)$ if and only if ${\langle O_{\text{el}}\left(G\right)\rangle }_R={\langle {\bar{O}}_{\text{el}}\left(G\right)\rangle }_R$. (2)

Consequently, in case of equivalence, there holds

${\dim }_R{\langle O_{\text{el}}\left(G\right)\rangle }_R=\left|E\right|-\left|V\right|+\mathrm{<mo>\; \#\; </mo>}G={\dim }_R\Lambda \left(G\mathrm{,}R\right)\mathrm{.}$ (3)

Indeed the construction of the induced subgraph $\mathcal{G}\left(O_{\text{el}}\left(G\right)\right)$ is given by the union of all strongly connected components, which therefore can be realized in $\mathcal{O}\left(\left|E\right|\right)$ [16]. Consequently, Theorem 1 allows to determine ${\dim }_R{\langle O_{\text{el}}\left(G\right)\rangle }_R$ efficiently in $\mathcal{O}\left(\left|E\right|\right)$. The efficient computation of ${\dim }_R{\langle O_{\text{el}}\left(G\right)\rangle }_R$ potentially addresses many challenging problems in graph theory. In this article, we extend the 1-dimensional CW-complex $X_1\left(G\right)$ given by the geometrical realization of G given by attaching 2-cells accordingly to a chosen set of elementary cycles $O\subseteq {\bar{O}}_{\text{el}}\left(G\right)$. Thereby, much more structural information of G is understood as topological structure. Theorem 1 enables us to derive formulas for the Betti numbers of the associated homology groups $H_k\left(G\mathrm{,}{O}_{\text{el}}\left(G\right)\mathrm{,}R\right)$, $k=0,1,2$.

Theorem 2 (Homology of the Elementary Filling). Let $G=\left(V\mathrm{,}E\mathrm{,}\text{head}\mathrm{,}\text{tail}\right)$ be a multi-digraph, $R=\mathbb{Z},{\mathbb{Z}}_2$, $O\subseteq {\bar{O}}_{\text{el}}\left(G\right)$ and $X\left(G\mathrm{,}O\right)$ the geometrical realization induced by the choice of $O\subseteq {\bar{O}}_{\text{el}}$. The associated cellular homology groups $H_k\left(G\mathrm{,}O\mathrm{,}R\right)$ are free R-modules of ranks $b_k\left(G\mathrm{,}O\mathrm{,}R\right)$, $k=0,1,2$.

i) $b_0\left(G\mathrm{,}O\mathrm{,}R\right)=\mathrm{<mo>\; \#\; </mo>}G$ and can be computed in $\mathcal{O}\left({\left|V\right|}^2+\left|V\right|\left|E\right|\right)$.

ii) $b_1\left(G\mathrm{,}O\mathrm{,}R\right)=\left|E\right|-\left|V\right|+\mathrm{<mo>\; \#\; </mo>}G-{\dim }_R{\langle O\rangle }_R$ and $b_1\left(G\mathrm{,}{\bar{O}}_{\text{el}}\left(G\right)\mathrm{,}R\right)=0$.

If $O=O_{\text{el}}\left(G\right)$ then $b_1\left(G\mathrm{,}O\mathrm{,}R\right)$ can be computed in $\mathcal{O}\left({\left|V\right|}^2+\left|V\right|\left|E\right|\right)$.

iii) $b_2\left(G\mathrm{,}O\mathrm{,}R\right)=\left|O\right|-{\dim }_R{\langle O\rangle }_R$. If $O=O_{\text{el}}\left(G\right)\mathrm{,}{\bar{O}}_{\text{el}}\left(G\right)$ then it is #P-hard (sharp P-hard) to compute $b_2\left(G\mathrm{,}O\mathrm{,}R\right)$.

Using that cellular and singular homology are isomorphic [15] (Theorem 2.35), Theorem 2 provides a path for computing the singular homology of the geometric realization $X\left(G\mathrm{,}O\right)$ of G with respect to the set of cycles $O\subseteq O_{\text{el}}\left(G\right)\mathrm{,}{\bar{O}}_{\text{el}}\left(G\right)$. To overcome the involvement of a #P-hard counting problem in iii), we suggest several representation independent sub-fillings $O⊊O_{\text{el}}\left(G\right)\mathrm{,}{\bar{O}}_{\text{el}}\left(G\right)$ allowing to compute $H_k\left(G\mathrm{,}O\mathrm{,}R\right)$, $k=\mathrm{0,1,2}$, efficiently. Consequently, the graph structure of G can be understood in terms of singular homology. In light of this fact, we revisit classic problems in graph theory as graph embeddings, discrete Morse theory and graph clustering from this new perspective.

1.2. Preleminaries

For rendering the introduced concepts of this article and the proof Theorem 1 consistent we introduce a definition of graphs that yields a notion of multi-digraphs without requiring multi-sets.

Definition 1. Let $G=\left(V\mathrm{,}E\mathrm{,}\text{head}\mathrm{,}\text{tail}\right)$ be a 4-tuple, where $V\mathrm{,}E$ are finite sets and $\text{head}\mathrm{,}\text{tail}\mathrm{<mo>\; :\; </mo>}E\to V$ are some maps. We call the elements $v\in V$ vertices and the elements $e\in E$ edges of G, while $\text{head}\left(e\right)\mathrm{,}\text{tail}\left(e\right)\in V$ are called head and tail of the edge e. An edge e with $\text{head}\left(e\right)=\text{tail}\left(e\right)$ is called a loop. In general, we call G a multi-digraph. The following cases are often relevant:

i) G is called a digraph iff the map $H\mathrm{<mo>\; :\; </mo>}E\to V\times V$, with $H\left(e\right)=\left(\text{tail}\left(e\right)\mathrm{,}\text{head}\left(e\right)\right)$ is injective.

ii) If there are no loops, i.e., $e\in E$ with $\text{tail}\left(e\right)=\text{head}\left(e\right)$, then G is called simple.

ii) G is called an undirected graph if G is a digraph and for every $e\in E$ there is $f\in E\backslash \left\{e\right\}$ with $\text{head}\left(e\right)=\text{tail}\left(f\right)$, $\text{tail}\left(e\right)=\text{head}\left(f\right)$. In this case, we slightly simplify notation by shortly writing e for the pair $e\mathrm{<mo>\; :\; </mo>}=\left(f\mathrm{,}g\right)\in E\times E$, which is then called an edge. The notion of $\text{head}\mathrm{,}\text{tail}$ can thereby be replaced by $\text{link}\mathrm{<mo>\; :\; </mo>}E\to V$ with $\text{link}\left(e\right)=\text{head}\left(e\right)\cup \text{tail}\left(e\right)$.

iv) In the special case, where $E\subseteq V\times V$ the maps $\text{head}\mathrm{,}\text{tail}$ are assumed to be canonically given by the relation of E, i.e., $\text{head}\left(\left(x\mathrm{,}y\right)\right)=y$, $\text{tail}\left(\left(x\mathrm{,}y\right)\right)=x$ for all $\left(x\mathrm{,}y\right)\in E$.

One readily observes that our definition coincides with the common understanding of graphs. As said, the notion allows to consider multiple edges $e\mathrm{,}f$ with $\text{head}\left(e\right)=\text{head}\left(f\right)$, $\text{tail}\left(e\right)=\text{tail}\left(f\right)$ by distinguishing $e\mathrm{,}f$. Thus, no considerations of multi-sets E as in [17] are needed. We denote with $\left|E\right|$, $\left|V\right|$ and #G the number of edges, vertices and the number of connected components of G, respectively.

Two edges e and f are called consecutive if $\text{head}\left(e\right)=\text{tail}\left(f\right)$ and are called connected if $\left\{\text{head}\left(e\right)\mathrm{,}\text{tail}\left(e\right)\right\}\cap \left\{\text{head}\left(f\right)\mathrm{,}\text{tail}\left(f\right)\right\}\ne \varnothing$. The degree $\mathrm{deg}\left(v\right)$ of a vertex $v\in V$ is given by the number of all edges $e\in E$ that are connected with v. A directed path $p=\left\{e_1\mathrm{,}\cdots \mathrm{,}{e}_n\right\}\subseteq E$ of length $n\in \mathbb{N}$ from a vertex u to a vertex v is a list of consecutive edges $e_i\in E$, $i=1,\cdots ,n$ such that $u=\text{tail}\left(e_1\right)$ and $v=\text{head}\left(e_n\right)$. Thereby, repetition is allowed, i.e., $e_i=e_j$, $1\le i<j\le n$ is possible. A connected path $p=\left\{e_1\mathrm{,}\cdots \mathrm{,}{e}_n\right\}\subseteq E$ from a vertex u to a vertex v is a list of possible multiple occurring connected edges that become a directed path by exchanging a subset $\left\{e_{i_1}\mathrm{,}\cdots \mathrm{,}{e}_{i_k}\right\}$, $j=1,\cdots ,k$, $k\le n$ of edges with their converse directed versions.

A directed (connected) cycle is a directed (connected) path p from some vertex $u\in V$ to itself, which can also be a loop. A cycle is elementary if every vertex it contains is passed exactly once. A cycle is called simple if each edge it contains occurs exactly once. We denote by $\bar{O}\left(G\right)\mathrm{,}O\left(G\right)$ the set of all connected or directed cycles and with ${\bar{O}}_{\text{el}}\left(G\right)\mathrm{,}{O}_{\text{el}}\left(G\right)$ the set of all directed, connected elementary cycles, respectively. In fact, every simple or even non-simple cycle $c\in \bar{O}\left(G\right)\mathrm{,}O\left(G\right)$ is generated by passing through several elementary cycles $c_1\mathrm{,}\cdots \mathrm{,}{c}_n\in {\bar{O}}_{\text{el}}\left(G\right)\mathrm{,}{O}_{\text{el}}\left(G\right)$, $n\in \mathbb{N}$.

Given $c=\left(e_1,\cdots ,e_n\right),d=\left(f_1,\cdots ,f_n\right)\in \bar{O}\left(G\right)$, $n\in \mathbb{N}$ we introduce the equivalence relation $c\sim d$ iff d can be derived from $c$ by cyclic reordering, i.e., there is $k\in \mathbb{N}$ with $e_{i+k\mathrm{mod}n+k+1}=f_i$, $i=1,\cdots ,n$. We denote with $\bar{O}\left(G\right){\mathrm{<mo>\; /\; </mo>}}_{\sim }$ and $O\left(G\right){\mathrm{<mo>\; /\; </mo>}}_{\sim }$ the quotients of non-equivalent cycles and count $\bar{O}\left(G\right)\mathrm{,}O\left(G\right)$ up to equivalence, i.e., $\left|\bar{O}\left(G\right)\right|\mathrm{<mo>\; :\; </mo>}=\left|\bar{O}\left(G\right){\mathrm{<mo>\; /\; </mo>}}_{\sim }\right|$, $\left|O\left(G\right)\right|\mathrm{<mo>\; :\; </mo>}=\left|O\left(G\right){\mathrm{<mo>\; /\; </mo>}}_{\sim }\right|$. While non-elementary cycles $c\mathrm{,}{c}^{\prime }$ can coincide in their edge sets but differ in their orderings an elementary cycle is uniquely determined up to cyclic reordering of its edges. This makes elementary cycles the pivotal choice of our considerations. We will slightly abuse notation by making no difference between $O_{\text{el}}\left(G\right)\mathrm{,}{\bar{O}}_{\text{el}}\left(G\right)$ and $O_{\text{el}}\left(G\right){\mathrm{<mo>\; /\; </mo>}}_{\sim }\mathrm{,}{\bar{O}}_{\text{el}}\left(G\right){\mathrm{<mo>\; /\; </mo>}}_{\sim }$, respectively.

Example 1. For G in Figure 1 the cycle $c_0=\left\{e\mathrm{,}f\mathrm{,}g\mathrm{,}h\mathrm{,}k\mathrm{,}l\mathrm{,}m\mathrm{,}o\mathrm{,}n\right\}$ is a directed, simple and non-elementary cycle, while the directed cycles $c_1=\left\{e\mathrm{,}f\mathrm{,}g\mathrm{,}h\mathrm{,}k\mathrm{,}n\right\}$ and $c_2=\left\{o\mathrm{,}l\mathrm{,}m\right\}$ are elementary. Certainly, $c_0$ is given by passing through $c_1$ and $c_2$. Further, the cycle $c_3=\left\{e\mathrm{,}f\mathrm{,}g\mathrm{,}h\mathrm{,}k\mathrm{,}n\mathrm{,}o\mathrm{,}l\mathrm{,}m\right\}\cancel{\sim }{c}_0$ while $c_0\sim \left\{l\mathrm{,}m\mathrm{,}o\mathrm{,}n\mathrm{,}e\mathrm{,}f\mathrm{,}g\mathrm{,}h\mathrm{,}k\right\}=c_4$. The only reorderings of $c_1\mathrm{,}{c}_2$ keeping the edges consecutive are cyclic reorderings.

Figure 1. Elementary and simple cycles.

With $G\backslash e$, $G\backslash v$ we denote the graphs obtained by deleting the edge e or the vertex v and all its connected edges. Further, $\mathcal{G}(\cdot )$, $\mathcal{E}(\cdot )$, $\mathcal{V}(\cdot )$ denote the graph, the set of all edges, and the set of all vertices induced by a set of graphs, edges and vertices. By $\mathcal{P}\left(A\right)$ we denote the power set of a given set A of finite cardinality $\left|A\right|\in \mathbb{N}$.

1.3. Outline

In Section 2, we provide all ingredients to generalize Bigss Theorem and give the proof in Section 3. In Section 4, the 2-dimensional elementary CW complex of G and its homology is studied. Section 5 considers representation invariant sub-fillings while Sections 6 and 7 suggest applications and yield a conclusion of our results.

2. The Module of Cycles

To provide an algebraic notion of cycles we define the characteristic vector representing how often and in which direction an edge is passed by a cycle or path.

Definition 2 (Characteristic Vector). Let $G=\left(V\mathrm{,}E\mathrm{,}\text{head}\mathrm{,}\text{tail}\right)$ be a multi-digraph we introduce the free R-modules, $R=\mathbb{Z}\mathrm{,}{\mathbb{Z}}_2$

$\mathbb{V}\left(G\right)\mathrm{<mo>\; :\; </mo>}=\underset{v\in V}{{\displaystyle \oplus }}\mathbb{Z}v\mathrm{,}{\mathbb{V}}_2\left(G\right)\mathrm{<mo>\; :\; </mo>}=\mathbb{V}\left(G\right)\mathrm{<mo>\; /\; </mo>2}\mathbb{V}\left(G\right)=\underset{v\in V}{{\displaystyle \oplus }}{\mathbb{Z}}_{2}v$ (4)

$\mathbb{E}\left(G\right)\mathrm{<mo>\; :\; </mo>}=\underset{e\in E}{{\displaystyle \oplus }}\mathbb{Z}e\mathrm{,}{\mathbb{E}}_2\left(G\right)\mathrm{<mo>\; :\; </mo>}=\mathbb{E}\left(G\right)\mathrm{<mo>\; /\; </mo>2}\mathbb{E}\left(G\right)=\underset{e\in E}{{\displaystyle \oplus }}{\mathbb{Z}}_{2}e\mathrm{.}$ (5)

Let $\epsilon =\left\{e_1\mathrm{,}\cdots \mathrm{,}{e}_n\right\}$, $e_i\in E$, $i=\mathrm{1,}\cdots \mathrm{,}n\in \mathbb{N}$ be an ordered list of connected edges. Then for $i=1,\cdots ,n-1$ we define

$x_i=\{\begin{array}{ll}1\mathrm{,}\hfill & \text{if}{e}_i\mathrm{,}{e}_{i+1}\text{are consecutive}\hfill \\ -1\mathrm{,}\hfill & \text{if}{e}_i\mathrm{,}{e}_{i+1}\text{are connected but not consecutive}\hfill \end{array}$ (6)

If $\epsilon \in \bar{O}\left(G\right)$ is a cycle then we set $x_n=1$ if $e_n\mathrm{,}{e}_1$ are consecutive and $x_n=-1$ else. If $\epsilon \cancel{\in }\bar{O}\left(G\right)$ then we set $x_n=0$. By considering $y_i=x_i\mathrm{mod}2\mathbb{Z}$, $i=1,\cdots ,n$ the vectors

$\left[\epsilon \right]={\displaystyle \underset{i=1,\cdots ,n}{\sum }}{x}_i{e}_i\in \mathbb{E}\left(G\right),{\left[\epsilon \right]}_2={\displaystyle \underset{i=1,\cdots ,n}{\sum }}{y}_i{e}_i\in {\mathbb{E}}_2\left(G\right)$ (7)

are called the characteristic vectors of $\epsilon$ with respect to $\mathbb{Z}$ -and ${\mathbb{Z}}_2$ -coefficients.

Remark 1. We want the following fact to be clear. The characteristic vector depends on the ordering of $\epsilon$. However, if $c_1\mathrm{,}{c}_2\in {\bar{O}}_{\text{el}}\left(G\right)$ are connected elementary cycles such that $c_1\sim c_2$ are equivalent. Then $\left[c_1\right]=\pm \left[c_2\right]$ holds. If $c_1\mathrm{,}{c}_2\in O_{\text{el}}\left(G\right)$ are directed then even $\left[c_1\right]=\left[c_2\right]$ holds. Thus, the maps

$\chi \mathrm{<mo>\; :\; </mo>}{O}_{\text{el}}\left(G\right){\mathrm{<mo>\; /\; </mo>}}_{\sim }\to \mathbb{E}\left(G\right)\mathrm{,}c\mapsto \left[c\right]\mathrm{,}{\chi }_2\mathrm{<mo>\; :\; </mo>}{\bar{O}}_{\text{el}}\left(G\right){\mathrm{<mo>\; /\; </mo>}}_{\sim }\to {\mathbb{E}}_2\left(G\right)\mathrm{,}c\mapsto {\left[c\right]}_2$ (8)

are well defined.

Definition 3 (Incidence operator). Let $G=\left(V\mathrm{,}E\mathrm{,}\text{head}\mathrm{,}\text{tail}\right)$ be a multi-digraph. We denote with $\mathcal{I}\left(G\mathrm{,}\mathbb{Z}\right)\mathrm{<mo>\; :\; </mo>}\mathbb{E}\to \mathbb{V}$, $\mathcal{I}\left(G\mathrm{,}{\mathbb{Z}}_2\right)\mathrm{<mo>\; :\; </mo>}{\mathbb{E}}_2\to {\mathbb{V}}_2$ the $\mathbb{Z}\mathrm{,}{\mathbb{Z}}_2$ -linear incidence operator operators, defined on the generators by

$\mathcal{I}\left(G\mathrm{,}\mathbb{Z}\right)\left[e\right]=\text{head}\left(e\right)-\text{tail}\left(e\right)\mathrm{,}$ (9)

$\mathcal{I}\left(G\mathrm{,}{\mathbb{Z}}_2\right){\left[e\right]}_2=\text{head}\left(e\right)+\text{tail}\left(e\right)\mathrm{mod}2\mathbb{V}\left(G\right)\mathrm{.}$ (10)

By choosing an enumeration $V\cong \left\{v_1\mathrm{,}\cdots \mathrm{,}{v}_{\left|V\right|}\right\}$, $E=\left\{e_1\mathrm{,}\cdots \mathrm{,}{e}_{\left|E\right|}\right\}$ we can represent $\mathcal{I}\left(G\mathrm{,}\mathbb{Z}\right)$ by the classic incidence matrix $I\left(G\mathrm{,}\mathbb{Z}\right)={\left({\theta }_{ij}\right)}_{\begin{array}{l}1\le i\le \left|E\right|\\ 1\le j\le \left|V\right|\end{array}}$ with

${\theta }_{ij}\mathrm{<mo>\; =\; </mo>}\{\begin{array}{ll}\mathrm{0,}\hfill & \text{if}\text{tail}\left(e_i\right)=v_j\text{and}\text{head}\left(e_i\right)=v_j\mathrm{,}\hfill \\ \mathrm{0,}\hfill & \text{if}\text{tail}\left(e_i\right)\ne v_j\text{and}\text{head}\left(e_i\right)\ne v_j\mathrm{,}\hfill \\ \mathrm{1,}\hfill & \text{if}\text{tail}\left(e_i\right)=v_j\text{and}\text{head}\left(e_i\right)\ne v_j\mathrm{,}\hfill \\ -\mathrm{1,}\hfill & \text{if}\text{tail}\left(e_i\right)\ne v_j\text{and}\text{head}\left(e_i\right)=v_j\mathrm{.}\hfill \end{array}$ (11)

The notion of $I\left(G\mathrm{,}{\mathbb{Z}}_2\right)={\left({\mu }_{ij}\right)}_{\begin{array}{l}1\le i\le \left|E\right|\\ 1\le j\le \left|V\right|\end{array}}$ is given by setting ${\mu }_{ij}={\theta }_{ij}\mathrm{mod}2\mathbb{Z}$.

By Remark 1 the characteristic vector $\left[c\right]$, $c\in \bar{O}\left(G\right)$ might depend on the ordering of c. However, the kernel of $\mathcal{I}\left(G\mathrm{,}R\right)$ is not sensitive to the possible choices of signs. Therefore, we obtain a well defined algebraic notion of cycles as follows.

Lemma 3. Let $G=\left(V\mathrm{,}E\mathrm{,}\text{head}\mathrm{,}\text{tail}\right)$ be a multi-digraph and $O\subseteq {\bar{O}}_{\text{el}}\left(G\right)$ be a set of elementary cycles. Then we denote with

$\left[O\right]=\left\{x\in \mathbb{E}\left(G\right)\mathrm{<mo>\; |\; </mo>}x=\left[c\right]\mathrm{,}c\in O\right\}\mathrm{,}$ (12)

${\left[O\right]}_2=\left\{x\in {\mathbb{E}}_2\left(G\right)\mathrm{<mo>\; |\; </mo>}x={\left[c\right]}_2\mathrm{,}c\in O\right\}$ (13)

the set of all characteristic vectors induced by cycles in O. The free generated cycle modules are given by

$\Lambda \left(G\mathrm{,}\mathbb{Z}\right)\mathrm{<mo>\; :\; </mo>}={\langle \left[\bar{O}\left(G\right)\right]\rangle }_{\mathbb{Z}}={\langle \left[{\bar{O}}_{\text{el}}\left(G\right)\right]\rangle }_{\mathbb{Z}}=\ker \mathcal{I}\left(G\mathrm{,}\mathbb{Z}\right)$

$\Lambda \left(G\mathrm{,}{\mathbb{Z}}_2\right)\mathrm{<mo>\; :\; </mo>}={\langle {\left[\bar{O}\left(G\right)\right]}_2\rangle }_{{\mathbb{Z}}_2}={\langle {\left[{\bar{O}}_{\text{el}}\left(G\right)\right]}_2\rangle }_{{\mathbb{Z}}_2}=\ker \mathcal{I}\left(G\mathrm{,}{\mathbb{Z}}_2\right)\mathrm{,}$

where ${\langle \cdot \rangle }_{\mathbb{Z}}$, ${\langle \cdot \rangle }_{{\mathbb{Z}}_2}$ denotes the span with respect to $\mathbb{Z}\mathrm{,}{\mathbb{Z}}_2$.

Proof. The identities ${\langle \left[\bar{O}\left(G\right)\right]\rangle }_{\mathbb{Z}}={\langle \left[{\bar{O}}_{\text{el}}\left(G\right)\right]\rangle }_{\mathbb{Z}},{\langle {\left[\bar{O}\left(G\right)\right]}_2\rangle }_{{\mathbb{Z}}_2}={\langle {\left[{\bar{O}}_{\text{el}}\left(G\right)\right]}_2\rangle }_{{\mathbb{Z}}_2}$ follow directly by the definition of $\left[\bar{O}\left(G\right)\right]\mathrm{,}{\left[\bar{O}\left(G\right)\right]}_2$. Further, we verify that for any list $\epsilon =\left\{e_1\mathrm{,}\cdots \mathrm{,}{e}_n\right\}\subseteq E$ of connected edges, due to (6), we have

$\pm \mathcal{I}\left(G\mathrm{,}\mathbb{Z}\right)\left[\epsilon \right]=\text{tail}\left(e_1\right)-\text{head}\left(e_n\right)\mathrm{,}$

$\mathcal{I}\left(G\mathrm{,}{\mathbb{Z}}_2\right){\left[\epsilon \right]}_2=\text{tail}\left(e_1\right)+\text{head}\left(e_n\right)\mathrm{mod}2\mathbb{V}\left(G\right)\mathrm{.}$ (14)

Hence,

$\mathcal{I}\left(G\mathrm{,}\mathbb{Z}\right)\left[\epsilon \right]=0\iff \epsilon \in \bar{O}\left(G\right)\mathrm{,}\mathcal{I}\left(G\mathrm{,}{\mathbb{Z}}_2\right){\left[\epsilon \right]}_2=0\iff \epsilon \in \bar{O}\left(G\right)$ (15)

proving the claim.

To characterize the cycle spaces we rephrase Biggs Theorem [14] for connected cycles of simple digraphs matching our setup and notation.

Theorem 4 (Biggs Theorem). Let $G=\left(V\mathrm{,}E\mathrm{,}\text{head}\mathrm{,}\text{tail}\right)$ be a simple digraph then the dimension of the connected cycle spaces are given by

${\dim }_R\Lambda \left(G\mathrm{,}R\right)=\left|E\right|-\left|V\right|+\mathrm{<mo>\; \#\; </mo>}G\mathrm{,}R=\mathbb{Z}\mathrm{,}{\mathbb{Z}}_2\mathrm{,}$ (16)

where #G denotes the number of connected components of G.

Indeed, for simple digraphs the first line of the incidence matrix in (11) is unnecessary and thereby our definition yields the classic notion of $I\left(G\mathrm{,}R\right)$ for any fixed enumeration of $V\mathrm{,}E$. In fact, the proof of Theorem 4 is based on computing the rank of $I\left(G\mathrm{,}R\right)$, which is independent of the chosen enumeration, yielding our reformulation to be genuine. Due to Lemma 3 we obtain the following consequence.

Corollary 1 (Biggs Theorem for connected cycles of multi-digraphs). Let $G=\left(V\mathrm{,}E\mathrm{,}\text{head}\mathrm{,}\text{tail}\right)$ be a multi-digraph. Then the dimension of the connected cycle spaces are given by

${\dim }_R\Lambda \left(G\mathrm{,}R\right)=\left|E\right|-\left|V\right|+\mathrm{<mo>\; \#\; </mo>}G\mathrm{,}R=\mathbb{Z}\mathrm{,}{\mathbb{Z}}_2\mathrm{,}$ (17)

where #G denotes the number of connected components of G.

Proof. Indeed, each loop or multiple edge increases the dimension by 1. More precisely: Every loop $\left[\left\{e\right\}\right]\mathrm{,}{\left[\left\{e\right\}\right]}_2$ or two cycle $\left[\left\{e\mathrm{,}f\right\}\right]\mathrm{,}{\left[\left\{e\mathrm{,}f\right\}\right]}_2$, $e\mathrm{,}f\in E$ is R-linear independent, to all other elements in $\left[\bar{O}\left(G\backslash e\right)\right]\mathrm{,}{\left[\bar{O}\left(G\backslash e\right)\right]}_2$. Thus, by removing e we obtain ${\dim }_R\Lambda \left(G\backslash e\mathrm{,}R\right)={\dim }_R\Lambda \left(G\mathrm{,}R\right)-1$. Recursively applying this procedure ends up with a simple digraph $G^{\prime }=\left(V\mathrm{,}{E}^{\prime }\mathrm{,}\text{<mi> hea </mi> <msup> <mi> d </mi> <mo> ′ </mo> </msup>}\mathrm{,}\text{<mi> tai </mi> <msup> <mi> l </mi> <mo> ′ </mo> </msup>}\right)$ with $\mathrm{<mo>\; \#\; </mo>}{G}^{\prime }=\mathrm{<mo>\; \#\; </mo>}G$. Thus, due to Theorem 4 we compute

$\begin{array}{c}{\dim }_R\Lambda \left(G\mathrm{,}R\right)=\left|E\right|-\left|E^{\prime }\right|+{\dim }_R\Lambda \left(G^{\prime }\mathrm{,}R\right)\\ =\left|E\right|-\left|E^{\prime }\right|+\left|E^{\prime }\right|-\left|V\right|+\mathrm{<mo>\; \#\; </mo>}{G}^{\prime }\\ =\left|E\right|-\left|V\right|+\mathrm{<mo>\; \#\; </mo>}G\mathrm{.}\end{array}$ (18)

How to generalize the characterisation of cycle spaces in the directed case is provided in the next section.

3. Biggs Theorem for Directed Cycles

We prove a generalization, we introduce the concept of contracting edges in a multi-digraph as follows.

Definition 4 (Contracted Graph). Let $G=\left(V\mathrm{,}E\mathrm{,}\text{head}\mathrm{,}\text{tail}\right)$ be a multi-digraph and $e\in E$. Let $v=\text{head}\left(e\right)$, $u=\text{tail}\left(e\right)$. An equivalence relation ${\sim }_{u\mathrm{,}v}$ on V is defined by

$x{\sim }_{u\mathrm{,}v}y\iff x=y\text{or}x\mathrm{,}y\in \left\{u\mathrm{,}v\right\}\mathrm{.}$ (19)

The equivalence class of $x\in V$ is denoted by ${\left[x\right]}_{\sim u\mathrm{,}v}$ and $V\mathrm{<mo>\; /\; </mo>}e\mathrm{<mo>\; :\; </mo>}=V{\mathrm{<mo>\; /\; </mo>}}_{\sim u\mathrm{,}v}$ gives the quotient of V with respect to ${\sim }_{u\mathrm{,}v}$. Further, we define $E\mathrm{<mo>\; /\; </mo>}e\mathrm{<mo>\; :\; </mo>}=E\backslash \left\{e\right\}$ and set

${\text{head}}_{\mathrm{<mo>\; /\; </mo>}e}\left(f\right)={\left[\text{head}\left(f\right)\right]}_{\sim u\mathrm{,}v}\mathrm{,}{\text{tail}}_{\mathrm{<mo>\; /\; </mo>}e}\left(f\right)={\left[\text{tail}\left(f\right)\right]}_{\sim u\mathrm{,}v}\mathrm{,}\forall f\in E\mathrm{<mo>\; /\; </mo>}e\mathrm{.}$ (20)

The multi-digraph $G\mathrm{<mo>\; /\; </mo>}e\mathrm{<mo>\; :\; </mo>}=\left(V\mathrm{<mo>\; /\; </mo>}e\mathrm{,}E\mathrm{<mo>\; /\; </mo>}e\mathrm{,}{\text{head}}_{\mathrm{<mo>\; /\; </mo>}e}\mathrm{,}{\text{tail}}_{\mathrm{<mo>\; /\; </mo>}e}\right)$ is called the contracted graph of G with respect to $e\in E$. If $e\mathrm{,}f\in E$ then we observe that $\left(G\mathrm{<mo>\; /\; </mo>}e\right)\mathrm{<mo>\; /\; </mo>}f\cong \left(G\mathrm{<mo>\; /\; </mo>}f\right)\mathrm{<mo>\; /\; </mo>}e$. Thus, if $G^{\prime }\subseteq G$ is a subgraph then $G\mathrm{<mo>\; /\; </mo>}{G}^{\prime }\mathrm{<mo>\; :\; </mo>}=G\mathrm{<mo>\; /\; </mo>}\mathcal{E}\left(G^{\prime }\right)$ can be defined by contracting $\mathcal{E}\left(G^{\prime }\right)$ in arbitrary order, yielding a well defined notion.

Remark 2. Let $G=\left(V\mathrm{,}E\mathrm{,}\text{head}\mathrm{,}\text{tail}\right)$ be a simple digraph and $e\mathrm{,}f\mathrm{,}h\in E$ such that $e\mathrm{,}f$ are consecutive and $\text{tail}\left(h\right)=\text{tail}\left(e\right)\mathrm{,}\text{head}\left(h\right)=\text{head}\left(f\right)$. Then $G\mathrm{<mo>\; /\; </mo>}e$ becomes a multi-digraph, i.e., h and f become parallel edges in $G\mathrm{<mo>\; /\; </mo>}e$. Furthermore, the contraction of a two cycle $c=\left\{e\mathrm{,}f\right\}$, $\text{tail}\left(e\right)\in \left\{\text{tail}\left(f\right)\mathrm{,}\text{head}\left(f\right)\right\}$, $\text{head}\left(e\right)\in \left\{\text{tail}\left(f\right)\mathrm{,}\text{head}\left(f\right)\right\}$ results in a loop $c\mathrm{<mo>\; /\; </mo>}e\in \bar{O}\left(G\mathrm{<mo>\; /\; </mo>}e\right)$. These phenomena are the reasons why we consider multi-digraphs with loops, rendering the notion of contracted graphs consistent within our framework. Certainly, contraction preserves connectivity, i.e., $\mathrm{<mo>\; \#\; </mo>}G=\mathrm{<mo>\; \#\; </mo>}G\mathrm{<mo>\; /\; </mo>}e$.

Now we have all ingredients to state the first main theorem of this article.

Theorem 5 (Biggs Theorem for directed cycles). Let $G=\left(V\mathrm{,}E\mathrm{,}\text{head}\mathrm{,}\text{tail}\right)$ be a multi-digraph and $\Lambda \left(G\mathrm{,}R\right)={\langle {\bar{O}}_{\text{el}}\left(G\right)\rangle }_R$ its cycle space with respect to $R=\mathbb{Z}\mathrm{,}{\mathbb{Z}}_2$. Then

$\mathcal{G}\left(O_{\text{el}}\left(G\right)\right)=\mathcal{G}\left({\bar{O}}_{\text{el}}\left(G\right)\right)$ if and only if ${\langle O_{\text{el}}\left(G\right)\rangle }_R={\langle {\bar{O}}_{\text{el}}\left(G\right)\rangle }_R$. (21)

Consequently, in case of equivalence, there holds

${\dim }_R{\langle O_{\text{el}}\left(G\right)\rangle }_R=\left|E\right|-\left|V\right|+\mathrm{<mo>\; \#\; </mo>}G={\dim }_R\Lambda \left(G\mathrm{,}R\right)\mathrm{.}$ (22)

Proof. The proof splits into several steps:

Step 1: We show ${\langle O_{\text{el}}\left(G\right)\rangle }_{\mathbb{Z}}={\langle {\bar{O}}_{\text{el}}\left(G\right)\rangle }_{\mathbb{Z}}\Rightarrow \mathcal{G}\left(O_{\text{el}}\left(G\right)\right)=\mathcal{G}\left({\bar{O}}_{\text{el}}\left(G\right)\right)$. Indeed, given $\left[c\right]={\displaystyle {\sum }_{i=1}^n}{x}_i{e}_i\in {\langle {\bar{O}}_{\text{el}}\left(G\right)\rangle }_{\mathbb{Z}}$. Then we can generate $\left[c\right]={\displaystyle {\sum }_{k=1}^m}{\lambda }_k\left[c_k\right]$ by characteristic vectors of directed elementary cycles $c_k\in O_{\text{el}}\left(G\right)$, $k=\mathrm{1,}\cdots \mathrm{,}m$. Thus, every $e_i$ hast to be contained in at least one of them proving $\mathcal{G}\left(O_{\text{el}}\left(G\right)\right)=\mathcal{G}\left({\bar{O}}_{\text{el}}\left(G\right)\right)$.

Step 2: We show $\mathcal{G}\left(O_{\text{el}}\left(G\right)\right)=\mathcal{G}\left({\bar{O}}_{\text{el}}\left(G\right)\right)\Rightarrow {\langle O_{\text{el}}\left(G\right)\rangle }_{\mathbb{Z}}={\langle {\bar{O}}_{\text{el}}\left(G\right)\rangle }_{\mathbb{Z}}$. Indeed, $O_{\text{el}}\left(G\right)\subseteq {\bar{O}}_{\text{el}}\left(G\right)$ implies that by Lemma 3 ${\langle O_{\text{el}}\left(G\right)\rangle }_{\mathbb{Z}}\subseteq {\langle {\bar{O}}_{\text{el}}\left(G\right)\rangle }_{\mathbb{Z}}=\Lambda \left(G\mathrm{,}\mathbb{Z}\right)$ is a free sub-module of $\Lambda \left(G\mathrm{,}\mathbb{Z}\right)$. Thus, it suffices to show (22) in order to prove the converse inclusion. We argue by induction on $\left|V\right|-\mathrm{<mo>\; \#\; </mo>}G$. If $\left|V\right|-\mathrm{<mo>\; \#\; </mo>}G\mathrm{<mo>\; =\; </mo>0}$ then there are only loops. Thus,

${\dim }_{\mathbb{Z}}{\langle O_{\text{el}}\left(G\right)\rangle }_{\mathbb{Z}}=\left|E\right|\mathrm{<mo>\; =\; </mo>}\left|E\right|-\left|V\right|+\mathrm{<mo>\; \#\; </mo>}G$ (23)

and the claim follows. Now assume that $\left|V\right|-\mathrm{<mo>\; \#\; </mo>}G>1$. Let $f\in E$ be not a loop; then we consider the contracted graph $G\mathrm{<mo>\; /\; </mo>}f$. Let $c\in O_{\text{el}}\left(G\right)$ if $f\notin \mathcal{E}\left(c\right)$ and $\mathcal{V}\left(c\right)\cap \mathcal{V}\left(f\right)=\varnothing$ or $\mathcal{V}\left(f\right)\cap \mathcal{V}\left(c\right)=\left\{\text{head}\left(f\right)\right\}$, $\mathcal{V}\left(f\right)\cap \mathcal{V}\left(c\right)=\left\{\text{tail}\left(f\right)\right\}$ then certainly $c\mathrm{<mo>\; /\; </mo>}f\in O_{\text{el}}\left(G\right)$. If $f\in \mathcal{E}\left(c\right)$ then $c\mathrm{<mo>\; /\; </mo>}f$ remains elementary. If $f\in E\backslash \mathcal{E}\left(c\right)$ and $\mathcal{V}\left(f\right)\cap \mathcal{V}\left(c\right)=\mathcal{V}\left(f\right)$ then $c\mathrm{<mo>\; /\; </mo>}f$ consists of two elementary cycles $c_1\mathrm{,}{c}_2\in O_{\text{el}}\left(G\mathrm{<mo>\; /\; </mo>}f\right)$ with one of them being a loop. Thus, $\mathcal{G}\left(O_{\text{el}}\left(G\mathrm{<mo>\; /\; </mo>}f\right)\right)=\mathcal{G}\left({\bar{O}}_{\text{el}}\left(G\mathrm{<mo>\; /\; </mo>}f\right)\right)$. By induction, we therefore compute

$\begin{array}{c}{\dim }_{\mathbb{Z}}{\langle O_{\text{el}}\left(G\mathrm{<mo>\; /\; </mo>}f\right)\rangle }_{\mathbb{Z}}=\left|E\mathrm{<mo>\; /\; </mo>}f\right|-\left|V\mathrm{<mo>\; /\; </mo>}f\right|+\mathrm{<mo>\; \#\; </mo>}G\mathrm{<mo>\; /\; </mo>}f=\left|E\right|-\left|V\right|+\mathrm{<mo>\; \#\; </mo>}G\\ \ge {\dim }_{\mathbb{Z}}{\langle O_{\text{el}}\left(G\right)\rangle }_{\mathbb{Z}}\mathrm{.}\end{array}$ (24)

Step 2a: We show that ${\dim }_{\mathbb{Z}}{\langle O_{\text{el}}\left(G\right)\rangle }_{\mathbb{Z}}\ge {\dim }_{\mathbb{Z}}{\langle O_{\text{el}}\left(G\mathrm{<mo>\; /\; </mo>}f\right)\rangle }_{\mathbb{Z}}$. Let $c\in O_{\text{el}}\left(G\right)$ with $f\in \mathcal{E}\left(c\right)$. By choosing an equivalent cycle $\bar{c}$, $c\sim \bar{c}$ if necessary w.l.o.g. we can assume that c is ordered such that $c=\left(e_1\mathrm{,}\cdots \mathrm{,}{e}_{\left|c\right|-1}\mathrm{,}f\right)\in O_{\text{el}}\left(G\right)$, $e_i\in E$, $1\le i<\left|c\right|$. Conversely, for every cycle $d\in O_{\text{el}}\left(G\mathrm{<mo>\; /\; </mo>}f\right)$ we choose an ordering $d=\left(e_1\mathrm{,}\cdots \mathrm{,}{e}_{\left|c^{\prime }\right|}\right)$ such that either $\tilde{d}=\left(e_1\mathrm{,}\cdots \mathrm{,}{e}_{\left|c^{\prime }\right|}\mathrm{,}f\right)$ or $\tilde{d}=\left(e_1\mathrm{,}\cdots \mathrm{,}{e}_{\left|c^{\prime }\right|}\right)$ becomes a cycle in ${\bar{O}}_{\text{el}}\left(G\right)$. We consider the map

$\tau \mathrm{<mo>\; :\; </mo>}{O}_{\text{el}}\left(G\mathrm{<mo>\; /\; </mo>}f\right)$ ↪ ${\bar{O}}_{\text{el}}\left(G\right)\mathrm{,}\text{with}\tau \left(d\right)\mathrm{<mo>\; :\; </mo>}=\tilde{d}\mathrm{.}$ (25)

Given $h_1\mathrm{,}\cdots \mathrm{,}{h}_l\in O_{\text{el}}\left(G\mathrm{<mo>\; /\; </mo>}f\right)$, $l\in \mathbb{N}$ such that $\left[h_1\right]\mathrm{,}\cdots \mathrm{,}\left[h_l\right]\in \mathbb{E}\left(G\mathrm{<mo>\; /\; </mo>}f\right)$ are a basis of ${\langle O_{\text{el}}\left(G\mathrm{<mo>\; /\; </mo>}f\right)\rangle }_{\mathbb{Z}}$. Then $\tau$ induces a $\mathbb{Z}$ -linear injective lift

${\tau }^{\mathrm{<mo>\; *\; </mo>}}\mathrm{<mo>\; :\; </mo>}{\langle O_{\text{el}}\left(G\mathrm{<mo>\; /\; </mo>}f\right)\rangle }_{\mathbb{Z}}\to {\langle {\bar{O}}_{\text{el}}\left(G\right)\rangle }_{\mathbb{Z}}\mathrm{,}{\tau }^{\mathrm{<mo>\; *\; </mo>}}\left(\left[h_i\right]\right)=\left[\tau \left(h_i\right)\right]=\left[{\tilde{h}}_i\right]\mathrm{,}i=\mathrm{1,}\cdots \mathrm{,}l\mathrm{.}$ (26)

Step 2b: We show that $\text{im}\left({\tau }^{\mathrm{<mo>\; *\; </mo>}}\right)\subseteq {\langle O_{\text{el}}\left(G\right)\rangle }_{\mathbb{Z}}$. Indeed, if $d\in O_{\text{el}}\left(G\mathrm{<mo>\; /\; </mo>}f\right)$ is such that $\left[\tilde{d}\right]$ has no negative entries then $\tilde{d}=\tau \left(d\right)\in O_{\text{el}}\left(G\right)$ and $\left[\tilde{d}\right]={\tau }^{\mathrm{<mo>\; *\; </mo>}}\left(\left[d\right]\right)\in {\langle O_{\text{el}}\left(G\right)\rangle }_{\mathbb{Z}}$. If this is not the case then the entry ${\left[\tilde{d}\right]}_f=-1$ corresponding to f is the only negative entry. Since $\mathcal{G}\left(O_{\text{el}}\left(G\right)\right)=\mathcal{G}\left({\bar{O}}_{\text{el}}\left(G\right)\right)$ there is $b\in O_{\text{el}}\left(G\right)$ with $f\in \mathcal{E}\left(b\right)$.

For any $x\mathrm{,}y\in V$ we denote by $d_{x\mathrm{,}y}$ the directed subpath of $\tilde{d}$ connecting x and y. Further, let $x_1\mathrm{,}\cdots \mathrm{,}{x}_n\in \mathcal{V}\left(\tilde{d}\right)$ be all crossing vertices such that for the edges $e_i\mathrm{,}{f}_i\in \mathcal{E}\left(b\right)$ with $\text{head}\left(e_i\right)=x_i=\text{tail}\left(f_i\right)$ we have $e_i\notin \mathcal{E}\left(\tilde{d}\right)$ and $f_i\in \mathcal{E}\left(\tilde{d}\right)$, $i=1,\cdots ,n$. Analogously, we consider all crossing vertices $y_1\mathrm{,}\cdots \mathrm{,}{y}_n\in \mathcal{V}\left(\tilde{d}\right)$ such that for the edges $h_i\mathrm{,}{g}_i\in \mathcal{E}\left(b\right)$ with $\text{head}\left(h_i\right)=y_i=\text{tail}\left(g_i\right)$ we have $h_i\in \mathcal{E}\left(\tilde{d}\right)$ and $g_i\notin \mathcal{E}\left(\tilde{d}\right)$. Moreover, we assume that $\text{tail}\left(f\right)=x_1\mathrm{,}\text{head}\left(f\right)=y_1$ and that the $x_i\mathrm{,}{y}_i$ are ordered w.r.t the ordering of directed path $d_{x_1\mathrm{,}{y}_1}$. We consider two cases.

Case 1: If $n=1$ then setting $d_0=b$, $d_1=b_{y_1,x_1}\ast d_{x_1,y_1}$ yields $d_{x_1\mathrm{,}{y}_1}=f$, see Figure 2 and thereby

$\left[\tilde{d}\right]+\left[d_0\right]-\left[d_1\right]=0$ (27)

implying $\left[\tilde{d}\right]={\tau }^{\mathrm{<mo>\; *\; </mo>}}\left(\left[d\right]\right)\in {\langle O_{\text{el}}\left(G\right)\rangle }_{\mathbb{Z}}$.

Case 2: If $n>1$ then we construct three cycles $d_0\mathrm{,}{d}_1\mathrm{,}{d}_2\in O_{\text{el}}\left(G\right)$ by

$d_0=b,d_1=d_{x_1,y_n}\ast b_{y_n,x_1},d_2=b_{y_1,y_n}\ast d_{y_n,y_1},$ (28)

see again Figure 3 for an illustration, where $d_0$ is indicated by the black lines. Since $b\mathrm{,}\tilde{d}\in O_{\text{el}}\left(G\right)$ are elementary we have that the connected components of

Figure 2. Sketch of the cycle construction for Case 1.

$b\backslash \tilde{d}=b_{y_n,x_1}{\displaystyle \underset{i=1,\cdots ,n-1}{\coprod }}{b}_{y_i,x_{i+1}},b\cap \tilde{d}={\displaystyle \underset{i=1,\cdots ,n}{\coprod }}{d}_{x_i,y_i}$ (29)

are pairwisely disjoint paths. Moreover, $d_0\mathrm{,}{d}_1\mathrm{,}{d}_2\in O_{\text{el}}\left(G\right)$ are elementary. Therefore, we verify again that

$\left[\tilde{d}\right]+\left[d_0\right]-\left[d_1\right]-\left[d_2\right]=0$ (30)

holds and thereby implies that $\left[\tilde{d}\right]={\tau }^{\mathrm{<mo>\; *\; </mo>}}\left(\left[d\right]\right)\in {\langle O_{\text{el}}\left(G\right)\rangle }_{\mathbb{Z}}$. Hence, $\text{im}\left({\tau }^{\mathrm{<mo>\; *\; </mo>}}\right)\subseteq {\langle O_{\text{el}}\left(G\right)\rangle }_{\mathbb{Z}}$ and we have proven Step 2. Thus, due to Corollary 1 we have proven the theorem for $R=\mathbb{Z}$.

Step 3: For $R={\mathbb{Z}}_2$ the claim follows by using that $\mathcal{G}\left(O_{\text{el}}\left(G\right)\right)=\mathcal{G}\left({\bar{O}}_{\text{el}}\left(G\right)\right)$ is equivalent to ${\langle {\bar{O}}_{\text{el}}\left(G\right)\rangle }_{\mathbb{Z}}={\langle O_{\text{el}}\left(G\right)\rangle }_{\mathbb{Z}}$ as proven above. Then the identity

$\Lambda \left(G\mathrm{,}{\mathbb{Z}}_2\right)\cong {\langle {\bar{O}}_{\text{el}}\left(G\right)\rangle }_{\mathbb{Z}}\mathrm{<mo>\; /\; </mo>2}\mathbb{E}\left(G\right)={\langle O_{\text{el}}\left(G\right)\rangle }_{\mathbb{Z}}\mathrm{<mo>\; /\; </mo>2}\mathbb{E}\left(G\right)\cong {\langle O_{\text{el}}\left(G\right)\rangle }_{{\mathbb{Z}}_2}$ (31)

proves the theorem with respect to ${\mathbb{Z}}_2$ -coefficients.

Remark 3. For simplification, the sketch of Case 2 in Figure 3 assumes that the paths $b_{x_i\mathrm{,}{y}_i}$ are not nested, which might be not true in general. However, this circumstance does not affect (29) nor the fact that $d_0\mathrm{,}{d}_1\mathrm{,}{d}_2$ are elementary, which were all assumptions we used for the argumentation.

An immediate consequence of Theorem 5 is the following.

Corollary 2. Let $G=\left(V\mathrm{,}E\mathrm{,}\text{head}\mathrm{,}\text{tail}\right)$ be a multi-digraph. Then

${\dim }_R{\langle O_{\text{el}}\left(G\right)\rangle }_R={\dim }_R\Lambda \left(\mathcal{G}\left(O_{\text{el}}\left(G\right)\right)\mathrm{,}R\right)\mathrm{,}R=\mathbb{Z}\mathrm{,}{\mathbb{Z}}_2$ (32)

can be determined in $\mathcal{O}\left(\left|E\right|\right)$.

Proof. By Theorem 5 we have ${\langle O_{\text{el}}\left(G\right)\rangle }_R=\Lambda \left(\mathcal{G}\left(O_{\text{el}}\left(G\right)\right)\mathrm{,}R\right)$ and therefore ${\dim }_R{\langle O_{\text{el}}\left(G\right)\rangle }_R={\dim }_R\Lambda \left(\mathcal{G}\left(O_{\text{el}}\left(G\right)\right)\mathrm{,}R\right)$. Now $\mathcal{G}\left(O_{\text{el}}\left(G\right)\right)$ is given by the union of all strongly connected components of G which can be computed in linear time [16] yielding the claim due to (22).

The opportunity of computing the dimension of the directed cycles space ${\langle O_{\text{el}}\left(G\right)\rangle }_R$ efficiently, potentially addresses many challenging problems in graph theory. We use the result to study the structure of G in terms of cellular homology groups.

4. The CW Complex of Elementary Cycles

An excellent introduction to algebraic topology is given by Allen Hatcher [15].

Figure 3. Sketch of the cycle construction for Case 2.

Especially, the notion of CW complexes, geometric realizations and the classic theory of simplicial and cellular homology were presented explicitly therein. The following notions and results take these concepts for granted.

Definition 5 (Coherent Orientation). Let $G=\left(V\mathrm{,}E\mathrm{,}\text{head}\mathrm{,}\text{tail}\right)$ be a multi-digraph and $O\subseteq {\bar{O}}_{\text{el}}\left(G\right)$ be a set of elementary connected cycles. A map $o\mathrm{<mo>\; :\; </mo>}E\to \left\{-\mathrm{1,0,1}\right\}$ is called a coherent orientation w.r.t. O iff

i) $o\left(e\right)=0$ for all $e\in E\backslash \mathcal{E}(\; O\; )$

ii) $\left[c\right]={\displaystyle {\sum }_{i=1}^n}{x}_i{e}_i=\pm {\displaystyle {\sum }_{i=1}^n}o\left(e_i\right)e_i$ for all characteristic vectors $\left[c\right]$ with $c\in O$.

Lemma 6. Let $G=\left(V\mathrm{,}E\mathrm{,}\text{head}\mathrm{,}\text{tail}\right)$ be a multi-digraph and $O\subseteq {\bar{O}}_{\text{el}}\left(G\right)$ be a set of elementary connected cycles. Then there exists a coherent orientation $o\mathrm{<mo>\; :\; </mo>}E\to \left\{-\mathrm{1,0,1}\right\}$.

Proof. We argue by induction on $\left|O\right|$. If $\left|O\right|=1$ then we choose an ordering $c=\left(e_1\mathrm{,}\cdots \mathrm{,}{e}_n\right)\in O$ and thereby a representative of all equivalent cycles in O. Thus, setting $o\left(e_i\right)=x_i$ with $\left[c\right]={\displaystyle \sum }{x}_i{e}_i$ defines a coherent orientation. Now assume that $\left|O\right|>1$. Let $c=\left(e_1\mathrm{,}\cdots \mathrm{,}{e}_n\right)\in O$ and $O^{\prime }⊊O$ be the set of all cycles being not equivalent to c. We consider $G^{\prime }=\mathcal{G}\left(O^{\prime }\right)$ and a splitting $G^{\prime }=G_1\cup \cdots \cup G_K$ into elementary connected components. That is

${\displaystyle \underset{i=1}{\overset{K}{\cup }}}O\cap {\bar{O}}_{\text{el}}\left(G_i\right)=O^{\prime }\text{and}{O}^{\prime }\cap {\bar{O}}_{\text{el}}\left(G_i\right)\cap {\bar{O}}_{\text{el}}\left(G_j\right)=\varnothing \mathrm{,}\forall 1\le i<j\le K\mathrm{.}$ (33)

By induction there is a coherent orientation $o^{\prime }$ w.r.t. $O^{\prime }$. Let $\left[c\right]={\displaystyle {\sum }_{i\mathrm{<mo>\; =\; </mo>1}}^n}{x}_i{e}_i$ be the characteristic vector of c. Assume there are $1\le k\mathrm{,}l\le n$ with $o^{\prime }\left(e_k\right)=x_k$ and $o^{\prime }\left(e_l\right)=-x_l$. Then $e_k\mathrm{,}{e}_l$ belong to different components, i.e., $e_k\in \mathcal{E}\left(G_i\right)$, $e_l\in \mathcal{E}\left(G_j\right)$, $i\ne j$. Observe, that we can change $o^{\prime }$ to $-o^{\prime }$ on every component $G_i$ by keeping the requirements of a coherent orientation preserved. Thus, we can change $o^{\prime }$ to $\tilde{o}$ such that $\tilde{o}\left(e_i\right)=x_i$ for all $e_i\in \mathcal{E}\left(c\right)\cap \mathcal{E}\left(O^{\prime }\right)$. Hence, setting $o=\tilde{o}$ on $\mathcal{E}\left(O^{\prime }\right)$ and $o\left(e_i\right)=x_i$ for all $e_i\notin \mathcal{E}\left(O^{\prime }\right)$ yields a coherent orientation.

Definition 6 (Elementary CW Complex). Let $G=\left(V\mathrm{,}E\mathrm{,}\text{head}\mathrm{,}\text{tail}\right)$ be a multi-digraph and $X_1\left(G\right)$ be its geometric realization. Further, let $O\subseteq {\bar{O}}_{\text{el}}\left(G\right)$ be a set of elementary connected cycles. The geometric realization $X\left(G\mathrm{,}O\right)$ given by attaching 2-cells to $X_1\left(G\right)$ accordingly to O is called the elementary CW complex of G w.r.t. O. Further, ${\bar{X}}_0\mathrm{,}{\bar{X}}_1\mathrm{,}{\bar{X}}_2$ shall denote the set of $\mathrm{0,1,2}$ -cells of $X\left(G\mathrm{,}O\right)$, and

$L_0\mathrm{<mo>\; :\; </mo>}{\bar{X}}_0\to V\mathrm{,}{L}_1\mathrm{<mo>\; :\; </mo>}{\bar{X}}_1\to E\mathrm{,}{L}_2\mathrm{<mo>\; :\; </mo>}{\bar{X}}_2\to O$ (34)

the maps yielding the identification of $\mathrm{0,1,2}$ -cells with vertices, edges and cycles, respectively.

Indeed, for the complexes $X\left(G\mathrm{,}{O}_{\text{el}}\left(G\right)\right)$, $X\left(G\mathrm{,}{\bar{O}}_{\text{el}}\left(G\right)\right)$ the cellular homology can be derived by considering the following chain complexes.

Definition 7 (Elementary Chain Complex). Let G be a multi-digraph, $O\subseteq {\bar{O}}_{\text{el}}\left(G\right)$, be a set of elementary connected cycles, $R=\mathbb{Z}\mathrm{,}{\mathbb{Z}}_2$ and $o\mathrm{<mo>\; :\; </mo>}E\to \left\{-\mathrm{1,0,1}\right\}$ be a coherent orientation w.r.t. O. Let $X\left(G\mathrm{,}O\right)$ be the associated CW complex. We consider the free generated R-modules

$C_2=\underset{{\sigma }^2\in {\bar{X}}_2\left(G\mathrm{,}O\right)}{{\displaystyle \oplus }}{\sigma }^{2}R\mathrm{,}{C}_1=\underset{{\sigma }^1\in {\bar{X}}_1\left(G\right)}{{\displaystyle \oplus }}{\sigma }^{1}R\mathrm{,}{C}_0=\underset{{\sigma }^0\in {\bar{X}}_0\left(G\right)}{{\displaystyle \oplus }}{\sigma }^{0}R\mathrm{.}$ (35)

For $R=\mathbb{Z}$, we define the boundary operators ${\partial }_k\mathrm{<mo>\; :\; </mo>}{C}_k\to C_{k-1}$, $k=1,2$ on the generators by ${\partial }_2\left({\sigma }^2\right)={\displaystyle {\sum }_{{\sigma }^1\in {\bar{X}}_1\left(G\right)}}m\left({\sigma }^2\mathrm{,}{\sigma }^1\right){\sigma }^1$,

$m\left({\sigma }^2\mathrm{,}{\sigma }^1\right)=\{\begin{array}{ll}o\left(L_1\left({\sigma }^1\right)\right)\mathrm{,}\hfill & \text{if}{L}_1\left({\sigma }^1\right)\subseteq \mathcal{E}\left(L_2\left({\sigma }^2\right)\right)\hfill \\ 0\mathrm{,}\hfill & \text{else}\hfill \end{array}$ (36)

and ${\partial }_1\left({\sigma }^1\right)={\displaystyle {\sum }_{{\sigma }^0\in X_0}}n\left({\sigma }^1,{\sigma }^0\right){\sigma }^0$,

$n\left({\sigma }^1\mathrm{,}{\sigma }^0\right)=\{\begin{array}{ll}1\mathrm{,}\hfill & \text{if}\text{head}\left(L_1\left({\sigma }^1\right)\right)=L_0\left({\sigma }^0\right)\hfill \\ -1\mathrm{,}\hfill & \text{if}\text{tail}\left(L_1\left({\sigma }^1\right)\right)=L_0\left({\sigma }^0\right)\hfill \\ 0\mathrm{,}\hfill & \text{else}\hfill \end{array}$ (37)

For $R={\mathbb{Z}}_2$ we consider $m\left({\sigma }^2\mathrm{,}{\sigma }^1\right)\mathrm{mod}2\mathbb{Z}$ and $n\left({\sigma }^1,{\sigma }^0\right)\mathrm{mod}2\mathbb{Z}$, respectively. We enforce ${\partial }_k$ to be R-linear by setting $m\left(\lambda {\sigma }^2+\mu {\bar{\sigma }}^2\mathrm{,}{\sigma }^1\right)\mathrm{<mo>\; :\; </mo>}=\lambda m\left({\sigma }^2\mathrm{,}{\sigma }^0\right)+\mu m\left({\bar{\sigma }}^2\mathrm{,}{\sigma }^0\right)$, $n\left(\lambda {\sigma }^1+\mu {\bar{\sigma }}^1\mathrm{,}{\sigma }^0\right)\mathrm{<mo>\; :\; </mo>}=\lambda m\left({\sigma }^1\mathrm{,}{\sigma }^0\right)+\mu n\left({\bar{\sigma }}^1\mathrm{,}{\sigma }^0\right)$ for all ${\sigma }^2\mathrm{,}{\bar{\sigma }}^2\in {\bar{X}}_2\left(G\mathrm{,}O\right)$, ${\sigma }^1\mathrm{,}{\bar{\sigma }}^1\in {\bar{X}}_1\left(G\right)$, ${\sigma }^0\in {\bar{X}}_0\left(G\right)$, $\lambda \mathrm{,}\mu \in R$. Finally, we set $C_3,C_{-1}=0$ and ${\partial }_k=0$ for $k\in \left\{\mathrm{0,3}\right\}$.

Remark 1 asserts why even in case of $\mathbb{Z}$ -coefficients the maps ${\partial }_k$ yield well defined boundary operators. More precisely:

Theorem 7. Let $G=\left(V\mathrm{,}E\mathrm{,}\text{head}\mathrm{,}\text{tail}\right)$ be a multi-digraph, $O\subseteq {\bar{O}}_{\text{el}}\left(G\right)$ be a set of connected elementary cycles and $o\mathrm{<mo>\; :\; </mo>}E\to \left\{-\mathrm{1,0,1}\right\}$ be a coherent orientation w.r.t. O. Let $X\left(G\mathrm{,}O\right)$ be the elementary CW complex, $R=\mathbb{Z}\mathrm{,}{\mathbb{Z}}_2$ and $\left(C_k\mathrm{,}{\partial }_k\right)$ be given due to Definition 7.

i) The pairs $\left(C_k\mathrm{,}{\partial }_k\right)$ define a finite chain complex, i.e., ${\partial }_{k-1}\circ {\partial }_k=0$ for all $k=0,1,2,3$.

ii) The cellular homology groups $H_k\left(X\left(G\mathrm{,}O\right)\mathrm{,}R\right)$ are free R-modules $H_k\left(X\left(G\mathrm{,}O\right)\mathrm{,}R\right)\mathrm{<mo>\; :\; </mo>}=\ker \left({\partial }_k\right)\mathrm{<mo>\; /\; </mo>}\text{im}\left({\partial }_{k+1}\right)$, $k=0,1,2$

$H_2\left(X\left(G\mathrm{,}O\right)\mathrm{,}R\right)\cong R^{b_2\left(G\mathrm{,}O\mathrm{,}R\right)}\mathrm{,}$ (38)

$H_1\left(X\left(G\mathrm{,}O\right)\mathrm{,}R\right)\cong R^{b_1\left(G\mathrm{,}O\mathrm{,}R\right)}\mathrm{,}$ (39)

$H_0\left(X\left(G\mathrm{,}O\right)\mathrm{,}R\right)\cong R^{b_0\left(G\mathrm{,}O\mathrm{,}R\right)}\mathrm{.}$ (40)

iii) The Betti numbers are given by

$b_2\left(G\mathrm{,}O\mathrm{,}R\right)=\left|O\right|-{\dim }_R{\langle O\rangle }_R$ (41)

$b_1\left(G\mathrm{,}O\mathrm{,}R\right)=\left|E\right|-\left|V\right|+\mathrm{<mo>\; \#\; </mo>}G-{\dim }_R{\langle O\rangle }_R$ (42)

$b_0\left(G\mathrm{,}O\mathrm{,}R\right)=\mathrm{<mo>\; \#\; </mo>}G\mathrm{.}$ (43)

Proof. By considering the sequence

$0\stackrel{{\partial }_3}{\to }{C}_2\stackrel{{\partial }_2}{\to }{C}_1\stackrel{{\partial }_1}{\to }{C}_0\stackrel{{\partial }_0}{\to }0$ (44)

the identities ${\partial }_{k-1}\circ {\partial }_k=0$, follow for $k\in \left\{\mathrm{1,3}\right\}$. For $\gamma ={\displaystyle {\sum }_{k=1}^n}{\lambda }_k{\sigma }_k^1\in C_1$ and $\delta ={\displaystyle {\sum }_{k=1}^m}{\alpha }_k{\sigma }_k^0\in C_0$ we consider the induced characteristic vectors

$\left[\gamma \right]={\displaystyle \underset{k=1}{\overset{n}{\sum }}}{\lambda }_k\left[L_1\left({\sigma }_k^1\right)\right],{\left[\gamma \right]}_2={\displaystyle \underset{k=1}{\overset{n}{\sum }}}{\mu }_k{\left[L_1\left({\sigma }_k^1\right)\right]}_2,{\mu }_k={\lambda }_k\mathrm{mod}2.$ (45)

$\left[\delta \right]={\displaystyle \underset{k=1}{\overset{m}{\sum }}}{\alpha }_k\left[L_0\left({\sigma }_k^0\right)\right],{\left[\delta \right]}_2={\displaystyle \underset{k=1}{\overset{m}{\sum }}}{\beta }_k{\left[L_0\left({\sigma }_k^0\right)\right]}_2,{\beta }_k={\alpha }_k\mathrm{mod}2.$ (46)

Then we observe that $\left[{\partial }_1\gamma \right]=\mathcal{I}\left(G\mathrm{,}\mathbb{Z}\right)\left[\gamma \right]$, ${\left[{\partial }_1\gamma \right]}_2=\mathcal{I}\left(G\mathrm{,}{\mathbb{Z}}_2\right){\left[\gamma \right]}_2$, where $\mathcal{I}\left(G\mathrm{,}R\right)$ denotes the incidence operator of G. Thus, ${\partial }_1\gamma =0$ if and only if $\gamma$ corresponds to a cycle, i.e., $\left[\gamma \right]\in \Lambda \left(G\mathrm{,}\mathbb{Z}\right)$, ${\left[\gamma \right]}_2\in \Lambda \left(G\mathrm{,}{\mathbb{Z}}_2\right)$. By definition of ${\partial }_2$ and Lemma 3, this yields $\text{im}\left({\partial }_2\right)\subseteq \ker \left({\partial }_1\right)\cong \ker \mathcal{I}\left(G\mathrm{,}R\right)$ and consequently ${\partial }_1\circ {\partial }_2=0$, showing (i). Furthermore, we realize that, $\text{im}\left({\partial }_3\right)=0$ and $\text{im}\left({\partial }_2\right)\cong {\langle O\rangle }_R$. Thus, $\text{im}\left({\partial }_2\right)$ is free generated by O, implying that $\text{im}\left({\partial }_2\right)\cong R^{{\dim }_R{\langle O\rangle }_R}$. By using the dimension formula we realize that the quotient $H_2\left(X\left(G\mathrm{,}O\right)\mathrm{,}R\right)=C_2\mathrm{<mo>\; /\; </mo>}\text{im}\left({\partial }_3\right)$ is a free R-module of dimension

$b_2\left(G\mathrm{,}O\mathrm{,}R\right)=\left|O\right|-{\dim }_R{\langle O\rangle }_R\mathrm{.}$ (47)

Likewise, $\ker \left({\partial }_1\right)\cong \ker \mathcal{I}\left(G\mathrm{,}R\right)$ implies that $H_1\left(X\left(G\mathrm{,}O\right)\mathrm{,}R\right)\cong \Lambda \left(G\mathrm{,}R\right)\mathrm{<mo>\; /\; </mo>}{\langle O\rangle }_R$. Since ${\langle O\rangle }_R$ and $\Lambda \left(G\mathrm{,}R\right)$ are free R-modules, there are isomorphisms $\rho \mathrm{<mo>\; :\; </mo>}{\langle O\rangle }_R\to R^{{\dim }_R{\langle O\rangle }_R}$, $\tau \mathrm{<mo>\; :\; </mo>}\Lambda \left(G\mathrm{,}R\right)\to R^{\left|E\right|-\left|V\right|+\mathrm{<mo>\; \#\; </mo>}G}$. Let $i\mathrm{<mo>\; :\; </mo>}{R}^{{\dim }_R{\langle O\rangle }_R}$ ↪ $R^{\left|E\right|-\left|V\right|+\mathrm{<mo>\; \#\; </mo>}G}$ be the natural embedding and $B_O$ be a basis of ${\langle O\rangle }_R$ then ${B^{\prime }}_O=i\circ \rho \left(B_O\right)$ can be extended to a basis $B_R$ of $R^{\mathrm{<mo>\; |\; </mo>}E\mathrm{<mo>\; |\; </mo>}-\mathrm{<mo>\; |\; </mo>}V\mathrm{<mo>\; |\; </mo>}+\mathrm{<mo>\; \#\; </mo>}G}$ and ${\tau }^{-1}\left(B_R\right)$ yields a basis of $\Lambda \left(G\mathrm{,}R\right)$ containing $B_O$ as a sub-basis of ${\langle O\rangle }_R$. Thus,

$R^{\left|E\right|-\left|V\right|+\mathrm{<mo>\; \#\; </mo>}G}\mathrm{<mo>\; /\; </mo>}{R}^{{\dim }_R{\langle O\rangle }_R}=\tau \left(\Lambda \left(G\mathrm{,}R\right)\right)\mathrm{<mo>\; /\; </mo>}\left(i\circ \rho \left({\langle O\rangle }_R\right)\right)\cong \Lambda \left(G\mathrm{,}R\right)\mathrm{<mo>\; /\; </mo>}{\langle O\rangle }_R\mathrm{,}$

showing that the 1-st homology $H_1\left(X\left(G\mathrm{,}O\right)\mathrm{,}R\right)$ is a free R-module of dimension

$b_1\left(G\mathrm{,}O\mathrm{,}R\right)={\dim }_R\left(\Lambda \left(G\mathrm{,}R\right)\mathrm{<mo>\; /\; </mo>}{\langle O\rangle }_R\right)=\left|E\right|-\left|V\right|+\mathrm{<mo>\; \#\; </mo>}G-{\dim }_R{\langle O\rangle }_R\mathrm{.}$ (48)

Since $C_1$ and $\ker \left({\partial }_1\right)$ are free R-modules we analogously observe that there is a sub-basis of $\ker \left({\partial }_0\right)$ generating $\text{im}\left({\partial }_1\right)$. Hence, $H_0\left(X\left(G\mathrm{,}O\right)\mathrm{,}R\right)$ is a free R-module of dimension

$\begin{array}{c}{b}_0\left(G\mathrm{,}O\mathrm{,}R\right)=\left|V\right|-{\dim }_R\text{im}\left({\partial }_1\right)=\left|V\right|-\left(\left|E\right|-{\dim }_R\ker \left({\partial }_1\right)\right)\\ =\left|V\right|-\left(\left|E\right|-{\dim }_R\Lambda \left(G\mathrm{,}R\right)\right)=\mathrm{<mo>\; \#\; </mo>}G\mathrm{,}\end{array}$ (49)

which proves (iii).

Remark 4. Note that the Betti numbers do not depend on the choice of the coherent orientation o. Even though, Lemma 6 provides the existence of a coherent orientation o an explicit construction of o, which might be computational expensive, is not necessary to compute the $b_k\left(G\mathrm{,}O\mathrm{,}\mathbb{Z}\right)$, $k=0,1,2$.

Remark 5. The singular homology $H_n^{\text{sing}}\left(X\right)$ of any CW complex X is isomorphic to its cellular homology [15] (Theorem 2.35). Thus, Theorem 7 provides a path for computing the singular homology of the elementary CW complexes $X\left(G\mathrm{,}O\right)$. Further, we obtain the following consequence that yields main Theorem 2.

Corollary 3. Let the assumptions of Theorem 7 be fulfilled and denote with $b_k$ the R-rank of the cellular homology group $H_k\left(X\left(G\mathrm{,}O\right)\right)$, $k=0,1,2$.

i) $b_0\left(G\mathrm{,}{O}_{\text{el}}\left(G\right)\mathrm{,}R\right)=b_0\left(G\mathrm{,}{\bar{O}}_{\text{el}}\left(G\right)\mathrm{,}R\right)=\mathrm{<mo>\; \#\; </mo>}G$ can be computed in $\mathcal{O}\left({\left|V\right|}^2+\left|V\right|\left|E\right|\right)$.

ii) $b_1\left(G\mathrm{,}{\bar{O}}_{\text{el}}\left(G\right)\mathrm{,}R\right)=0$ and $b_1\left(G\mathrm{,}{O}_{\text{el}}\left(G\right)\mathrm{,}R\right)$ can be computed in $\mathcal{O}\left({\left|V\right|}^2+\left|V\right|\left|E\right|\right)$.

iii) Computing $b_2\left(G\mathrm{,}{O}_{\text{el}}\left(G\right)\mathrm{,}R\right)$, $b_2\left(G\mathrm{,}{\bar{O}}_{\text{el}}\left(G\right)\mathrm{,}R\right)$ is #P-hard (sharp P-hard).

Proof. The number of connected components of any multi-graph can be determined by breadth-first search within $\mathcal{O}\left({\left|V\right|}^2+\left|V\right|\left|E\right|\right)$ [18], yielding i) due to Theorem 7. To show ii), recall that by Lemma 3, we have that ${\langle {\bar{O}}_{\text{el}}\left(G\right)\rangle }_R=\Lambda \left(G\mathrm{,}R\right)$ yielding $b_1\left(G\mathrm{,}{\bar{O}}_{\text{el}}\left(G\right)\mathrm{,}R\right)=0$. Due to Corollary 2, computing ${\dim }_R{\langle O_{\text{el}}\left(G\right)\rangle }_R$ can be done in $\mathcal{O}\left(\left|E\right|\right)$. Thus, by Theorem 7, the bottleneck for computing $b_1\left(G\mathrm{,}O\mathrm{,}R\right)$ is again given by determing #G yielding ii). Now iii) is a consequence of Theorem 7 and the fact that, by reduction to the Hamiltonian cycle problem, counting the number of all directed (connected) elementary cycles of a digraph is #P-hard [12].

We recall that two multi-digraphs $G_1=\left(V_1\mathrm{,}{E}_1\right)$ and $G_2=\left(V_2\mathrm{,}{E}_2\right)$ are called homeomorphic if there are sets of directed paths $P_1\mathrm{,}{P}_2$ such that $\mathrm{deg}\left(u\right)=2$ for any inner vertex $u\in \mathcal{V}\left(p\right)$ of $p\in P_1$ or $p\in P_2$, respectively, and the graphs $G_1\mathrm{<mo>\; /\; </mo>}{P}_1\cong G_2\mathrm{<mo>\; /\; </mo>}{P}_2$ given by contracting $P_1\mathrm{,}{P}_2$ are isomorphic.

Corollary 4. Let $G_1$ and $G_2$ be two homeomorphic multi-digraphs. We denote with $O_i=O_{\text{el}}\left(G_i\right)$, ${\bar{O}}_i={\bar{O}}_{\text{el}}\left(G_i\right)$, consider the elementary CW complexes $X\left(G_i\mathrm{,}{O}_i\right)$, $X\left(G_i\mathrm{,}{\bar{O}}_i\right)$, $i=1,2$ and $R=\mathbb{Z}\mathrm{,}{\mathbb{Z}}_2$. Then

$H_k\left(X\left(G_1\mathrm{,}{O}_1\right)\mathrm{,}R\right)\cong H_k\left(X\left(G_2\mathrm{,}{O}_2\right)\mathrm{,}R\right)\mathrm{,}$ (50)

$H_k\left(X\left(G_1\mathrm{,}{\bar{O}}_1\mathrm{,}R\right)\right)\cong H_k\left(X\left(G_2\mathrm{,}{\bar{O}}_2\mathrm{,}R\right)\right)\mathrm{,}$ (51)

where $k=0,1,2$.

Proof. As one can readily verify, neither the number of cycles $\left|O_{\text{el}}\left(G_i\right)\right|$, $\left|{\bar{O}}_{\text{el}}\left(G_i\right)\right|$ nor the dimension ${\dim }_R{\langle O_{\text{el}}\left(G_i\right)\rangle }_R$, ${\langle {\bar{O}}_{\text{el}}\left(G_i\right)\rangle }_R$ nor the number of connected components of $G_i$ change under the contraction of the paths $P_i$, $i=1,2$ yielding the claim due to Theorem 7.

Due to Corollary 3 (3) counting $\left|O_{\text{el}}\left(G\right)\right|\mathrm{,}\left|{\bar{O}}_{\text{el}}\left(G\right)\right|$ is #P-hard. Though there are efficient algorithms [19] counting the number of cycles approximately, we, here, suggest to consider certain sub-fillings $O\subseteq O_{\text{el}}\left(G\right)\mathrm{,}{\bar{O}}_{\text{el}}\left(G\right)$ to yield an suitable setup.

5. Representation Invariant Sub-Fillings

In this section we discuss several possibilities of filling the graph G by choosing $O⊊{\bar{O}}_{\text{el}}\left(G\right)$, such that the cellular homology of the resulting CW complexes $X\left(G\mathrm{,}O\right)$ can be computed efficiently and the filling is invariant under automorphisms, i.e., is independent of the chosen representation of G. The list below is by no means complete and just provides some suggestions.

5.1. Fillings Induced by Cycle Bases

If the cycles $O\subseteq {\bar{O}}_{\text{el}}\left(G\right)$ are R-linear independent then due to Theorem 7 for the CW complex $X\left(G\mathrm{,}O\right)$ the Betti numbers are given by $b_2\left(G,O,R\right)=0$, $b_1\left(G\mathrm{,}O\mathrm{,}R\right)=\left|E\right|-\left|V\right|+\mathrm{<mo>\; \#\; </mo>}G-\left|O\right|$ and $b_0\left(G\mathrm{,}O\mathrm{,}R\right)=\mathrm{<mo>\; \#\; </mo>}G$. Thus, $b_1$ is given by the co-dimension of ${\langle O\rangle }_R$ in $\Lambda \left(G\mathrm{,}R\right)$. Thereby, fillings by R-linear independent cycles or basis yield only trivial topological information.

5.2. Fillings Induced by Shortest Cycles

Let $G=\left(V\mathrm{,}E\mathrm{,}\text{head}\mathrm{,}\text{tail}\right)$ be a multi-digraph. We consider the set of all shortest cycles

$\min \left(G\right)=\left\{c\in {\bar{O}}_{\text{el}}\left(G\right)\mathrm{<mo>\; |\; </mo>}\left|c\right|\le \left|c^{\prime }\right|\forall c^{\prime }\in {\bar{O}}_{\text{el}}\left(G\right)\right\}\mathrm{.}$ (52)

Further, ${\stackrel{\leftarrow }{N}}_E\left(v\right)\mathrm{<mo>\; :\; </mo>}=\left\{e\in E\mathrm{<mo>\; |\; </mo>}\text{head}\left(e\right)=v\right\}$, ${\stackrel{\to }{N}}_E\left(v\right)\mathrm{<mo>\; :\; </mo>}=\left\{e\in E\mathrm{<mo>\; |\; </mo>}\text{tail}\left(e\right)=v\right\}$, $N_E\left(v\right)={\stackrel{\leftarrow }{N}}_E\left(v\right)\cup {\stackrel{\to }{N}}_E\left(v\right)$ denote the set of all incoming or outgoing edges of $v\in V$, and their unions.

Lemma 8. Let $G=\left(V\mathrm{,}E\right)$ be a multi-digraph and $\Delta$ its maximum degree.

i) $\left|O_{\min }\right|<\Delta \left|E\right|$.

ii) $O_{\min }$ can be determined in $\mathcal{O}\left(\Delta {\left|E\right|}^2\right)$.

Proof. Note that the all-shortest path problem, which is to find a shortest connected path between all pairs of vertices $u\mathrm{,}v\in V$ is very well studied. In the case of integer edge weights, as we consider here, for instance the algorithms of [20] [21], solve the problem in much less then $\mathcal{O}\left({\left|E\right|}^2\right)$. We consider all edges $E_{\min }\subseteq E$ with shortest path $p_e$ of minimum length $l_{\min }$ such that $p_e\cup \left\{e\right\}$ becomes a shortest cycle $c_{e\mathrm{,}{p}_e}$. For any outgoing edge $f\in {\stackrel{\to }{N}}_E\left(\text{tail}\left(e\right)\right)$ we denote with $N_f={\stackrel{\to }{N}}_E\left(\text{tail}\left(e\right)\right)\backslash f$ and with $c_{e\mathrm{,}f\mathrm{,}{p}_e}$ the possibly empty shortest cycle w.r.t. $G\backslash N_f$. Then we observe that

$O_{\min }={\displaystyle \underset{e\in E_{\min }\mathrm{,}f\in N_E\left(\text{tail}\left(e\right)\right)}{\cup }}\left\{c_{e\mathrm{,}f\mathrm{,}{p}_e}\right\}\mathrm{.}$ (53)

Thus, i) follows. Further, due to Edsger W. Dijkstra’s famous shortest path algorithm [22] each cycle $c_{e\mathrm{,}f\mathrm{,}{p}_e}$ can be computed in $\mathcal{O}\left(\left|E\right|\right)$ yielding ii).

Certainly, $O_{\min }\left(G\right)\cong O_{\min }\left(G^{\prime }\right)$ for all isomorphic graphs $G\cong G^{\prime }$. Further, the associated Betti numbers $b_k\left(G\mathrm{,}{O}_{\min }\left(G\right)\mathrm{,}R\right)$, $k=0,1,2$, $R=\mathbb{Z}\mathrm{,}{\mathbb{Z}}_2$ of $X\left(G\mathrm{,}{O}_{\min }\left(G\right)\right)$ can be computed efficiently due to Lemma 8 and Theorem 7. Indeed the bottleneck is given by computing ${\dim }_R{\langle O_{\text{min}}\left(G\right)\rangle }_R$, which requires at most $\mathcal{O}\left({\left|E\right|}^3\right)$ by applying Gauss elimination or can be done even faster [23].

Recursively applying this procedure to the contraction $G\mathrm{<mo>\; /\; </mo>}\mathcal{G}\left(O_{\min }\right)$ provides an array of Betti numbers $b_k^n$, $k=0,1,2,3$, $n=\mathrm{1,}\cdots \mathrm{,}N\in \mathbb{N}$ that decodes the structure of G independently of the chosen representation. We expect that this efficiently provided information is quite informative for structural analysis. That is: multi-digraphs $G\mathrm{,}\bar{G}$ with $b_k^n={\bar{b}}_k^n$ for all $k=0,1,2;n=1,\cdots ,N$ are similar and $G\mathrm{,}\bar{G}$ are not isomorphic whenever $b_k^n\mathrm{,}{\bar{b}}_k^n$ differ for some $k=0,1,2;n=1,\cdots ,N$.

5.3. Fillings Induced by Cliques

Let $K_n=\left(V_n\mathrm{,}{E}_n\right)$, $n\in \mathbb{N}$, denote the complete undirected graph of n vertices, $C_n={\bar{O}}_{\text{el}}\left(K_n\right)$. Then the number of cycles $\left|C_n\right|$, up to cyclic reordering, is given by all subsets of vertices larger than 3, i.e.,

$\left|V_n\right|=n,\left|E_n\right|=\left(\begin{array}{c}n\\ 2\end{array}\right),\left|C_n\right|={\displaystyle \underset{i=3}{\overset{n}{\sum }}}\left(\begin{array}{c}n\\ i\end{array}\right)=2^n-n^2,$ (54)

which can be computed in $\mathcal{O}\left(n\right)$ [24]. Since ${\langle C_n\rangle }_R=\Lambda \left(K_n\mathrm{,}R\right)$, computing the Betti numbers of $X\left(K_n\mathrm{,}{C}_n\right)$ can be done in $\mathcal{O}\left(n\right)$. Let ${\mathcal{K}}_n\left(G\right)$ be the set of all cliques $K_n\subseteq G$ of size $n\in \mathbb{N}$. Let $\alpha \subseteq \left\{\mathrm{3,}\cdots \mathrm{,}N\right\}$, $N\in \mathbb{N}$ with $3\in \alpha$. Then we consider a set of cycles $O_{\alpha }\subseteq {\bar{O}}_{\text{el}}\left(G\right)$ such that $c\in {\bar{O}}_{\text{el}}\left(K_k\right)$ and $K_k\in {\mathcal{K}}_k\left(G\right)$, $k\in \alpha$. The geometric realization $X\left(G\mathrm{,}{O}_{\alpha }\right)$ is a canonical filling in the following sense:

The number of cycles $\left|O_{\alpha }\right|$ can be computed efficiently due to (54). On the other hand $O_{\alpha }$ contains all triangles of $G_{\alpha }\mathrm{<mo>\; :\; </mo>}=\mathcal{G}\left(O_{\alpha }\right)$, which generate $\Lambda \left(G_{\alpha }\mathrm{,}R\right)$, $R=\mathbb{Z}\mathrm{,}{Z}_2$. Thus, ${\dim }_R{\langle O_{\alpha }\rangle }_R={\dim }_R\Lambda \left(G_{\alpha }\mathrm{,}R\right)$. Hence, due to Theorem 7 the associated Betti numbers can be computed efficiently once the cliques ${\mathcal{K}}_k\left(G\right)\mathrm{,}k\in \alpha$ have been determined.

Note that the general clique problem, i.e., finding a clique of given size $n\in \mathbb{N}$ in a graph G, belongs to the list of classic NP-complete problems [25]. However, if the size n is fixed, finding cliques can be done efficiently in $\mathcal{O}\left({\left|V\right|}^n{n}^2\right)$. Even better performs the Bron-Kerbosch algorithm, which lists all maximal cliques [26]. Many other contributions in regard of clique detecting algorithms were made, allowing us to find a non-trivial filling as described above efficiently. Consequently, the homology groups $H_k\left(X\left(G\mathrm{,}O\right)\mathrm{,}R\right)$ yield a method of decoding how the cliques are glued with each other.

6. Applications

We expect the concept of studying a graph G by computing its cellular homology groups with respect to specified fillings $O\subseteq {\bar{O}}_{\text{el}}\left(G\right)$ to open up many possible applications. A short, non-exclusive list of ideas is presented below.

6.1. Graph Embeddings

We strengthen the classic notion of cellular graph embeddings as follows.

Figure 4. Embeddings of $K_{\mathrm{3,3}}$ into $ℝ{\mathbb{P}}^2$ (left) and ${\mathbb{T}}^2$ (right).

Definition 8 (Elementary embedding). Let G be a simple undirected graph, $X_1\left(G\right)$ its 1-dimensional geometric realization, and S a compact, connected $C^0$ -surface without boundary. Given a continuous embedding

$\rho \mathrm{<mo>\; :\; </mo>}{X}_1\left(G\right)$ ↪ $S$ (55)

we set $X_1\left(S\right)=\rho \left(X_1\left(G\right)\right)$ and let $X\left(S\right)=X_2\left(S\right)$ be the CW complex given by attaching the set of disjoint 2-cells $S\backslash X_1\left(S\right)$ in the canonical way. We say that $\rho$ is an elementary embedding of G into S if and only if there is a CW-complex embedding

$\xi \mathrm{<mo>\; :\; </mo>}X\left(S\right)$ ↪ $X\left(G\mathrm{,}{\bar{O}}_{\text{el}}\left(G\right)\right)\mathrm{,}\text{with}{\xi }_{\mathrm{<mo>\; |\; </mo>}{X}_1\left(S\right)}\circ \rho =i{d}_{X_1\left(G\right)}\mathrm{.}$ (56)

Thus, there are no edge crossings in $\rho \left(X_1\left(G\right)\right)$, and every 2-cell in $X\left(S\right)$ corresponds to some 2-cell in $X\left(G\mathrm{,}{\bar{O}}_{\text{el}}\left(G\right)\right)$. By considering digraphs and replacing ${\bar{O}}_{\text{el}}\left(G\right)$ with $O_{\text{el}}\left(G\right)$ directed notions can be derived.

Remark 6. Note that the usual notion of 2-cell embeddings of graphs is given by requiring only that

$\rho \mathrm{<mo>\; :\; </mo>}{X}_1\left(G\right)$ ↪ $S$ (57)

is an embedding, such that $S\backslash \rho \left(X_1\left(G\right)\right)$ is given by the union of 2-cells. Hence, an elementary embedding of G into S is a special case of a cellular embedding and therefore a stronger requirement on the embedding $\rho$. The following example makes this circumstance visible.

Example 2. Figure 4 illustrates embeddings of $K_{\mathrm{3,3}}$ into the projective plane $ℝ{\mathbb{P}}^2$ and the torus ${\mathbb{T}}^2$. We recall that $ℝ{\mathbb{P}}^2$ can be understood as the quotient $D{\mathrm{<mo>\; /\; </mo>}}_{\sim }$ of a disc $D\subseteq {ℝ}^2$ with the equivalence relation ~ defined on the boundary $\partial D\cong S^1\subseteq {ℝ}^2$ by identifying opposite points $x\sim -x$, $x\in {ℝ}^2$. In contrast, the torus ${\mathbb{T}}^2={ℝ}^2\mathrm{<mo>\; /\; </mo>}{\mathbb{Z}}^2$ is given by identifying opposite sides of a square. Consequently, the embedding of $K_{\mathrm{3,3}}$ into $ℝ{\mathbb{P}}^2$ is an elementary embedding, while the boundary of $F_3$ in ${\mathbb{T}}^2$ is not an elementary cycle. Therefore, the embedding of $K_{\mathrm{3,3}}$ into ${\mathbb{T}}^2$ is a 2-cell embedding, but not an elementary embedding.

Remark 7. Note furthermore, that in contrast to cellular embeddings an elementary embedding needs not to exist. For instance consider 2 cubes intersecting

in only one vertex. An elementary embedding could only be realized by allowing S to consist of two spheres intersecting in one point, requiring a relaxation that allows S to be a polyfold.

Given a simple undirected graph G with $G=\mathcal{G}\left(O_{\text{el}}\left(G\right)\right)$ such that there is a surface S and an elementary embedding $\rho \mathrm{<mo>\; :\; </mo>}{X}_1\left(G\right)$ ↪ $S$. Observe that the Euler characteristic of S is given by

$\chi \left(S\mathrm{,}R\right)=b_2\left(G\mathrm{,}O\mathrm{,}R\right)-b_1\left(G\mathrm{,}O\mathrm{,}R\right)+b_0\left(G\mathrm{,}O\mathrm{,}R\right)\mathrm{,}R=\mathbb{Z}\mathrm{,}{\mathbb{Z}}_2\mathrm{.}$ (58)

Since S is a closed surface, we have $b_2\left(G\mathrm{,}O\mathrm{,}{\mathbb{Z}}_2\right)=1$, while $b_2\left(G\mathrm{,}O\mathrm{,}\mathbb{Z}\right)=1$ when S is orientable and $b_2\left(G\mathrm{,}O\mathrm{,}\mathbb{Z}\right)=0$ if S is non-orientable [15].

Thus, if $b_1\left(G\mathrm{,}O\mathrm{,}\mathbb{Z}\right)=0$ then S is given by the unit sphere $S^2$ or the projective plane $ℝ{\mathbb{P}}^2$ and G is required to be (projective) planar. The detection and construction of a (projective) planar cell embedding can be done in $\mathcal{O}\left(\left|V\right|\right)$ [27] [28]. In general, the problem of finding a cellular embedding of G into a orientable surface S of minimal genus is NP-complete [29]. However, finding a cellular embedding into a surface S of maximal genus is polynomial time solvable [30]. Our strengthened notion of embeddings and the relaxation of S being allowed to be non-orientable might provides new insights into embedding theory. Note that S is determined if we can find $O\subseteq {\bar{O}}_{\text{el}}\left(G\right)$ such that:

i) For every $e\in \mathcal{E}\left({\bar{O}}_{\text{el}}\left(G\right)\right)$ there are exactly 2 cycles $c_1\mathrm{,}{c}_2$ with $e\in \mathcal{E}\left(c_1\right)\mathrm{,}e\in \mathcal{E}\left(c_2\right)$.

ii) ${\dim }_R{\langle O\rangle }_R=\left|O\right|-1$.

Thus, due to this simple description, one might finds new methods as integer linear programming techniques (ILP), which construct O and thereby S. By changing (2) into ${\dim }_R{\langle O\rangle }_R<\left|O\right|$ the case of polyfold embeddings is treated, see Remark 7.

6.2. Graph Clustering

Many applications require comparing graphs or clustering a set of graphs $\mathbb{G}$ into subsets of “similar” graphs. The distance functions $D\mathrm{<mo>\; :\; </mo>}\mathbb{G}\times \mathbb{G}\to {ℝ}^{+}$ used to measure similarity between graphs often lead to NP-complete optimization problems and can only be approximated. For instance, the graph-edit distance $D_{\text{edit}}\mathrm{<mo>\; :\; </mo>}\mathbb{G}\times \mathbb{G}\to {ℝ}^{+}$ [31] is a (pseudo) metric measuring the cost of deleting and inserting the minimum number of edges and vertices required to modify a graph $G_1$ into a graph $G_2$. Determining this distance in general is an NP-hard problem, which is why additional assumptions and restrictions to special graph classes are usually made. We posit that any feasible clustering ${\mathbb{G}}_1\mathrm{,}\cdots \mathrm{,}{\mathbb{G}}_n\subseteq \mathbb{G}$ of a given set of graphs $\mathbb{G}$, i.e., ${\mathbb{G}}_i\cap {\mathbb{G}}_j=\varnothing$, $i\ne j$, and ${\displaystyle {\cup }_{i=1}^n{\mathbb{G}}_i}=\mathbb{G}$, must fulfill the following properties:

a) Let $G_1\mathrm{,}{G}_2\in \mathbb{G}$ be isomorphic or more generally homeomorphic, then $G_1\mathrm{,}{G}_2$ belong to the same cluster, i.e., $G_1\mathrm{,}{G}_2\in {\mathbb{G}}_i$ for some $1\le i\le n$.

b) Given $G_1\mathrm{,}{G}_2\in \mathbb{G}$, the problem of deciding whether $G_1$ and $G_2$ will belong to the same cluster is solvable in polynomial time.

b) The similarity distance $D\mathrm{<mo>\; :\; </mo>}\mathbb{G}\times \mathbb{G}\to {ℝ}^{+}$ is a (pseudo) metric.

As a consequence of (c) we have that if $D\left(G_0\mathrm{,}G\right)\le d$, $d\in {ℝ}^{+}$ for all $G\in {\mathbb{G}}_i$ and some $G_0\in {\mathbb{G}}_i$, then $D\left(G_1\mathrm{,}{G}_2\right)\le 2d$ for all $G_1\mathrm{,}{G}_2\in {\mathbb{G}}_i$, $1\le i\le n$. We propose that the following distance definition based on our work leads to a feasible clustering:

Definition 9. Let $\mathbb{G}=\left\{G_1\mathrm{,}\cdots \mathrm{,}{G}_n\right\}$ be a given set of multi-digraphs and $O_1\mathrm{,}\cdots \mathrm{,}{O}_n\subseteq {\bar{O}}_{\text{el}}\left(G\right)$ be sets of elementary cycles of $G_i$, $i=1,\cdots ,n$. Then, we define the homological distance $D_H\mathrm{<mo>\; :\; </mo>}\mathbb{G}\times \mathbb{G}\to \mathbb{N}$ by

$D_H\left(G_{i_1}\mathrm{,}{G}_{i_2}\right)\mathrm{<mo>\; :\; </mo>}={\displaystyle \underset{i=0}{\overset{2}{\sum }}}\left|b_i\left(G_{i_1}\mathrm{,}{O}_{i_1}\mathrm{,}R\right)-b_i\left(G_{i_2}\mathrm{,}{O}_{i_2}\mathrm{,}R\right)\right|\mathrm{,}1\le i_1\mathrm{,}{i}_2\le n\mathrm{.}$ (59)

Certainly, $D_H$ is a pseudo metric. Further, due to Section 5, we can choose fillings $O_i$ that ensure that the Betti numbers, and thereby $D_H$, can be computed efficiently. We denote with $B_i={\displaystyle {\sum }_{k=0}^3}\left|b_k\left(G_i,O_i,R\right)\right|$ and let $\nu ={\displaystyle {\sum }_{i=1}^n}{\left(B_i-\mu \right)}^2$, $\mu =\text{mean}{\left(B_i\right)}_{i=\mathrm{1,}\cdots \mathrm{,}n}$ be the variance of the $B_i$. Consider a maximum set of graphs $G_{i_j}\in \mathbb{G}$, $1\le j<n$ with $D_H\left(G_{i_j},G_{i_{j^{\prime }}}\right)>2\nu$ for all $j\ne j^{\prime }$, then

${\mathbb{G}}_j=\left\{G\in \mathbb{G}\mathrm{<mo>\; |\; </mo>}{D}_H\left(G_{i_j}\mathrm{,}G\right)\le \nu \right\}$ (60)

yields a clustering $\mathbb{G}={\displaystyle {\cup }_{i=1}^n{\mathbb{G}}_i}$ that satisfies (a), (b), and (c) above. Due to the fact that the Betti numbers measure the topological complexity of the graphs, we expect that such a clustering will be informative in structural data analysis.

6.3. Discrete Morse Theory

Let X be a CW complex, K the set of cells of X, and $f\mathrm{<mo>\; :\; </mo>}K\to ℝ$ a given function. If the (discrete) gradient flow of f possesses no degenerate critical points or singularities f is called a discrete Morse function [32]. In this regard, the strong and weak Morse inequalities become important, stating that

$m_N-m_{N-1}+\cdots \pm m_0\ge b_N-b_{N-1}+\cdots \pm b_0$ (61)

$m_n\ge b_n\text{forall}1\le n\le N=\dim X\mathrm{,}$ (62)

where $m_n$ denotes the number of critical cells of a Morse function f with Morse index n, and $b_n=b_n\left(X\mathrm{,}K\right)$ are the Betti numbers of X w.r.t. some field e.g. ${\mathbb{Z}}_2$. Thus, if $X=X\left(G\mathrm{,}O\right)$ is given by a filling of G then we can bound the essential complexity of the dynamics from below. Since the Betti numbers do not depend on the Morse function, we can furthermore determine whether there are homotopies that reduce the complexity of the system without loosing any of its essential dynamics [32].

7. Conclusion

We extended the classic Theorem of Biggs to the case of directed cycles of multi-digraphs. These findigs were then incorporated to extend the classic interpretation of a graph G being a 1-dimensional CW complex to the 2-dimensional case by attaching 2-cells accordingly to an a priori specified set of elementary cycles $O\subseteq {\bar{O}}_{\text{el}}\left(G\right)$. We proved the associated cellular homology groups $H_k\left(G\mathrm{,}O\mathrm{,}R\right)$, $k=0,1,2$ to be free R-modules and derived formulas for computing their Betti numbers. Of course, one could ask for extending these considerations to even higher dimensions. However, in order to describe a 3-cell, we need to know all cycles forming its boundary. Thus, dealing with higher-dimensional cells makes computing the Betti numbers combinatorically harder, which made us restricting to the presented case.

7.1. Classic Graph-Theoretical Problems

It is natural to ask the question how classic graph-theoretical problems behave for certain classes of graphs. Here we provided some methods to classify graphs with respect to certain aspects of their topology. The fillings presented in Section 5 might be a good starting point of investigating classic graph theoretical problems on graphs with bounded topological complexity in terms of the derived Betti numbers. For instance the Feedback Arc Set Problem, which is to delete as less edges as possible to make G acyclic, could profit from certain obstructions on the cycle topology, [33] [34], as derived in Section 5.2. Further, the understanding of cliques of a graph is crucial if one wants to determine its chromatic numbers [35]. Despite for coloring problems [8], the minimal genus of a graph plays an important role within the unresolved Graph Isomorphism Problem [36] or extensions of Whitney’s Theorem [11].

7.2. Related Complexes and Homology Theories

In addition to the concepts presented here, there are multiple other possibilities of assigning complexes and (co)-homologies to a given graph G [37] [38] [39]. Translations of these theories in terms of our contribution are certainly of interest.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Mcnaught, A.D. and Wilkinson, A. (1997) IUPAC. Compendium of Chemical Terminology. 2nd Edition (the “Gold Book”), Wiley Blackwell, Hoboken.
[2]	Dokholyan, N.V., Li, L., Ding, F. and Shakhnovich, E.I. (2002) Topological Determinants of Protein Folding. Proceedings of the National Academy of Sciences, 99, 8637-8641. https://doi.org/10.1073/pnas.122076099
[3]	Albert, R. (2005) Scale-Free Networks in Cell Biology. Journal of Cell Science, 118, 4947-4957. https://doi.org/10.1242/jcs.02714
[4]	Barkai, N. and Leibler, S. (1997) Robustness in Simple Biochemical Networks. Nature, 387, 913-917. https://doi.org/10.1038/43199
[5]	Anderson, J.A. (1995) An Introduction to Neural Networks. MIT Press, Cambridge. https://doi.org/10.7551/mitpress/3905.001.0001
[6]	Otte, E. and Rousseau, R. (2002) Social Network Analysis: A Powerful Strategy, Also for the Information Sciences. Journal of Information Science, 28, 441-453. https://doi.org/10.1177/016555150202800601
[7]	Hopcroft, J.E. and Wong, J.K. (1974) Linear Time Algorithm for Isomorphism of Planar Graphs (Preliminary Report). In: Proceedings of the 6th Annual ACM Symposium on Theory of Computing, STOC ‘74, ACM, New York, 172-184. https://doi.org/10.1145/800119.803896
[8]	Berge, C. (2001) The Theory of Graphs. Dover Books on Mathematics. Dover, New York.
[9]	Deı, V.G., Klinz, B., Woeginger, G.J., et al. (2006) Exact Algorithms for the Hamiltonian Cycle Problem in Planar Graphs. Operations Research Letters, 34, 269-274. https://doi.org/10.1016/j.orl.2005.04.013
[10]	Berge, C. and Ghouila-Houri, A. (1965) Programming, Games and Transportation Networks. Methuen, London.
[11]	Whitney, H. (1992) Congruent Graphs and the Connectivity of Graphs. In: Hassler Whitney Collected Papers, Springer, Berlin, 61-79. https://doi.org/10.1007/978-1-4612-2972-8_4
[12]	Arora, S. and Barak, B. (2009) Computational Complexity: A Modern Approach. Cambridge University Press, New York.
[13]	Gross, J.L. and Tucker, T.W. (1987) Topological Graph Theory. Wiley-Interscience, New York.
[14]	Biggs, N. (1993) Algebraic Graph Theory. 2nd Edition, Cambridge University Press, Cambridge.
[15]	Hatcher, A. (2002) Algebraic Topology. Cambridge University Press, Cambridge.
[16]	Tarjan, R. (1972) Depth-First Search and Linear Graph Algorithms. SIAM Journal on Computing, 1, 146-160. https://doi.org/10.1137/0201010
[17]	Bang-Jensen, J. and Gutin, G.Z. (2008) Digraphs: Theory, Algorithms and Applications. 2nd Edition, Springer Publishing Company, Incorporated, Berlin.
[18]	Hopcroft, J. and Tarjan, R. (1973) Algorithm 447: Efficient Algorithms for Graph Manipulation. Communications of the ACM, 16, 372-378. https://doi.org/10.1145/362248.362272
[19]	Roberts, B. and Kroese, D. (2007) Estimating the Number of ST Paths in a Graph. Journal of Graph Algorithms and Applications, 11, 195-214. https://doi.org/10.7155/jgaa.00142
[20]	Johnson, D.B. (1977) Efficient Algorithms for Shortest Paths in Sparse Networks. Journal of the ACM (JACM), 24, 1-13. https://doi.org/10.1145/321992.321993
[21]	Hagerup, T. (2000) Improved Shortest Paths on the Word Ram. In: International Colloquium on Automata, Languages, and Programming, Springer, Berlin, 61-72. https://doi.org/10.1007/3-540-45022-X_7
[22]	Dijkstra, E.W. (1959) A Note on Two Problems in Connexion with Graphs. Numerische Mathematik, 1, 269-271. https://doi.org/10.1007/BF01386390
[23]	Cheung, H.Y., Kwok, T.C. and Lau, L.C. (2013) Fast Matrix Rank Algorithms and Applications. Journal of the ACM (JACM), 60, 31. https://doi.org/10.1145/2528404
[24]	Preiss, B.R. (1999) Data Structures and Algorithms with Object-Oriented Design Patterns in C++. John Wiley & Sons Inc., New York.
[25]	Karp, R.M. (1972) Reducibility among Combinatorial Problems. In: Miller, R.E. and Thatcher, J.W., Eds., Complexity of Computer Computations, Plenum Press, New York, 85-103. https://doi.org/10.1007/978-1-4684-2001-2_9
[26]	Bron, C. and Kerbosch, J. (1973) Algorithm 457: Finding All Cliques of an Undirected Graph. Communications of the ACM, 16, 575-577. https://doi.org/10.1145/362342.362367
[27]	Gagarin, A. (2003) Graph Embedding Algorithms.
[28]	Hopcroft, J. and Tarjan, R. (1974) Efficient Planarity Testing. Journal of the ACM (JACM), 21, 549-568. https://doi.org/10.1145/321850.321852
[29]	Thomassen, C. (1989) The Graph Genus Problem Is NP-Complete. Journal of Algorithms, 10, 568-576. https://doi.org/10.1016/0196-6774(89)90006-0
[30]	Furst, M.L., Gross, J.L. and McGeoch, L.A. (1988) Finding a Maximum-Genus Graph Imbedding. Journal of the ACM, 35, 523-534. https://doi.org/10.1145/44483.44485
[31]	Hecht, M. (2017) A Generalization of the Most Common Subgraph Distance and Its Application to Graph Editing. Pattern Recognition Letters, 87, 71-78. https://doi.org/10.1016/j.patrec.2016.09.008
[32]	Forman, R. (1998) Morse Theory for Cell Complexes. Advances in Mathematics, 134, 90-145. https://doi.org/10.1006/aima.1997.1650
[33]	Hecht, M. (2018) Exact Localisations of Feedback Sets. Theory of Computing Systems, 62, 1048-1084. https://doi.org/10.1007/s00224-017-9777-6
[34]	Hecht, M., Gonciarz, K. and Horvát, S. (2021) Tight Localizations of Feedback Sets. ACM Journal of Experimental Algorithmics, 26, 1-19. https://doi.org/10.1145/3447652
[35]	Johnson, D.S. and Trick, M.A. (1996) Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, October 11-13, 1993. Volume 26, American Mathematical Society, Boston.
[36]	Babai, L. (2016) Graph Isomorphism in Quasi-Polynomial Time. In: Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, ACM, New York, 684-697. https://doi.org/10.1145/2897518.2897542
[37]	Grigor’yan, A., Lin, Y., Muranov, Y. and Yau, S.-T. (2012) Homologies of Path Complexes and Digraphs.
[38]	Grigor’yan, A., Lin, Y., Muranov, Y. and Yau, S.-T. (2014) Cohomology of Digraphs and (Undirected) Graphs. Asian Journal of Mathematics, 19, 887-932.
[39]	Jonsson, J. (2008) Simplicial Complexes of Graphs. Springer-Verlag, Berlin. https://doi.org/10.1007/978-3-540-75859-4