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 orientado 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  chámase grafo  ou grafo regular de grao .

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

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

 Existencia 
As condicións necesarias e suficientes para un -grafo regular de orde  existir son iso  e iso  é 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  e o grao aquí é . Entón  . Este é o mínimo  para un  en particular. Teña en conta tamén que se algún grafo regular ten orde  entón o número de arestas son  así  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 -regular con  impar ten un número par de vértices.

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

Sexa A a matriz de adxacencia dun grafo. Entón o grafo é regular se e só se  é un vector propio de A.  O seu autovalor será o grao constante do grafo. Os vectores propios correspondentes a outros valores propios son ortogonais , polo que para eses vectores propios , temos .

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 , 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 . Se G non é bipartito, daquela



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


 Véxase tamén 

 Bibliografía 

 Outros artigos 
 Grafo regular aleatorio
 Grafo fortemente regular
 grafo de Moore
 grafo de Cage
 Grafo altamente irregular
 Ligazóns externas 


 GenReg software e datos por Markus Meringer.

Categoría:Teoría de grafos