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

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

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

де

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

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

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

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

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

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