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

## 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 ${\textbf {j}}=(1,\dots ,1)$ é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 ${\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$.

## Notes

* ↑ 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

* ↑ Chen, Wai-Kai. Graph Theory and its Engineering Applications. World Scientific, 1997, p. 29. ISBN 978-981-02-1859-1.
* ↑ Tomescu, Ioan. Problems in combinatorics and graph theory. Nova York: Wiley, 1985, p. 212-213. ISBN 978-0471801559.
* 1 2 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.
* ↑ 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.
* ↑ 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].
* ↑ Nash-Williams, Crispin «Valency sequences which force graphs to have Hamiltonian circuits». University of Waterloo Research Report, Waterloo, Ontario, 1969.
* ↑ Niculae, Vlad. «Nash-Williams theorem on the Hamiltonian property of some regular graphs», 29-01-2012.
* ↑ per a valors ben escollits de k. «Graphclass: k-regular, fixed k». Graphclasses.org.
* ↑ 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.