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 .
Ficheiro:0-regular_graph.svg|alt=0-regular graph| 0-grafo regular
Ficheiro:1-regular_graph.svg|alt=1-regular graph| 1-grafo regular
Ficheiro:2-regular_graph.svg|alt=2-regular graph| 2-grafo regular
Ficheiro:3-regular_graph.svg|alt=3-regular graph| 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 -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 \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. 
## 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.