Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

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



Нехай 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; Прочитано: 2222 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.009 с)...