Graf cicle
En teoria de grafs, un graf cicle o graf cíclic és un graf que consisteix d'un conjunt de vèrtexs connectats mitjançant una cadena tancada. El graf cicle es denota per Cn. El nombre de vèrtexs de Cn és igual al nombre d'arestes, i tot vèrtex té grau 2;[1] és a dir, tot vèrtex té exactament dues arestes que hi són adjacents.
Terminologia
Existeixen molts sinònims per a "graf cicle"; entre ells, graf cicle simple i graf cíclic, encara que aquest últim terme és menys utilitzat, perquè també pot referir-se als grafs que no són acíclics. Entre els estudiosos de la teoria de grafs també s'utilitzen cicle, polígon o n-cicle. Hom diu que un cicle amb un nombre parell de vèrtexs és un cicle parell, i un cicle amb un nombre senar de vèrtexs s'anomena cicle senar.
Propietats
Un graf cicle és:
- 2-aresta acolorible si i només si té un nombre parell de vèrtexs.
- 2-regular.
- 2-vèrtex acolorible si i només si té un nombre parell de vèrtexs. En general, un graf és bipartit si i només si no té cicles senars.[2]
- connex.
- eulerià.
- hamiltonià.
- un graf distància unitat.
Addicionalment, com que els grafs cicle es poden dibuixar com a polígons regulars, les simetries d'un n-cicle són les mateixes que les d'un polígon regular amb n costats, el grup diedral d'ordre 2n.[3] En particular, existeixen simetries que porten un vèrtex qualsevol a un altre vèrtex qualsevol, i una aresta qualsevol a una altra aresta qualsevol; per tant, lPlantilla:'n-cicle és un graf simètric.
Graf cicle dirigit
Un graf cicle dirigit és una versió dirigida d'un graf cicle, amb totes les arestes orientades en el mateix sentit.
Un graf cicle dirigit té grau d'entrada uniforme igual a 1 i grau de sortida uniforme igual a 1.
Els grafs cicle dirigits són grafs de Cayley per als grafs cíclics,[4] amb
- i .