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