También podemos llamar a la teoría del apretón de manos teorema de la suma de grados o lema del apretón de manos. La teoría del apretón de manos establece que la suma de grados de todos los vértices de un gráfico será el doble del número de aristas contenidas en ese gráfico. La representación simbólica de la teoría del apretón de manos se describe a continuación:
Aquí,
'd' se utiliza para indicar el grado del vértice.
'v' se utiliza para indicar el vértice.
'e' se utiliza para indicar los bordes.
Teorema del apretón de manos:
Hay algunas conclusiones del teorema del apretón de manos que deben extraerse, que se describen a continuación:
En cualquier gráfico:
- Debe haber números pares para la suma de grados de todos los vértices.
- Si hay grados impares para todos los vértices, entonces la suma de grados de estos vértices siempre debe permanecer par.
- Si hay algunos vértices que tienen un grado impar, entonces el número de estos vértices será par.
Ejemplos de teoría del apretón de manos
Hay varios ejemplos de teoría del apretón de manos, y algunos de los ejemplos se describen a continuación:
Ejemplo 1: Aquí tenemos una gráfica que tiene el grado de cada vértice como 4 y 24 aristas. Ahora averiguaremos el número de vértices en este gráfico.
Solución: Con la ayuda del gráfico anterior, tenemos los siguientes detalles:
Grado de cada vértice = 24
clase vs objeto java
Número de aristas = 24
Ahora asumiremos el número de vértices = n
Con la ayuda del teorema del apretón de manos, tenemos lo siguiente:
Suma de un grado de todos los Vértices = 2 * Número de aristas
Ahora pondremos los valores dados en la fórmula de protocolo de enlace anterior:
n*4 = 2*24
norte = 2*6
norte = 12
Así, en el gráfico G, el número de vértices = 12.
Ejemplo 2: Aquí, tenemos un gráfico que tiene 21 aristas, 3 vértices de grado 4 y todos los demás vértices de grado 2. Ahora averiguaremos el número total de vértices en este gráfico.
Solución: Con la ayuda del gráfico anterior, tenemos los siguientes detalles:
ordenar una lista de matrices en java
Número de vértices de Grado 4 = 3
Número de aristas = 21
Todos los demás vértices tienen grado 2.
Ahora asumiremos el número de vértices = n
Con la ayuda del teorema del apretón de manos, tenemos lo siguiente:
Suma de grados de todos los vértices = 2 * Número de aristas
Ahora pondremos los valores dados en la fórmula de protocolo de enlace anterior:
3*4 + (n-3) * 2 = 2*21
12+2n-6 = 42
2norte = 42 - 6
2norte=36
norte = 18
Así, en el gráfico G, el número total de vértices = 18.
máquina de estados finitos
Ejemplo 3: Aquí tenemos una gráfica que tiene 35 aristas, 4 vértices de grado 5, 5 vértices de grado 4 y 4 vértices de grado 3. Ahora averiguaremos el número de vértices con grado 2 en esta gráfica.
Solución: Con la ayuda del gráfico anterior, tenemos los siguientes detalles:
Número de aristas = 35
Número de vértices de grado 5 = 4
Número de vértices de grado 4 = 5
Número de vértices de grado 3 = 4
Ahora asumiremos el número de vértices de grado 2 = n
Con la ayuda del teorema del apretón de manos, tenemos lo siguiente:
Suma de grados de todos los vértices = 2 * Número de aristas
Ahora pondremos los valores dados en la fórmula de protocolo de enlace anterior:
4*5 + 5*4 + 4*3 + n*2 = 2*35
20 + 20 + 12 + 2norte = 70
52+2norte = 70
2norte = 70-52
2norte = 18
norte = 9
Así, en el gráfico G, número de vértices de grado 2 = 9.
Ejemplo 4: Aquí tenemos una gráfica que tiene 24 aristas y el grado de cada vértice es k. Ahora averiguaremos el número posible de vértices a partir de las opciones dadas.
- 15
- 20
- 8
- 10
Solución: Con la ayuda del gráfico anterior, tenemos los siguientes detalles:
npm limpiar caché
Número de aristas = 24
Grado de cada vértice = k
Ahora asumiremos el número de vértices = n
Con la ayuda del teorema del apretón de manos, tenemos lo siguiente:
Suma de grados de todos los vértices = 2 * Número de aristas
Ahora pondremos los valores dados en la fórmula de protocolo de enlace anterior:
N*k = 2*24
K = 48/aprox.
Es obligatorio que un número entero esté contenido en el grado de cualquier vértice.
Entonces podemos usar solo aquellos tipos de valores de n en la ecuación anterior que nos proporcionan un valor completo de k.
Ahora, verificaremos las opciones dadas anteriormente colocándolas en el lugar de n una por una de esta manera:
- Para n = 15, obtendremos k = 3,2, que no es un número entero.
- Para n = 20, obtendremos k = 2,4, que no es un número entero.
- Para n = 8, obtendremos k = 6, que es un número entero y está permitido.
- Para n = 10, obtendremos k = 4,8, que no es un número entero.
Por tanto, la opción correcta es la opción C.