Graf regular

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

Una condició necessària i suficient perquè existeixi un graf k-regular d'ordre n és que nk+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 j = ( 1 , , 1 ) {\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 j {\displaystyle {\textbf {j}}} , de manera que, per a aquests vectors propis v = ( v 1 , , v n ) {\displaystyle v=(v_{1},\dots ,v_{n})} , es té

i = 1 n v i = 0 {\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 J i j = 1 {\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 k = λ 0 > λ 1 λ n 1 {\displaystyle k=\lambda _{0}>\lambda _{1}\geq \cdots \geq \lambda _{n-1}} . Si G no és bipartit, llavors

D log ( n 1 ) log ( λ 0 / λ 1 ) + 1 {\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 0-regular
  • Graf 1-regular
    Graf 1-regular
  • Graf 2-regular
    Graf 2-regular
  • Graf 3-regular
    Graf 3-regular
  • Graf de Petersen (graf cúbic particular)
    Graf de Petersen (graf cúbic particular)
  • Graf 2-regular infinit
    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 K m {\displaystyle K_{m}} és fortament regular per a qualsevol m {\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. 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. 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.