Graf cyklu

Graf cyklu o délce 6.

V teorii grafů je cyklický graf grafem, který se skládá z jediného cyklu, nebo jinými slovy z určitého počtu vrcholů spojených do uzavřeného řetězce. Cyklus grafu s vrcholy se nazývá . Počet vrcholů v a se rovná počtu hran a každý vrchol má stupeň dva, to znamená, že každý vrchol má přesně dvě hrany, které s ním incidentují.

Existuje mnoho synonym pro výraz „cyklogram“. Patří mezi ně jednoduchý cyklický graf a cyklický graf, ačkoli se zdá, že druhý z těchto termínů je častěji používán teoretiky, kteří se nezabývají teorií grafů. Mezi teoretiky grafů se také často používají pojmy cyklus, polygon nebo n-gon. Přesněji řečeno, cyklus se sudým počtem vrcholů se nazývá sudý cyklus, cyklus s lichým počtem vrcholů se nazývá lichý cyklus.

Směrovaný cyklický graf délky 8.

Směrovaný cyklický graf je směrovaná verze cyklického grafu, kde jsou všechny hrany orientovány stejným směrem.

V orientovaném grafu se množina hran, která obsahuje alespoň jednu hranu (nebo oblouk) z každého orientovaného cyklu, nazývá množina zpětnovazebních oblouků. Podobně se množina vrcholů, která obsahuje alespoň jeden vrchol z každého směrovaného cyklu, nazývá množina vrcholů se zpětnou vazbou.

Přes libovolné dva vrcholy silně propojené komponenty vede směrovaný cyklus.

Doporučujeme:  Purkyňovy buňky