Gráfico regular en teoría de grafos

Prerrequisito: Conceptos básicos de teoría de grafos – Conjunto 1 , Conjunto 2

Gráfico regular:
Un gráfico se llama gráfico regular si el grado de cada vértice es igual. Una gráfica se llama K regular si el grado de cada vértice en la gráfica es K.

Ejemplo:
Considere el siguiente gráfico:

El grado de cada vértice de este gráfico es 2. Entonces, el gráfico es 2 Regular . De manera similar, los gráficos a continuación son 3 Regulares y 4 Regulares respectivamente.

Propiedades de los gráficos regulares:

1. Un grafo completo de N vértices es (N-1) regular.
   Prueba :
   en un gráfico completo de N vértices, cada vértice está conectado a todos los (N-1) vértices restantes. Entonces, el grado de cada vértice es (N-1). Entonces el gráfico es (N-1) Regular.
2. Para un gráfico K Regular, si K es impar, entonces el número de vértices del gráfico debe ser par.
   Prueba :
   Supongamos, número de vértices, N es impar.
   Del Teorema del apretón de manos sabemos,
   Suma del grado de todos los vértices = 2 * Número de aristas del gráfico …….(1)
   El RHS de la ecuación (1) es un número par.

   Para un gráfico regular K, cada vértice es de grado K. La suma de los grados de todos los vértices = K * N, donde tanto K como N son impares. Por lo tanto, su producto (la suma de los grados de todos los vértices) debe ser impar. Esto hace que LHS de la ecuación (1) sea un número impar. Así que LHS no es igual a RHS Así que nuestra suposición inicial de que N es impar era incorrecta. Entonces, el número de vértices (N) debe ser par.

3. Cycle(C _n ) es siempre 2 Regular.
   Prueba :
   En Cycle (C _n ) cada vértice tiene dos vecinos. Entonces, son 2 Regulares.
4. 2 Grafos regulares consisten en Unión Disjunta de ciclos y Strings Infinitas .

   

5. Número de aristas de un gráfico K Regular con N vértices = (N*K)/2.
   Prueba :
   Sea E el número de aristas de un gráfico regular K con N vértices.
   Del teorema del apretón de manos sabemos,

   Suma de grado de todos los vértices = 2 * E
   N * K = 2 * E
   o, E = (N*K)/2

6. Un Hipercubo K-dimensional (Q _k ) es un gráfico K Regular.
   A continuación se muestra un hipercubo tridimensional (Q ₃ ) que es un gráfico regular de 3.