Graph homology

In algebraic topology and graph theory, graph homology describes the homology groups of a graph, where the graph is considered as a topological space. It formalizes the idea of the number of "holes" in the graph. It is a special case of a simplicial homology, as a graph is a special case of a simplicial complex. Since a finite graph is a 1-complex (i.e., its 'faces' are the vertices - which are 0-dimensional, and the edges - which are 1-dimensional), the only non-trivial homology groups are the 0-th group and the 1-th group.
The 1st homology group.
The general formula for the 1st homology group of a topological space "X" is:formula_1 The example below explains these symbols and concepts in full detail on a graph.
Example.
Let "X" be a directed graph with 3 vertices {x,y,z} and 4 edges {a: x→y, b: y→z, c: z→x, d: z→x}. It has several "cycles":
If we cut the plane along the loop a+b+d, and then cut at c and "glue" at d, we get a cut along the loop a+b+c. This can be represented by the following relation: (a+b+d) + (c-d) = (a+b+c). To formally define this relation, we define the following commutative groups:
Most elements of "C"1 are not cycles, for example a+b, 2a+5b-c, etc. are not cycles. To formally define a cycle, we first define "boundaries". The boundary of an edge is denoted by the formula_2 operator and defined as its target minus its source, so formula_3 So formula_2 is a mapping from "C"1 to "C"0. Since a,b,c,d are the generators of "C"1, this formula_2 naturally extends to a group homomorphism from "C"1 to "C"0. In this homomorphism, formula_6. Similarly, formula_2 maps any cycle in "C"1 to the zero element of "C"0. In other words, the set of cycles in C1 is exactly the null space (the kernel) of formula_2. In this case, the kernel of formula_2 has two generators: one corresponds to a+b+c and the other to a+b+d (the third cycle, c-d, is a linear combination of the first two). So ker formula_2is isomorphic to Z2.
In a general topological space, we would define higher-dimensional chains. In particular, "C"2 would be the free abelian group on the set of 2-dimensional objects. However, in a graph there are no such objects, so "C"2 is a trivial group. Therefore, the image of the second boundary operator, formula_11, is trivial too. Therefore:formula_12 This corresponds to the intuitive fact that the graph has two "holes". The exponent is the number of holes.
General case.
The above example can be generalized to an arbitrary connected graph "G" = ("V", "E"). Let "T" be a spanning tree of "G". Every edge in "E" \ "T" corresponds to a cycle; these are exactly the linearly independent cycles. Therefore, the first homology group "H"1 of a graph is the free abelian group with |"E" \ "T"| generators. This number equals |"E"|-|"V"|+1; so:formula_13 It can be generated by any |"C"|-tuple of vertices, one from each component.
Reduced homology.
Often, it is convenient to assume that the 0-th homology of a connected graph is trivial (so that, if the graph contains a single point, then all its homologies are trivial). This leads to the definition of the reduced homology. For a graph, the reduced 0-th homology is: formula_14 This "reduction" affects only the 0-th homology; the reduced homologies of higher dimensions are equal to the standard homologies.
Higher dimensional homologies.
A graph has only vertices (0-dimensional elements) and edges (1-dimensional elements). We can generalize the graph to an abstract simplicial complex by adding elements of a higher dimension. Then, the concept of graph homology is generalized by the concept of simplicial homology.
Example.
In the above example graph, we can add a two-dimensional "cell" enclosed between the edges c and d; let's call it A and assume that it is oriented clockwise. Define "C"2 as the free abelian group generated by the set of two-dimensional cells, which in this case is a singleton {A}. Each element of "C"2 is called a "2-dimensional chain".
Just like the boundary operator from "C"1 to "C"0, which we denote by formula_2, there is a boundary operator from "C"2 to "C"1, which we denote by formula_11. In particular, the boundary of the 2-dimensional cell A are the 1-dimensional edges c and d, where c is in the "correct" orientation and d is in a "reverse" orientation; therefore: formula_17. The sequence of chains and boundary operators can be presented as follows: formula_18 The addition of the 2-dimensional cell A implies that its boundary, c-d, no longer represents a hole (it is homotopic to a single point). Therefore, the group of "holes" now has a single generator, namely a+b+c (it is homotopic to a+b+d). The first homology group is now defined as the quotient group: formula_1 Here, formula_20 is the group of 1-dimensional cycles, which is isomorphic to Z2, and formula_21 is the group of 1-dimensional cycles that are boundaries of 2-dimensional cells, which is isomorphic to Z. Hence, their quotient "H"1 is isomorphic to Z. This corresponds to the fact that "X" now has a single hole. Previously. the image of formula_11 was the trivial group, so the quotient was equal to formula_23. Suppose now that we add another oriented 2-dimensional cell B between the edges c and d, such that formula_24. Now "C"2 is the free abelian group generated by {A,B}. This does not change "H"1 - it is still isomorphic to Z (X still has a single 1-dimensional hole). But now "C"2 contains the two-dimensional cycle A-B, so formula_11 has a non-trivial kernel. This cycle generates the second homology group, corresponding to the fact that there is a single two-dimensional hole: formula_26 We can proceed and add a 3-cell - a solid 3-dimensional object (called C) bounded by A and B. Define "C"3 as the free abelian group generated by {C}, and the boundary operator formula_27. We can orient C such that formula_28; note that the boundary of C is a cycle in "C"2. Now the second homology group is: formula_29 corresponding to the fact that there are no two-dimensional holes (C "fills the hole" between A and B).
General case.
In general, one can define chains of any dimension. If the maximum dimension of a chain is "k", then we get the following sequence of groups: formula_30 It can be proved that any boundary of a ("k"+1)-dimensional cell is a "k"-dimensional cycle. In other words, for any "k", formula_31(the group of boundaries of "k"+1 elements) is contained in formula_32 (the group of "k"-dimensional cycles). Therefore, the quotient formula_33 is well-defined, and it is defined as the "k"-th homology group: formula_34