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

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

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

Джерела інформації[ред. | ред. код]

Див. також[ред. | ред. код]