Grafo regular

En teoría de grafos, un grafo regular é un grafo onde cada vértice ten o mesmo número de veciños; é dicir, cada vértice ten o mesmo grao ou valencia. Un grafo regular dirixido tamén debe satisfacer a condición máis forte de que o grao interior e o grao exterior de cada vértice interno sexan iguais entre si. Un grafo regular con vértices de grao k chámase grafo k‑regular ou grafo regular de grao k.

Casos especiais

Os grafos regulares de grao 2 como máximo, son fáciles de clasificar: un grafo 0-regular consta de vértices desligados, un grafo 1-regular consta de arestas desligadas e un grafo 2-regular consiste nunha unión disxunta de ciclos e cadeas infinitas.

Un grafo 3-regular coñécese como grafo cúbico.

Un grafo fortemente regular é un grafo regular onde cada par de vértices adxacentes ten o mesmo número l de veciños en común, e cada par de vértices non adxacentes ten o mesmo número n de veciños en común. Os grafos máis pequenos que son regulares pero non fortemente regulares son o grafo cíclico e o grafo circulante en 6 vértices.

A grafo completo K_m é fortemente regular para calquera m.

• 
  0-grafo regular
• 
  1-grafo regular
• 
  2-grafo regular
• 
  3-grafo regular

Existencia

As condicións necesarias e suficientes para un $k$-grafo regular de orde $n$ existir son iso $n\geq k+1$ e iso $nk$ é par.

Proba: un grafo completo ten cada par de vértices distintos ligados entre si por unha única aresta. Polo tanto, as arestas son máximas no grafo completo e o número de arestas son ${\binom {n}{2}}={\dfrac {n(n-1)}{2}}$ e o grao aquí é $n-1$. Entón $k=n-1,n=k+1$ . Este é o mínimo $n$ para un $k$ en particular. Teña en conta tamén que se algún grafo regular ten orde $n$ entón o número de arestas son ${\dfrac {nk}{2}}$ así $nk$ ten que ser par. Neste caso, é doado construír grafos regulares tendo en conta os parámetros apropiados para os grafos circulantes.

Propiedades

A partir do lema do apertón de mans, un grafo k-regular con k impar ten un número par de vértices.

Un teorema de Nash-Williams di que todo grafo k‑regular en 2k + 1 vértices ten un ciclo hamiltoniano.

Sexa A a matriz de adxacencia dun grafo. Entón o grafo é regular se e só se ${\textbf {j}}=(1,\dots ,1)$ é un vector propio de A. O seu autovalor será o grao constante do grafo. Os vectores propios correspondentes a outros valores propios son ortogonais ${\textbf {j}}$, polo que para eses vectores propios $v=(v_{1},\dots ,v_{n})$, temos $\sum _{i=1}^{n}v_{i}=0$.

Un grafo regular de grao k está conectado se e só se o autovalor k ten multiplicidade un. A dirección "só se" é unha consecuencia do teorema de Perron-Frobenius.

Tamén hai un criterio para os grafos regulares e conectados: un grafo é conexo e regular se e só se a matriz de uns J, con $J_{ij}=1$, está na álxebra de adxacencia do grafo (o que significa que é unha combinación linear de potencias de A).

Sexa G un grafo k-regular con diámetro D e valores propios da matriz de adxacencia $k=\lambda _{0}>\lambda _{1}\geq \cdots \geq \lambda _{n-1}$. Se G non é bipartito, daquela

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

Xeración

Existen algoritmos rápidos para xerar, ata isomorfismo, todos os grafos regulares cun grao e número de vértices dados.

Véxase tamén

Bibliografía

• Nash-Williams, Crispin (1969). Valency Sequences which force graphs to have Hamiltonian Circuits. University of Waterloo Research Report. Waterloo, Ontario: University of Waterloo. 

Outros artigos

• Grafo regular aleatorio
• Grafo fortemente regular
• grafo de Moore
• grafo de Cage
• Grafo altamente irregular

Ligazóns externas

• Weisstein, Eric W. "Regular Graph". MathWorld. 
• Weisstein, Eric W. "Strongly Regular Graph". MathWorld. 
• GenReg software e datos por Markus Meringer.