Цикломатичне число
Матеріал з Вікіпедії — вільної енциклопедії.
Цикломати́чне число́ — ізоморфна характеристика
графу L,
де
- n(L) — кількість його вершин,
- m(L) — кількість ребер,
кількість компонент.
Основні властивості цикломатичного числа:
- λ(L) ≥ 0;
- λ(L) = 0 тоді і тільки тоді, коли граф не містить циклів;
- при λ(L) > 0 на L можна видалити λ(L) ребер таким чином, щоб суграф, який залишиться не мав циклів і мав попередню кількість компонент; будь який суграф, отриманий із L шляхом видалення меншої кількості ребер, містить цикли.
Будь який суграф T, який задовольняє умовам
,- m(T) = m(L) − λ(L),
- λ(T) = 0,
називається каркасом графу L, а видалені ребра хордами L (відносно T). Кожна компонента каркасу є деревом, яке містить всі вершини відповідної компоненти графу L.
[ред.] Джерела інформації
Енциклопедія кібернетики, Зиков А. А., т. 2, с. 519.

