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 Modelo:Mvar chámase grafo Modelo:Nowrap ou grafo regular de grao Modelo:Mvar.

Casos especiais

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

Un grafo Modelo:Nowrap 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 Modelo:Mvar de veciños en común, e cada par de vértices non adxacentes ten o mesmo número Modelo:Mvar 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 Modelo:Mvar é fortemente regular para calquera Modelo:Mvar.

• 
  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\ge 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 $(\genfrac{}{}{0ex}{}{n}{2})=\frac{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 $\frac{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 Modelo:Mvar-regular con Modelo:Mvar impar ten un número par de vértices.

Un teorema de Nash-Williams di que todo grafo Modelo:Nowrap en Modelo:Math vértices ten un ciclo hamiltoniano.

Sexa A a matriz de adxacencia dun grafo. Entón o grafo é regular se e só se $\mathbf{\text{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 $\mathbf{\text{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\ge \cdots \ge {\lambda }_{n-1}$. Se G non é bipartito, daquela

$D\le \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

• Modelo:Cita libro

Outros artigos

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

Ligazóns externas

• Modelo:MathWorld
• Modelo:MathWorld
• GenReg software e datos por Markus Meringer.