Biggs Theorem for Directed Cycles and Topological Invariants of Digraphs ()
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
of a simple digraph G generates a free R-module or vector space
of dimension
(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
,
spanned by all directed cycles
of a multi-digraph G.
1.1. Statement of Contribution
We denote by
the set of all directed or connected elementary cycles (passing no vertex twice) of a multi-digraph G and by
the induced subgraphs, respectively. Then we prove the following generalization of Biggs Theorem.
Theorem 1 (Biggs Theorem for directed cycles).Let
be a multi-digraph and
its connected cycle space with respect to
. Then
if and only if
. (2)
Consequently, in case of equivalence, there holds
(3)
Indeed the construction of the induced subgraph
is given by the union of all strongly connected components, which therefore can be realized in
[16]. Consequently, Theorem 1 allows to determine
efficiently in
. The efficient computation of
potentially addresses many challenging problems in graph theory. In this article, we extend the 1-dimensional CW-complex
given by the geometrical realization of G given by attaching 2-cells accordingly to a chosen set of elementary cycles
. 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
,
.
Theorem 2 (Homology of the Elementary Filling). Let
be a multi-digraph,
,
and
the geometrical realization induced by the choice of
. The associated cellular homology groups
are free R-modules of ranks
,
.
i)
and can be computed in
.
ii)
and
.
If
then
can be computed in
.
iii)
. If
then it is #P-hard (sharp P-hard) to compute
.
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
of G with respect to the set of cycles
. To overcome the involvement of a #P-hard counting problem in iii), we suggest several representation independent sub-fillings
allowing to compute
,
, 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
be a 4-tuple, where
are finite sets and
are some maps. We call the elements
vertices and the elements
edges of G, while
are called head and tail of the edge e. An edge e with
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
, with
is injective.
ii) If there are no loops, i.e.,
with
, then G is called simple.
ii) G is called an undirected graph if G is a digraph and for every
there is
with
,
. In this case, we slightly simplify notation by shortly writing e for the pair
, which is then called an edge. The notion of
can thereby be replaced by
with
.
iv) In the special case, where
the maps
are assumed to be canonically given by the relation of E, i.e.,
,
for all
.
One readily observes that our definition coincides with the common understanding of graphs. As said, the notion allows to consider multiple edges
with
,
by distinguishing
. Thus, no considerations of multi-sets E as in [17] are needed. We denote with
,
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
and are called connected if
. The degree
of a vertex
is given by the number of all edges
that are connected with v. A directed path
of length
from a vertex u to a vertex v is a list of consecutive edges
,
such that
and
. Thereby, repetition is allowed, i.e.,
,
is possible. A connected path
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
,
,
of edges with their converse directed versions.
A directed (connected) cycle is a directed (connected) path p from some vertex
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
the set of all connected or directed cycles and with
the set of all directed, connected elementary cycles, respectively. In fact, every simple or even non-simple cycle
is generated by passing through several elementary cycles
,
.
Given
,
we introduce the equivalence relation
iff d can be derived from
by cyclic reordering, i.e., there is
with
,
. We denote with
and
the quotients of non-equivalent cycles and count
up to equivalence, i.e.,
,
. While non-elementary cycles
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
and
, respectively.
Example 1. For G in Figure 1 the cycle
is a directed, simple and non-elementary cycle, while the directed cycles
and
are elementary. Certainly,
is given by passing through
and
. Further, the cycle
while
. The only reorderings of
keeping the edges consecutive are cyclic reorderings.
With
,
we denote the graphs obtained by deleting the edge e or the vertex v and all its connected edges. Further,
,
,
denote the graph, the set of all edges, and the set of all vertices induced by a set of graphs, edges and vertices. By
we denote the power set of a given set A of finite cardinality
.
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
be a multi-digraph we introduce the free R-modules,
(4)
(5)
Let
,
,
be an ordered list of connected edges. Then for
we define
(6)
If
is a cycle then we set
if
are consecutive and
else. If
then we set
. By considering
,
the vectors
(7)
are called the characteristic vectors of
with respect to
-and
-coefficients.
Remark 1. We want the following fact to be clear. The characteristic vector depends on the ordering of
. However, if
are connected elementary cycles such that
are equivalent. Then
holds. If
are directed then even
holds. Thus, the maps
(8)
are well defined.
Definition 3 (Incidence operator). Let
be a multi-digraph. We denote with
,
the
-linear incidence operator operators, defined on the generators by
(9)
(10)
By choosing an enumeration
,
we can represent
by the classic incidence matrix
with
(11)
The notion of
is given by setting
.
By Remark 1 the characteristic vector
,
might depend on the ordering of c. However, the kernel of
is not sensitive to the possible choices of signs. Therefore, we obtain a well defined algebraic notion of cycles as follows.
Lemma 3. Let
be a multi-digraph and
be a set of elementary cycles. Then we denote with
(12)
(13)
the set of all characteristic vectors induced by cycles in O. The free generated cycle modules are given by
where
,
denotes the span with respect to
.
Proof. The identities
follow directly by the definition of
. Further, we verify that for any list
of connected edges, due to (6), we have
(14)
Hence,
(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
be a simple digraph then the dimension of the connected cycle spaces are given by
(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
for any fixed enumeration of
. In fact, the proof of Theorem 4 is based on computing the rank of
, 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
be a multi-digraph. Then the dimension of the connected cycle spaces are given by
(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
or two cycle
,
is R-linear independent, to all other elements in
. Thus, by removing e we obtain
. Recursively applying this procedure ends up with a simple digraph
with
. Thus, due to Theorem 4 we compute
(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
be a multi-digraph and
. Let
,
. An equivalence relation
on V is defined by
(19)
The equivalence class of
is denoted by
and
gives the quotient of V with respect to
. Further, we define
and set
(20)
The multi-digraph
is called the contracted graph of G with respect to
. If
then we observe that
. Thus, if
is a subgraph then
can be defined by contracting
in arbitrary order, yielding a well defined notion.
Remark 2. Let
be a simple digraph and
such that
are consecutive and
. Then
becomes a multi-digraph, i.e., h and f become parallel edges in
. Furthermore, the contraction of a two cycle
,
,
results in a loop
. 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.,
.
Now we have all ingredients to state the first main theorem of this article.
Theorem 5 (Biggs Theorem for directed cycles). Let
be a multi-digraph and
its cycle space with respect to
. Then
if and only if
. (21)
Consequently, in case of equivalence, there holds
(22)
Proof. The proof splits into several steps:
Step 1: We show
. Indeed, given
. Then we can generate
by characteristic vectors of directed elementary cycles
,
. Thus, every
hast to be contained in at least one of them proving
.
Step 2: We show
. Indeed,
implies that by Lemma 3
is a free sub-module of
. Thus, it suffices to show (22) in order to prove the converse inclusion. We argue by induction on
. If
then there are only loops. Thus,
(23)
and the claim follows. Now assume that
. Let
be not a loop; then we consider the contracted graph
. Let
if
and
or
,
then certainly
. If
then
remains elementary. If
and
then
consists of two elementary cycles
with one of them being a loop. Thus,
. By induction, we therefore compute
(24)
Step 2a: We show that
. Let
with
. By choosing an equivalent cycle
,
if necessary w.l.o.g. we can assume that c is ordered such that
,
,
. Conversely, for every cycle
we choose an ordering
such that either
or
becomes a cycle in
. We consider the map
↪
(25)
Given
,
such that
are a basis of
. Then
induces a
-linear injective lift
(26)
Step 2b: We show that
. Indeed, if
is such that
has no negative entries then
and
. If this is not the case then the entry
corresponding to f is the only negative entry. Since
there is
with
.
For any
we denote by
the directed subpath of
connecting x and y. Further, let
be all crossing vertices such that for the edges
with
we have
and
,
. Analogously, we consider all crossing vertices
such that for the edges
with
we have
and
. Moreover, we assume that
and that the
are ordered w.r.t the ordering of directed path
. We consider two cases.
Case 1: If
then setting
,
yields
, see Figure 2 and thereby
(27)
implying
.
Case 2: If
then we construct three cycles
by
(28)
see again Figure 3 for an illustration, where
is indicated by the black lines. Since
are elementary we have that the connected components of
Figure 2. Sketch of the cycle construction for Case 1.
(29)
are pairwisely disjoint paths. Moreover,
are elementary. Therefore, we verify again that
(30)
holds and thereby implies that
. Hence,
and we have proven Step 2. Thus, due to Corollary 1 we have proven the theorem for
.
Step 3: For
the claim follows by using that
is equivalent to
as proven above. Then the identity
(31)
proves the theorem with respect to
-coefficients.
Remark 3. For simplification, the sketch of Case 2 in Figure 3 assumes that the paths
are not nested, which might be not true in general. However, this circumstance does not affect (29) nor the fact that
are elementary, which were all assumptions we used for the argumentation.
An immediate consequence of Theorem 5 is the following.
Corollary 2. Let
be a multi-digraph. Then
(32)
can be determined in
.
Proof. By Theorem 5 we have
and therefore
. Now
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
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
be a multi-digraph and
be a set of elementary connected cycles. A map
is called a coherent orientation w.r.t. O iff
i)
for all
ii)
for all characteristic vectors
with
.
Lemma 6. Let
be a multi-digraph and
be a set of elementary connected cycles. Then there exists a coherent orientation
.
Proof. We argue by induction on
. If
then we choose an ordering
and thereby a representative of all equivalent cycles in O. Thus, setting
with
defines a coherent orientation. Now assume that
. Let
and
be the set of all cycles being not equivalent to c. We consider
and a splitting
into elementary connected components. That is
(33)
By induction there is a coherent orientation
w.r.t.
. Let
be the characteristic vector of c. Assume there are
with
and
. Then
belong to different components, i.e.,
,
,
. Observe, that we can change
to
on every component
by keeping the requirements of a coherent orientation preserved. Thus, we can change
to
such that
for all
. Hence, setting
on
and
for all
yields a coherent orientation.
Definition 6 (Elementary CW Complex). Let
be a multi-digraph and
be its geometric realization. Further, let
be a set of elementary connected cycles. The geometric realization
given by attaching 2-cells to
accordingly to O is called the elementary CW complex of G w.r.t. O. Further,
shall denote the set of
-cells of
, and
(34)
the maps yielding the identification of
-cells with vertices, edges and cycles, respectively.
Indeed, for the complexes
,
the cellular homology can be derived by considering the following chain complexes.
Definition 7 (Elementary Chain Complex). Let G be a multi-digraph,
, be a set of elementary connected cycles,
and
be a coherent orientation w.r.t. O. Let
be the associated CW complex. We consider the free generated R-modules
(35)
For
, we define the boundary operators
,
on the generators by
,
(36)
and
,
(37)
For
we consider
and
, respectively. We enforce
to be R-linear by setting
,
for all
,
,
,
. Finally, we set
and
for
.
Remark 1 asserts why even in case of
-coefficients the maps
yield well defined boundary operators. More precisely:
Theorem 7. Let
be a multi-digraph,
be a set of connected elementary cycles and
be a coherent orientation w.r.t. O. Let
be the elementary CW complex,
and
be given due to Definition 7.
i) The pairs
define a finite chain complex, i.e.,
for all
.
ii) The cellular homology groups
are free R-modules
,
(38)
(39)
(40)
iii) The Betti numbers are given by
(41)
(42)
(43)
Proof. By considering the sequence
(44)
the identities
, follow for
. For
and
we consider the induced characteristic vectors
(45)
(46)
Then we observe that
,
, where
denotes the incidence operator of G. Thus,
if and only if
corresponds to a cycle, i.e.,
,
. By definition of
and Lemma 3, this yields
and consequently
, showing (i). Furthermore, we realize that,
and
. Thus,
is free generated by O, implying that
. By using the dimension formula we realize that the quotient
is a free R-module of dimension
(47)
Likewise,
implies that
. Since
and
are free R-modules, there are isomorphisms
,
. Let
↪
be the natural embedding and
be a basis of
then
can be extended to a basis
of
and
yields a basis of
containing
as a sub-basis of
. Thus,
showing that the 1-st homology
is a free R-module of dimension
(48)
Since
and
are free R-modules we analogously observe that there is a sub-basis of
generating
. Hence,
is a free R-module of dimension
(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
,
.
Remark 5. The singular homology
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
. Further, we obtain the following consequence that yields main Theorem 2.
Corollary 3. Let the assumptions of Theorem 7 be fulfilled and denote with
the R-rank of the cellular homology group
,
.
i)
can be computed in
.
ii)
and
can be computed in
.
iii) Computing
,
is #P-hard (sharp P-hard).
Proof. The number of connected components of any multi-graph can be determined by breadth-first search within
[18], yielding i) due to Theorem 7. To show ii), recall that by Lemma 3, we have that
yielding
. Due to Corollary 2, computing
can be done in
. Thus, by Theorem 7, the bottleneck for computing
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
and
are called homeomorphic if there are sets of directed paths
such that
for any inner vertex
of
or
, respectively, and the graphs
given by contracting
are isomorphic.
Corollary 4. Let
and
be two homeomorphic multi-digraphs. We denote with
,
, consider the elementary CW complexes
,
,
and
. Then
(50)
(51)
where
.
Proof. As one can readily verify, neither the number of cycles
,
nor the dimension
,
nor the number of connected components of
change under the contraction of the paths
,
yielding the claim due to Theorem 7.
Due to Corollary 3 (3) counting
is #P-hard. Though there are efficient algorithms [19] counting the number of cycles approximately, we, here, suggest to consider certain sub-fillings
to yield an suitable setup.
5. Representation Invariant Sub-Fillings
In this section we discuss several possibilities of filling the graph G by choosing
, such that the cellular homology of the resulting CW complexes
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
are R-linear independent then due to Theorem 7 for the CW complex
the Betti numbers are given by
,
and
. Thus,
is given by the co-dimension of
in
. Thereby, fillings by R-linear independent cycles or basis yield only trivial topological information.
5.2. Fillings Induced by Shortest Cycles
Let
be a multi-digraph. We consider the set of all shortest cycles
(52)
Further,
,
,
denote the set of all incoming or outgoing edges of
, and their unions.
Lemma 8. Let
be a multi-digraph and
its maximum degree.
i)
.
ii)
can be determined in
.
Proof. Note that the all-shortest path problem, which is to find a shortest connected path between all pairs of vertices
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
. We consider all edges
with shortest path
of minimum length
such that
becomes a shortest cycle
. For any outgoing edge
we denote with
and with
the possibly empty shortest cycle w.r.t.
. Then we observe that
(53)
Thus, i) follows. Further, due to Edsger W. Dijkstra’s famous shortest path algorithm [22] each cycle
can be computed in
yielding ii).
Certainly,
for all isomorphic graphs
. Further, the associated Betti numbers
,
,
of
can be computed efficiently due to Lemma 8 and Theorem 7. Indeed the bottleneck is given by computing
, which requires at most
by applying Gauss elimination or can be done even faster [23].
Recursively applying this procedure to the contraction
provides an array of Betti numbers
,
,
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
with
for all
are similar and
are not isomorphic whenever
differ for some
.
5.3. Fillings Induced by Cliques
Let
,
, denote the complete undirected graph of n vertices,
. Then the number of cycles
, up to cyclic reordering, is given by all subsets of vertices larger than 3, i.e.,
(54)
which can be computed in
[24]. Since
, computing the Betti numbers of
can be done in
. Let
be the set of all cliques
of size
. Let
,
with
. Then we consider a set of cycles
such that
and
,
. The geometric realization
is a canonical filling in the following sense:
The number of cycles
can be computed efficiently due to (54). On the other hand
contains all triangles of
, which generate
,
. Thus,
. Hence, due to Theorem 7 the associated Betti numbers can be computed efficiently once the cliques
have been determined.
Note that the general clique problem, i.e., finding a clique of given size
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
. 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
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
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
into
(left) and
(right).
Definition 8 (Elementary embedding). Let G be a simple undirected graph,
its 1-dimensional geometric realization, and S a compact, connected
-surface without boundary. Given a continuous embedding
↪
(55)
we set
and let
be the CW complex given by attaching the set of disjoint 2-cells
in the canonical way. We say that
is an elementary embedding of G into S if and only if there is a CW-complex embedding
↪
(56)
Thus, there are no edge crossings in
, and every 2-cell in
corresponds to some 2-cell in
. By considering digraphs and replacing
with
directed notions can be derived.
Remark 6. Note that the usual notion of 2-cell embeddings of graphs is given by requiring only that
↪
(57)
is an embedding, such that
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
. The following example makes this circumstance visible.
Example 2. Figure 4 illustrates embeddings of
into the projective plane
and the torus
. We recall that
can be understood as the quotient
of a disc
with the equivalence relation ~ defined on the boundary
by identifying opposite points
,
. In contrast, the torus
is given by identifying opposite sides of a square. Consequently, the embedding of
into
is an elementary embedding, while the boundary of
in
is not an elementary cycle. Therefore, the embedding of
into
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
such that there is a surface S and an elementary embedding
↪
. Observe that the Euler characteristic of S is given by
(58)
Since S is a closed surface, we have
, while
when S is orientable and
if S is non-orientable [15].
Thus, if
then S is given by the unit sphere
or the projective plane
and G is required to be (projective) planar. The detection and construction of a (projective) planar cell embedding can be done in
[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
such that:
i) For every
there are exactly 2 cycles
with
.
ii)
.
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
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
into subsets of “similar” graphs. The distance functions
used to measure similarity between graphs often lead to NP-complete optimization problems and can only be approximated. For instance, the graph-edit distance
[31] is a (pseudo) metric measuring the cost of deleting and inserting the minimum number of edges and vertices required to modify a graph
into a graph
. 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
of a given set of graphs
, i.e.,
,
, and
, must fulfill the following properties:
a) Let
be isomorphic or more generally homeomorphic, then
belong to the same cluster, i.e.,
for some
.
b) Given
, the problem of deciding whether
and
will belong to the same cluster is solvable in polynomial time.
b) The similarity distance
is a (pseudo) metric.
As a consequence of (c) we have that if
,
for all
and some
, then
for all
,
. We propose that the following distance definition based on our work leads to a feasible clustering:
Definition 9. Let
be a given set of multi-digraphs and
be sets of elementary cycles of
,
. Then, we define the homological distance
by
(59)
Certainly,
is a pseudo metric. Further, due to Section 5, we can choose fillings
that ensure that the Betti numbers, and thereby
, can be computed efficiently. We denote with
and let
,
be the variance of the
. Consider a maximum set of graphs
,
with
for all
, then
(60)
yields a clustering
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
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
(61)
(62)
where
denotes the number of critical cells of a Morse function f with Morse index n, and
are the Betti numbers of X w.r.t. some field e.g.
. Thus, if
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
. We proved the associated cellular homology groups
,
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.