Cyklomatické číslo grafu
(Presmerované z Cyklomatické číslo)
Cyklomatické číslo grafu je minimálny počet hrán, po ktorých odstránení nebude v grafe žiadna kružnica.
Cyklomatické číslo C(G) značí počet nezávislých kružníc v grafe. Ak je , potom graf neobsahuje kružnice.
Pre každý graf existuje cyklomatické číslo grafu, pre ktoré platí:
C(G) = |E| − |V| + p
kde E je množina všetkých hrán, V je množina všetkých vrcholov a p je počet komponentov grafu.
Špeciálnym prípadom je strom. Z definície vyplýva, že strom neobsahuje kružnicu, teda .
|
Tento článok týkajúci sa matematiky je zatiaľ „výhonok“. Pomôž Wikipédii tým, že ho doplníš a rozšíriš. |
Literatúra upraviť
- Znám, Š: Kombinatorika a teória grafov. Bratislava, Matematicko-fyzikálna fakulta Univerzity Komenského. 1982, s. 41-44