| Cyklus | |
|---|---|
| Vrcholy | n |
| žebra | n |
| obvod | n |
| Automorfismy | 2n ( Dn ) _ _ |
| Chromatické číslo | 3 je-li n liché a 2 je-li sudé |
| Chromatický index | 3 je-li n liché a 2 je-li sudé |
| Spektrum | {2 cos(2 k π / n ), k =1, ... , n } [1] |
| Vlastnosti |
2-pravidelný
Euler |
| Mediální soubory na Wikimedia Commons | |
V teorii grafů je graf-cyklus graf skládající se z jediného cyklu nebo jinými slovy z určitého počtu vrcholů spojených uzavřeným řetězcem. Cyklický graf s n vrcholy je označen jako C n . Počet vrcholů v C n se rovná počtu hran a každý vrchol má stupeň 2 , to znamená, že každý vrchol je incidentní právě se dvěma hranami.
Graf-cyklus má mnoho synonym. Používají se termíny jednoduchý cyklický graf a cyklický graf , ačkoli druhý termín se běžně nepoužívá, protože může odkazovat na grafy, které nejsou acyklické . Někdy se používají termíny cyklus , mnohoúhelník nebo n - úhelník . Cyklus se sudým počtem vrcholů se nazývá sudý cyklus a s lichým počtem vrcholů lichý cyklus .
cyklus grafů:
Kromě toho:
Orientovaný graf cyklu je orientovaná verze grafu cyklu, ve kterém všechny oblouky směřují stejným směrem.
V orientovaném grafu se množina oblouků, které obsahují alespoň jeden oblouk z každého orientovaného cyklu, nazývá trhací množina oblouků . Podobně množina vrcholů obsahující alespoň jeden vrchol z každého orientovaného cyklu se nazývá množina vrcholů pro řezání cyklů .
Cyklus orientovaného grafu má konstantní stupeň 1 a konstantní přesah 1 .
Grafy řízeného cyklu jsou Cayleyovy grafy pro cyklické skupiny (viz například Trevisan ) .