En teoría de grafos , un grafo regular es un grafo en el que cada vértice tiene el mismo número de vecinos; es decir, cada vértice tiene el mismo grado o valencia. Una gráfica dirigida regular también debe satisfacer la condición más estricta de que el grado y el grado de salida de cada vértice son iguales entre sí. [1] Un gráfico regular con vértices de grado se llama un -Gráfica regular o gráfica regular de grado. Además, a partir del lema de apretón de manos , un gráfico regular contiene vértices de números pares con grados impares.
Familias de gráficos definidas por sus automorfismos | ||||
---|---|---|---|---|
distancia-transitiva | → | distancia regular | ← | muy regular |
↓ | ||||
simétrico (arco-transitivo) | ← | t -transitivo, t ≥ 2 | simétrico sesgado | |
↓ | ||||
(si está conectado) vértice y borde transitivo | → | edge-transititive y regular | → | borde transitivo |
↓ | ↓ | ↓ | ||
vértice-transitivo | → | regular | → | (si es bipartito) birregular |
↑ | ||||
Gráfico de Cayley | ← | simétrico cero | asimétrico |
Las gráficas regulares de grado 2 como máximo son fáciles de clasificar: una gráfica regular 0 consiste en vértices desconectados, una gráfica regular 1 consiste en aristas desconectadas y una gráfica regular 2 consiste en una unión disjunta de ciclos y cadenas infinitas.
Una gráfica de 3 regulares se conoce como gráfica cúbica .
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 muy regulares son el gráfico de ciclo y el gráfico circulante en 6 vértices.
El gráfico completo es muy regular para cualquier .
Un teorema de Nash-Williams dice que cada-Gráfico regular en 2 k + 1 vértices tiene un ciclo hamiltoniano .
0-gráfico regular
1 gráfico regular
2-gráfico regular
Gráfico de 3 regulares
Existencia
Es bien sabido que las condiciones necesarias y suficientes para una gráfico regular de orden existir son que y eso incluso.
Prueba: como sabemos, un gráfico completo tiene cada par de vértices distintos conectados entre sí por un borde único. Entonces, los bordes son máximos en el gráfico completo y el número de bordes es y orden aquí está . Entonces. Este es el mínimo para un particular . También tenga en cuenta que si algún gráfico regular tiene orden entonces el número de aristas es entonces tiene que ser parejo. En tal caso, es fácil construir gráficos regulares considerando los parámetros apropiados para los gráficos circulantes .
Propiedades algebraicas
Sea A la matriz de adyacencia de un gráfico. Entonces la gráfica es regular si y solo si es un vector propio de A . [2] Su valor propio será el grado constante del gráfico. Los autovectores correspondientes a otros autovalores son ortogonales a, entonces para tales autovectores , tenemos .
Una gráfica regular de grado k está conectada si y solo 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áficos regulares y conectados: un gráfico está conectado y es regular si y solo si la matriz de unos J , con, está en el álgebra de adyacencia del gráfico (lo que significa que es una combinación lineal de potencias de A ). [3]
Sea G un k- grafo regular con diámetro D y valores propios de matriz de adyacencia. Si G no es bipartito, entonces
Generacion
Existen algoritmos rápidos para enumerar, 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 muy regular
- Gráfico de Moore
- Gráfico de jaula
- Gráfico muy irregular
Referencias
- ^ Chen, Wai-Kai (1997). Teoría de grafos y sus aplicaciones de ingeniería . World Scientific. pp. 29 . ISBN 978-981-02-1859-1.
- ↑ a b Cvetković, DM; Doob, M .; y Sachs, H. Spectra of Graphs: Theory and Applications, 3ª rev. enl. ed. Nueva York: Wiley, 1998.
- ^ Curtin, Brian (2005), "Caracterizaciones algebraicas de las condiciones de regularidad de grafos", Diseños, códigos y criptografía , 34 (2–3): 241–248, doi : 10.1007 / s10623-004-4857-4 , MR 2128333.
- ^ [1] [ cita requerida ]
- ^ 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" . MathWorld .
- Weisstein, Eric W. "Gráfico fuertemente regular" . MathWorld .
- GENREG software y los datos 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