Circuit rank: Difference between revisions

Revision as of 18:18, 28 May 2012

Template:Undirected graph numerical invariant

Definition

Definition for a finite graph

Suppose $G$ is a finite undirected graph. The circuit rank of $G$ , also called the cyclomatic number of $G$ , is defined in the following equivalent ways:

It is the minimum number of edges that needs to be removed from the edge set of $G$ to make it a forest (i.e., an acyclic graph)
It is given by $|E(G)|-|V(G)|+c$ where $V(G)$ is the vertex set, $E(G)$ is the edge set, and $c$ is the number of conncted components of $G$ .

@@ Line 5: / Line 5: @@
 ===Definition for a finite graph===
-Suppose <math>G</math> is a [[finite graph|finite]] [[undirected graph]]. The '''circuit rank''' of <math>G</math>, also called the '''cyclotomic number''' of <math>G</math>, is defined in the following equivalent ways:
+Suppose <math>G</math> is a [[finite graph|finite]] [[undirected graph]]. The '''circuit rank''' of <math>G</math>, also called the '''cyclomatic number''' of <math>G</math>, is defined in the following equivalent ways:
 # It is the minimum number of edges that needs to be removed from the edge set of <math>G</math> to make it a [[forest]] (i.e., an acyclic graph)
 # It is given by <math>|E(G)| - |V(G)| + c</math> where <math>V(G)</math> is the vertex set, <math>E(G)</math> is the edge set, and <math>c</math> is the number of conncted components of <math>G</math>.