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

Цикломати́чне число́ або ко́нтурний ранг — ізоморфна характеристика графів. Для графу L, цикломатичне число λ(L) дорівнює:

$\lambda (L)=m(L)-n(L)+\varkappa (L)$,

де

• m(L) — кількість ребер,
• n(L) — кількість його вершин,
• $\varkappa (L)$ — кількість компонент.

Основні властивості цикломатичного числа:

• λ(L) ≥ 0;
• λ(L) = 0 тоді і тільки тоді, коли граф не містить циклів;
• при λ(L) > 0 на L можна видалити λ(L) ребер таким чином, щоб суграф, який залишиться не мав циклів і мав попередню кількість компонент; будь-який суграф, отриманий із L видаленням меншої кількості ребер, містить цикли.

Будь-який суграф T, який задовольняє умови

• $\varkappa (T)=\varkappa (L)$,
• m(T) = m(L) − λ(L),
• λ(T) = 0,

називається каркасом графу L, а видалені ребра хордами L (відносно T). Кожна компонента каркаса є деревом, яке містить всі вершини відповідної компоненти графу L.

Джерела інформації

• Енциклопедія кібернетики, Зиков О. О., т. 2, с. 519.

Див. також

• Дерево (теорія графів)
• Граф (математика)
• Цикломатична складність — застосування теорії графів та цикломатичних чисел для оцінки складності програм.
• Циклічний ранг
• Коефіцієнт сітчастості