Revision as of 11:24, 22 May 2022 edit DannyStoll (talk \| contribs) 1 edit →Explanation in terms of algebraic topology: Clarified notation for fundamental group as a free product rather than a direct product. Added stipulation that the control graph be connected in the relevant discussion. Tags: Mobile edit Mobile web edit ← Previous edit		Revision as of 02:29, 28 June 2022 edit undo BrownHairedGirl (talk \| contribs) Autopatrolled, Extended confirmed users, File movers, Pending changes reviewers, Rollbackers 2,942,733 edits m clean up Tag: AWB Next edit →
Line 62: 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 of this space. Since GF(2) has two elements and the cycle space is necessarily finite, the cyclomatic number is also equal to the 2-logarithm of the number of elements in the cycle space. A 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 constitute a basis for the cycle space. Hence, 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> above for the cyclomatic number follows.<ref>{{cite book \|last=Diestel \|first=Reinhard

Cyclomatic complexity: Difference between revisions