gráfico regular

Grafica donde cada vértice tiene el mismo número de vecinos

En teoría de grafos , una gráfica regular es una gráfica donde cada vértice tiene el mismo número de vecinos; es decir, cada vértice tiene el mismo grado o valencia. Un gráfico dirigido regular también debe satisfacer la condición más estricta de que los grados de entrada y salida de cada vértice interno sean iguales entre sí. ^[1] Un gráfico regular con vértices de grado k se llama k -gráfico regular o gráfico regular de grado k . Además, según el lema del protocolo de enlace , un gráfico regular contiene un número par de vértices con grado impar.

Casos especiales

Los gráficos regulares de grado 2 como máximo son fáciles de clasificar: un gráfico regular 0 consta de vértices desconectados, un gráfico regular 1 consta de aristas desconectadas y un gráfico regular 2 consta de una unión disjunta de ciclos y cadenas infinitas.

Una gráfica de 3 regulares se conoce como gráfica cúbica .

Un grafo fuertemente regular es un grafo 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 muy regulares son el gráfico de ciclo y el gráfico circulante en 6 vértices.

La gráfica completa K _m es fuertemente regular para cualquier m .

• 
  0-gráfico regular
• 
  1-gráfico regular
• 
  2-gráfico regular
• 
  gráfico de 3 regulares

Existencia

Las condiciones necesarias y suficientes para que exista un grafo regular de orden son que y que sea par. ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle n\geq k+1}$ ${\displaystyle nk}$

Prueba: un gráfico completo tiene cada par de vértices distintos conectados entre sí por una arista única. Entonces, las aristas son máximas en el gráfico completo y el número de aristas es el grado aquí . Entonces . Este es el mínimo para un particular . También tenga en cuenta que si cualquier gráfico regular tiene orden , entonces el número de aristas debe ser par . En tal caso, es fácil construir gráficos regulares considerando parámetros apropiados para los gráficos circulantes . ${\displaystyle {\binom {n}{2}}={\dfrac {n(n-1)}{2}}}$ ${\displaystyle n-1}$ ${\displaystyle k=n-1,n=k+1}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle {\dfrac {nk}{2}}}$ ${\displaystyle nk}$

Propiedades

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

Sea A la matriz de adyacencia de un gráfico. Entonces la gráfica es regular si y sólo si es un vector propio de A. ^[2] Su valor propio será el grado constante del gráfico. Los vectores propios correspondientes a otros valores propios son ortogonales a , por lo que para dichos vectores propios tenemos . ${\displaystyle {\textbf {j}}=(1,\dots ,1)}$ ${\displaystyle {\textbf {j}}}$ ${\displaystyle v=(v_{1},\dots ,v_{n})}$ ${\displaystyle \sum _{i=1}^{n}v_{i}=0}$

Una gráfica regular de grado k es conexa si y sólo si el valor propio k tiene multiplicidad uno. La dirección "sólo si" es una consecuencia del teorema de Perron-Frobenius . ^[2]

También hay un criterio para gráficas regulares y conexas: una gráfica es conexa y regular si y solo si la matriz de unos J , con , está en el álgebra de adyacencia de la gráfica (lo que significa que es una combinación lineal de potencias de A ). ^[3] ${\displaystyle J_{ij}=1}$

Sea G un gráfico k -regular con diámetro D y valores propios de la matriz de adyacencia . Si G no es bipartito, entonces ${\displaystyle k=\lambda _{0}>\lambda _{1}\geq \cdots \geq \lambda _{n-1}}$

${\displaystyle D\leq {\frac {\log {(n-1)}}{\log(\lambda _{0}/\lambda _{1})}}+1.}$^[4]

Generación

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

Ver también

• Gráfico regular aleatorio
• Gráfico fuertemente regular
• gráfico de moore
• Gráfico de jaula
• Gráfico muy irregular

Referencias

1. Chen, Wai Kai (1997). Teoría de grafos y sus aplicaciones en ingeniería . Científico mundial. págs.29. ISBN 978-981-02-1859-1.
2. Cvetković, DM; Doob, M.; y Sachs, H. Espectros de gráficos: teoría y aplicaciones, 3ª rev. enl. ed. Nueva York: Wiley, 1998.
3. Curtin, Brian (2005), "Caracterizaciones algebraicas de condiciones de regularidad de gráficos", Diseños, códigos y criptografía , 34 (2–3): 241–248, doi :10.1007/s10623-004-4857-4, SEÑOR  2128333.
4. [1] ^{[ cita necesaria ]}
5. Meringer, Markus (1999). "Generación rápida de gráficos regulares y construcción de jaulas" (PDF) . Revista de teoría de grafos . 30 (2): 137-146. doi :10.1002/(SICI)1097-0118(199902)30:2<137::AID-JGT7>3.0.CO;2-G.

enlaces externos

• Weisstein, Eric W. "Gráfico regular". MundoMatemático .
• Weisstein, Eric W. "Gráfico muy regular". MundoMatemático .
• Software y datos GenReg de Markus Meringer.
• Nash-Williams, Crispin (1969), Secuencias de valencia que obligan a los gráficos a tener circuitos hamiltonianos , Informe de investigación de la Universidad de Waterloo, Waterloo, Ontario: Universidad de Waterloo