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

Матеріал з Вікіпедії — вільної енциклопедії.

Цикломати́чне число́ — ізоморфна характеристика

\lambda(L) = m(L) - n(L) + \varkappa(L) графу L,

де

  • n(L) — кількість його вершин,
  • m(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.

[ред.] Дивіться також