![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Нехай 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. Двокомпонентний граф з кількістю циклів,
що дорівнює трьом
Дата публикования: 2014-11-18; Прочитано: 2250 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!