Graficul ciclului
În teoria graficelor , un grafic ciclu sau grafic circular este un grafic format dintr-un singur ciclu sau, cu alte cuvinte, un număr de vârfuri conectate într-un lanț închis. Graficul ciclului cu n vârfuri se numește C n . Numărul de vârfuri din C n este egal cu numărul de muchii și fiecare vârf are gradul 2; adică fiecare vârf are exact două margini incidente cu el.
Terminologie
Există multe sinonime pentru „ciclu grafic”. Acestea includ grafic ciclu simplu și grafic ciclic , deși al doilea termen este folosit mai rar, deoarece se poate referi la grafice care pur și simplu nu sunt aciclice . Dintre teoreticienii graficului, ciclul , poligonul sau n- gon sunt, de asemenea, adesea folosite. Un ciclu cu un număr par de vârfuri se numește ciclu par; un ciclu cu un număr impar de vârfuri se numește ciclu impar .
Proprietate
Un grafic de ciclu este:
- Conectat
- 2-regulat
- Eulerian
- Hamiltoniană
- 2-colorable pe vârfuri , dacă și numai dacă are un număr par de vârfuri. Mai general, un grafic este bipartit dacă și numai dacă are un număr impar de cicluri ( Kőnig , 1936)
- 2-colorabile pe margini , dacă și numai dacă are un număr par de vârfuri
- 3-colorabile pe vârfuri și 3-colorable pe margini, pentru orice număr de vârfuri
- Un grafic al distanței unitare
În plus:
- Deoarece graficele ciclului pot fi desenate ca poligoane regulate , simetriile unui ciclu n sunt aceleași cu cele ale unui poligon regulat cu n laturi, grupul diedru de ordinul 2 n . În special, există simetrii care conduc orice vârf către orice alt vârf și orice margine către orice altă margine, astfel încât ciclul n este un grafic simetric .
Grafic cu ciclu direct
Un grafic cu ciclu direct este o versiune directă a unui grafic cu ciclu, cu toate muchiile orientate în aceeași direcție.
Într-un grafic direct , un set de margini care conține cel puțin o margine (sau arc ) din fiecare ciclu direct se numește un set de margini de feedback . În mod similar, un set de vârfuri care conțin cel puțin un vârf al fiecărui ciclu înainte se numește un set de vârfuri de feedback .
Un grafic cu ciclu direct are un grad uniform de intrare 1 și un grad uniform de ieșire 1.
Graficele cu ciclu direct sunt grafice Cayley pentru grupuri ciclice (a se vedea, de exemplu, Trevisan).
Notă
Elemente conexe
Alte proiecte
-
Wikimedia Commons conține imagini sau alte fișiere pe grafice
linkuri externe
- (EN) Eric W. Weisstein, Cycle Graph , în MathWorld Wolfram Research. (discutarea ambelor grafice cu 2 cicluri regulate și a conceptului de teorie de grup a diagramelor ciclului )
- ( EN ) Luca Trevisan , Personaje și expansiune .
