Цикломати́чне число́ або ко́нтурний ранг — ізоморфна характеристика графів. Для графу L, цикломатичне число λ(L) дорівнює:
- ,
де
- m(L) — кількість ребер,
- n(L) — кількість його вершин,
- — кількість компонент.
Основні властивості цикломатичного числа:
- λ(L) ≥ 0;
- λ(L) = 0 тоді і тільки тоді, коли граф не містить циклів;
- при λ(L) > 0 на L можна видалити λ(L) ребер таким чином, щоб суграф, який залишиться не мав циклів і мав попередню кількість компонент; будь-який суграф, отриманий із L видаленням меншої кількості ребер, містить цикли.
Будь-який суграф T, який задовольняє умови
- ,
- m(T) = m(L) − λ(L),
- λ(T) = 0,
називається каркасом графу L, а видалені ребра хордами L (відносно T). Кожна компонента каркаса є деревом, яке містить всі вершини відповідної компоненти графу L.
Джерела інформації
- Енциклопедія кібернетики, (Зиков О. О.), т. 2, с. 519.
Див. також
- Дерево (теорія графів)
- Граф (математика)
- Цикломатична складність — застосування теорії графів та цикломатичних чисел для оцінки складності програм.
- (Циклічний ранг)
- Коефіцієнт сітчастості
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет