Editing Cyclomatic complexity (section)

== {{anchor|Explanation in terms of algebraic topology}}In algebraic topology ==
An even subgraph of a graph (also known as an [[Eulerian path|Eulerian subgraph]]) is one in which every [[vertex (graph theory)|vertex]] is [[Graph (discrete mathematics)#Graph|incident]] with an even number of edges. Such subgraphs are unions of cycles and isolated vertices. Subgraphs will be identified with their edge sets, which is equivalent to only considering those even subgraphs which contain all vertices of the full graph.

The set of all even subgraphs of a graph is closed under [[symmetric difference]], and may thus be viewed as a [[vector space]] over [[GF(2)]]. This vector space is called the cycle space of the graph. The [[cyclomatic number]] of the graph is defined as the [[dimension (vector space)|dimension]] of this space. Since GF(2) has two elements and the cycle space is necessarily finite, the cyclomatic number is also equal to the [[binary logarithm|2-logarithm]] of the number of elements in the cycle space.

A [[basis (linear algebra)|basis]] for the cycle space is easily constructed by first fixing a [[Glossary of graph theory#Trees|spanning forest]] of the graph, and then considering the cycles formed by one edge not in the forest and the path in the forest connecting the endpoints of that edge. These cycles form a basis for the cycle space. The cyclomatic number also equals the number of edges not in a maximal spanning forest of a graph. Since the number of edges in a maximal spanning forest of a graph is equal to the number of vertices minus the number of components, the formula <math>E-N+P</math> defines the cyclomatic number.<ref>{{cite book |last=Diestel |first=Reinhard |title=Graph theory |publisher=Springer |year=2000 |isbn=978-0-387-98976-1 |edition=2 |series=Graduate texts in mathematics '''173''' |location=New York}}</ref>

Cyclomatic complexity can also be defined as a relative [[Betti number]], the size of a [[relative homology]] group:<math display="block">M := b_1(G,t) := \operatorname{rank}H_1(G,t),</math>

which is read as "the rank of the first [[Homology (mathematics)|homology]] group of the graph ''G'' relative to the [[Tree (data structure)#Terminology|terminal nodes]] ''t''". This is a technical way of saying "the number of linearly independent paths through the flow graph from an entry to an exit", where:
* "linearly independent" corresponds to homology, and backtracking is not double-counted;
* "paths" corresponds to first homology (a path is a one-dimensional object); and
* "relative" means the path must begin and end at an entry (or exit) point.

This cyclomatic complexity can be calculated. It may also be computed via absolute [[Betti number]] by identifying the terminal nodes on a given component, or drawing paths connecting the exits to the entrance. The new, augmented graph <math>\tilde G</math> obtains
<math display="block">M = b_1(\tilde G) = \operatorname{rank}H_1(\tilde G).</math>

It can also be computed via [[homotopy]]. If a (connected) control-flow graph is considered a one-dimensional [[CW complex]] called <math>X</math>, the [[fundamental group]] of <math>X</math> will be <math>\pi_1(X) \cong \Z^{*n}</math>. The value of <math>n+1</math> is the cyclomatic complexity. The fundamental group counts how many loops there are through the graph up to homotopy, aligning as expected.