Graf regular

De Viquipèdia
Jump to navigation Jump to search
El graf de Petersen és un graf regular de grau 3

En teoria de grafs, un graf regular és un graf on cada vèrtex té el mateix nombre de veïns; és a dir, tots els vèrtexs tenen el mateix grau o valència. Un graf dirigit regular ha de satisfer la condició addicional que el grau d'entrada i el grau de sortida de tots els vèrtexs han de ser iguals.[1] Un graf regular amb vèrtexs de grau k s'anomena graf k-regular o graf regular de grau k.

Existència[modifica]

Una condició necessària i suficient perquè existeixi un graf k-regular d'ordre n és que n ≥ k+1 i que nk sigui parell.[2] En tal cas, resulta senzill construir grafs regulars a partir d'una elecció adequada dels paràmetres d'un graf circulant.

Propietats algebraiques[modifica]

Sigui A la matriu d'adjacència d'un graf. Aleshores el graf és regular si i només si és un vector propi de A.[3] El seu valor propi és el grau constant del graf. Els vectors propis corresponents a altres valors propis són ortogonals a , de manera que, per a aquests vectors propis , es té

.

Un graf regular de grau k és connex si i només si el valor propi k té multiplicitat 1. La implicació en sentit directe és una conseqüència del teorema de Perron-Frobenius.[3]

També existeix un criteri per a grafs regulars i connexos: un graf és connex i regular si i només si la matriu d'uns J, amb , està en l'àlgebra d'adjacència del graf (és a dir, si i només si és una combinació lineal de potències de A).[4]

Sigui G un graf k-regular amb diàmetre D, i escrivim els valors propis de la seva matriu d'adjacència com . Si G no és bipartit, llavors

.[5]

Un teorema de Nash-Williams afirma que tot graf k-regular de 2k + 1 vèrtexs té un cicle hamiltonià.[6][7]

Classificació[modifica]

Els grafs regulars de grau fins a 2 són fàcils de classificar: un graf 0-regular consisteix d'un conjunt de vèrtexs desconnectats; un graf 1-regular consisteix d'un conjunt d'arestes desconnectades, i un graf 2-regular pot estar format per cicles desconnectats i cadenes infinites.

Un graf 3-regular es coneix amb el nom de graf cúbic.

Consideracions algorísmiques[modifica]

Optimització combinatòria[modifica]

Alguns problemes sobre grafs són difícils inclús si hom es restringeix a la classe dels grafs regulars. En concret, la coloració, el problema del viatjant de comerç i el problema del conjunt independent maximal són NP-complets per als grafs regulars i fins i tot per als grafs k-regulars amb k fixat.[8]

En canvi, el problema d'isomorfisme de grafs és decidible en temps polinòmic per als grafs de grau fitat, com per exemple els grafs regulars.[nota 1]

Generació[modifica]

Es poden generar grafs regulars amb el programari GenReg.[9]

Grafs fortament regulars[modifica]

Un graf fortament regular és un graf regular on tot parell adjacent de vèrtexs té el mateix nombre λ de veïns en comú, i tot parell de vèrtexs no adjacents té el mateix nombre μ de veïns en comú. Els grafs més petits que són regulars però no fortament regulars són el graf cicle de 6 vèrtexs i el graf circulant de 6 vèrtexs. El graf complet és fortament regular per a qualsevol .

Notes[modifica]

  1. Vegeu Luks 1982. Amb aquest article, Eugene Luks fou guardonat amb el premi Fulkerson l'any 1985. A Fortin 1996, secció 2.3 es pot trobar una idea de l'algorisme.

Referències[modifica]

  1. Chen, Wai-Kai. Graph Theory and its Engineering Applications. World Scientific, 1997, p. 29. ISBN 978-981-02-1859-1. 
  2. Tomescu, Ioan. Problems in combinatorics and graph theory. Nova York: Wiley, 1985, p. 212-213. ISBN 978-0471801559. 
  3. 3,0 3,1 Cvetković, D. M.; Doob, M.; Sachs, H. Spectra of Graphs: Theory and Applications. 3a edició revisada i ampliada. Nova York: Wiley, 1998. ISBN 978-3527296859. 
  4. Curtin, Brian «Algebraic characterizations of graph regularity conditions». Designs, Codes and Cryptography, 34, 2-3, 2005, pàg. 241–248. DOI: 10.1007/s10623-004-4857-4.
  5. Quenell, Gregory. «Spectral diameter estimates for k-regular graphs» (pdf), maig 1992.
  6. Nash-Williams, Crispin «Valency sequences which force graphs to have Hamiltonian circuits». University of Waterloo Research Report, Waterloo, Ontario, 1969.
  7. Niculae, Vlad. «Nash-Williams theorem on the Hamiltonian property of some regular graphs», 29-01-2012.
  8. per a valors ben escollits de k. «Graphclass: k-regular, fixed k». Graphclasses.org.
  9. Meringer, Markus «Fast generation of regular graphs and construction of cages» (pdf). Journal of Graph Theory, 30, 2, 1999, pàg. 137-146. DOI: 10.1002/(SICI)1097-0118(199902)30:2<>1.0.CO;2-G.

Bibliografia[modifica]

  • Luks, Eugene M. «Isomorphism of graphs of bounded valence can be tested in polynomial time». Journal of Computer and System Sciences, 25, 1982, pàg. 42-65. DOI: 10.1016/0022-0000(82)90009-5.
  • Fortin, Scott «The graph isomorphism problem» (pdf). Technical Report 96-20. Universitat d'Alberta [Edmonton, Alberta, Canadà], 1996.

Enllaços externs[modifica]

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Graf regular Modifica l'enllaç a Wikidata