Graf cicle

Un graf cicle de longitud 6

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 C_n. El nombre de vèrtexs de C_n és igual al nombre d'arestes, i tot vèrtex té grau 2; é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.
• 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. 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, l'n-cicle és un graf simètric.

Graf cicle dirigit

Un graf cicle dirigit de longitud 8

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, amb

$G={\frac {\mathbb {Z} }{n{\mathbb {Z} }}}$ i $S=\{1,n-1\}$.

Vegeu també

• Graf bipartit complet
• Graf complet
• Graf nul
• Camí (teoria de grafs)