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. 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. 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 ${\textbf {j}}=(1,\dots ,1)$ és un vector propi de A. El seu valor propi és el grau constant del graf. Els vectors propis corresponents a altres valors propis són ortogonals a ${\textbf {j}}$, de manera que, per a aquests vectors propis $v=(v_{1},\dots ,v_{n})$, es té

$\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.

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 $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).

Sigui G un graf k-regular amb diàmetre D, i escrivim els valors propis de la seva matriu d'adjacència com $k=\lambda _{0}>\lambda _{1}\geq \cdots \geq \lambda _{n-1}$. Si G no és bipartit, llavors

$D\leq {\frac {\log {(n-1)}}{\log(\lambda _{0}/\lambda _{1})}}+1$.

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

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.

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.

Generació

Es poden generar grafs regulars amb el programari GenReg.

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

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

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Graf regular

• 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.