Цикломатичне число

Нехай G = <X, V>- неорієнтований граф, у якому |X| = n, |V| = m і r – число компонентів зв’язності (тобто зв'язних підграфів графу G).

Визначення. Цикломатичним числом графу називається число n, що дорівнює

n(G) = m –n + r

Цикломатичне число має цікавий фізичний зміст - воно дорівнює найбільшому числу незалежних циклів у графі. При розрахунку електронних ланцюгів цикломатичним числом можна користатися для визначення числа незалежних контурів.

Приклад. Для наведеного на рис. 23.2. двохкомпонентного графу V(G) = 5-4+2 = 3

Рис. 17.2. Двокомпонентний граф з кількістю циклів,
що дорівнює трьом