miniatura|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. Un graf regular amb vèrtexs de grau k s'anomena graf k-regular o graf regular de grau k.
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 eixe 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 és un vector propi d'A. 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.
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).
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 .
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.
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.per a valors ben escollits de k.
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.Vegeu . Amb aquest article, Eugene Luks fou guardonat amb el premi Fulkerson l'any 1985. A es pot trobar una idea de l'algorisme.
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 és fortament regular per a qualsevol .
Notes
Referències
Bibliografia
Enllaços externs
GenReg programari i dades, per Markus Meringer.
Categoria:Famílies de grafs