Gráfico regular

En teoría de grafos, un grafo regular es un grafo donde cada vértice tiene el mismo número de vecinos; es decir, todos los vértices tienen el mismo grado o valencia. Un gráfico dirigido regular también debe satisfacer la condición más estricta de que el grado de entrada y el de salida de cada vértice interno son iguales entre sí. Un gráfico regular con vértices de grado k se denomina k‑regular graph o gráfico regular de grado k. Además, del lema del apretón de manos, un gráfico regular contiene un número par de vértices con grado impar.

Los gráficos regulares de grado máximo 2 son fáciles de clasificar: un gráfico 0-regular consta de vértices desconectados, un 1-regular< El gráfico /span> consiste en bordes desconectados, y un gráfico 2-regular consiste en una unión disjunta de ciclos y cadenas infinitas.

Un gráfico 3-regulares se conoce como gráfico cúbico.

Un gráfico fuertemente regular es un gráfico regular donde cada par de vértices adyacentes tiene el mismo número l de vecinos en común, y cada par de vértices no adyacentes tiene el mismo número n de vecinos en común. Los gráficos más pequeños que son regulares pero no fuertemente regulares son el gráfico de ciclo y el gráfico circulante en 6 vértices.

El gráfico completo K_m es muy regular para cualquier m.

Un teorema de Nash-Williams dice que cada k‑regular el gráfico en 2k + 1 vértices tiene un ciclo hamiltoniano.

• 

  Gráfico 0-regular

• 

  Gráfico 1

• 

  Gráfico 2-regular

• 

  Gráfico 3-regular

Existencia

Es bien sabido que las condiciones necesarias y suficientes para un ${displaystyle k}$ gráfico regular de orden ${displaystyle n}$ existir es que ${displaystyle ngeq k+1}$ y eso ${displaystyle nk}$ es incluso.

Prueba: Como sabemos un gráfico completo tiene cada par de vértices distintos conectados entre sí por un borde único. Así que los bordes son máximos en gráficos completos y el número de bordes son ${displaystyle {binom} {n}{2}={dfrac {n-1)}{2}} {cH00} {cH00} {cH00}$ y grado aquí es ${displaystyle n-1}$. Así que... ${displaystyle k=n-1,n=k+1}$. Este es el mínimo ${displaystyle n}$ para un particular ${displaystyle k}$. También tenga en cuenta que si algún gráfico regular tiene orden ${displaystyle n}$ entonces el número de bordes son ${displaystyle {dfrac {nk}{2}}$ Así que... ${displaystyle nk}$ tiene que ser uniforme. En tal caso es fácil construir gráficos regulares considerando parámetros apropiados para gráficos circulantes.

Propiedades algebraicas

Vamos A ser la matriz adyacencia de un gráfico. Entonces el gráfico es regular si y sólo si ${displaystyle {textbf {j}=(1,dots1)}$ es un eigenvector de A. Su eigenvalue será el grado constante del gráfico. Eigenvectores correspondientes a otros eigenvalues son ortogonales a ${displaystyle {textbf}}$, así para tales eigenvectores ${displaystyle v=(v_{1},dotsv_{n}}$, tenemos ${displaystyle sum _{i=1}{n}v_{i}=0}$.

Un gráfico regular de grado k es conexo si y solo si el valor propio k tiene multiplicidad uno. El "solo si" dirección es una consecuencia del teorema de Perron-Frobenius.

También hay un criterio para gráficos regulares y conectados: un gráfico está conectado y regular si y sólo si la matriz de los J, con ${displaystyle J_{ij}=1}$, está en el álgebra adyacency del gráfico (que significa que es una combinación lineal de poderes de A).

Vamos G ser un k- Gráfico regular con diámetro D y eigenvalues de la matriz de adyacencia ${displaystyle k=lambda _{0}lambda _{1}geq cdots geq lambda ¿Qué?$. Si G no es bipartita, entonces

${displaystyle ¿Qué? _{0}/lambda - Sí.$

Generación

Existen algoritmos rápidos para enumerar, hasta el isomorfismo, todos los gráficos regulares con un grado y número de vértices determinados.