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[modifica]
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[modifica]
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, l'n-cicle és un graf simètric.
Graf cicle dirigit[modifica]
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 .
Referències[modifica]
- ↑ Weisstein, Eric W., «Cycle Graph» a MathWorld (en anglès).
- ↑ Asratian, Armen S.; Denley, Tristan M. J.; Häggkvist, Roland. «Theorem 2.1.3». A: Bipartite Graphs and their Applications. 131. Cambridge University Press, 1998, p. 8 (Cambridge Tracts in Mathematics). ISBN 9780521593458. «(anglès) During the course of this book we shall meet several characterisations of bipartite graphs, but let us begin with one of the most widely used, which was obtained by Kőnig (1916)»
- ↑ Rosen, Kenneth H.; Michaels, John G. «8.10.2. Graph automorphisms». A: Handbook of Discrete and Combinatorial Mathematics (pdf). CRC Press, 2000, p. 622. ISBN 0-8493-0149-1. Arxivat 2017-10-13 a Wayback Machine.
- ↑ Trevisan, Luca. «in theory: Characters and Expansion», 21-12-2006. [Consulta: 16 juny 2016].
Vegeu també[modifica]
 |
A Wikimedia Commons hi ha contingut multimèdia relatiu a: Graf cicle |