Cyclomatic number

The cyclomatic number is a term from the mathematical branch of graph theory .

definition

Be a graph . The number of basic elements of a cycle base , i.e. the dimension of the cycle space of, is called the cyclomatic number. It is also called the index of the graph. ${\displaystyle G}$ ${\displaystyle G}$

properties

• The index is never negative and disappears if and only if the graph is a forest .
• The index is never greater than the number of cycles of the graph and is exactly equal to this number if it is a cactus graph .
• The cyclomatic number can be given by the formula

${\displaystyle \mu (G):=|E(G)|-|V(G)|+\kappa (G)}$

are calculated, thereby designates the number of edges (engl. e DGES ), the number of nodes (engl. v ertices ) and the number of connected components of the graph. ${\displaystyle |E(G)|}$ ${\displaystyle |V(G)|}$ ${\displaystyle \kappa (G)}$

Individual evidence

1. ^ Peter Tittmann: Graph theory . Specialist book publ. Leipzig im Carl-Hanser-Verl., Munich 2003, ISBN 3-446-22343-6 , p. 134 .
2. ^ Reinhard Diestel: Graph theory . Springer, Berlin 2010, ISBN 978-3-642-14278-9 , pp. 23 .
3. ^ Peter Tittmann: Graph theory . Specialist book publ. Leipzig im Carl-Hanser-Verl., Munich 2003, ISBN 3-446-22343-6 , p. 136 .