Graf regular

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.

El graf de Petersen és un graf regular de grau 3

Existència

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

Sigui A la matriu d'adjacència d'un graf. Aleshores el graf és regular si i només si ${\displaystyle {\textbf {j}}=(1,\dots ,1)}$ é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 ${\displaystyle {\textbf {j}}}$, de manera que, per a aquests vectors propis ${\displaystyle v=(v_{1},\dots ,v_{n})}$, es té

${\displaystyle \sum _{i=1}^{n}v_{i}=0}$.

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 ${\displaystyle J_{ij}=1}$, 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 ${\displaystyle k=\lambda _{0}>\lambda _{1}\geq \cdots \geq \lambda _{n-1}}$. Si G no és bipartit, llavors

${\displaystyle D\leq {\frac {\log {(n-1)}}{\log(\lambda _{0}/\lambda _{1})}}+1}$.^[5]

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

Classificació

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.

• 
  Graf 0-regular
• 
  Graf 1-regular
• 
  Graf 2-regular
• 
  Graf 3-regular
• 
  Graf de Petersen (graf cúbic particular)
• 
  Graf 2-regular infinit

Consideracions algorísmiques

Optimització combinatòria

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ó

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

Grafs fortament regulars

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 ${\displaystyle K_{m}}$ és fortament regular per a qualsevol ${\displaystyle m}$.

Notes

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

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. 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), 01-05-1992. Arxivat de l'original el 2014-01-06. [Consulta: 17 juny 2016].
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

• 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

• Weisstein, Eric W., «Regular Graph» a MathWorld (en anglès).
• Weisstein, Eric W., «Strongly Regular Graph» a MathWorld (en anglès).
• GenReg programari i dades, per Markus Meringer.