Цикломатичне число — Вікіпедія

Цикломати́чне число́ або ко́нтурний ранг — ізоморфна характеристика графів. Для графу 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.

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

[ред. | ред. код]

Див. також

[ред. | ред. код]