Ciclu | |
---|---|
Vârfurile | n |
coaste | n |
Circumferinţă | n |
Automorfisme | 2n ( Dn ) _ _ |
Număr cromatic | 3 dacă n este impar și 2 dacă par |
Indicele cromatic | 3 dacă n este impar și 2 dacă par |
Spectru | {2 cos(2 k π / n ), k =1, ... , n } [1] |
Proprietăți |
Euler |
Fișiere media la Wikimedia Commons |
În teoria grafurilor, un graf-ciclu este un grafic format dintr-un singur ciclu , sau, cu alte cuvinte, un anumit număr de vârfuri conectate printr-un lanț închis. Un grafic de ciclu cu n vârfuri este notat cu C n . Numărul de vârfuri din C n este egal cu numărul de muchii, iar fiecare vârf are gradul 2 , adică orice vârf este incident cu exact două muchii.
Ciclul grafic are multe sinonime. Sunt folosiți termenii graf ciclic simplu și graf ciclic , deși ultimul termen nu este folosit în mod obișnuit, deoarece se poate referi la grafice care nu sunt aciclice . Termenii ciclu , poligon sau n - gon sunt uneori folosiți . Un ciclu cu un număr par de vârfuri se numește ciclu par , iar cu un număr impar de vârfuri, un ciclu impar .
ciclu grafic:
În plus:
Un grafic de ciclu direcționat este o versiune direcționată a unui grafic de ciclu în care toate arcurile sunt îndreptate în aceeași direcție.
Într -un grafic dirijat , setul de arce care conțin cel puțin un arc din fiecare ciclu direcționat se numește setul de arce de rupere . În mod similar, un set de vârfuri care conține cel puțin un vârf din fiecare ciclu orientat este numit un set de vârfuri de tăiere a ciclului .
Un ciclu de grafic direcționat are un grad constant 1 și un grad exterior constant 1 .
Graficele ciclului direcționat sunt graficele Cayley pentru grupuri ciclice (vezi, de exemplu, Trevisan ) .