Cyklomatické číslo (graf)

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
Minimální kostra grafu a šedé hrany jsou tětivy.

Cyklomatické číslo grafu je minimální počet hran takový, že po jejich odstranění nebude v grafu žádný cyklus. Cyklomatické číslo C(G) značí počet nezávislých kružnic v grafu. Pokud C(G) = 0, tak graf neobsahuje kružnice. Obecně pro každý graf existuje cyklomatické číslo, pro které platí: C(G) = E – N + P

Cyklomatické číslo je také rovno počtu tětiv. Tětivy jsou ty hrany, které zbudou potom, co se odebere minimální kostra grafu.