Nous pouvons également appeler la théorie de la poignée de main le théorème de la somme des degrés ou le lemme de la poignée de main. La théorie de la prise de contact stipule que la somme des degrés de tous les sommets d'un graphe sera le double du nombre d'arêtes contenues par ce graphe. La représentation symbolique de la théorie de la poignée de main est décrite comme suit :
Ici,
'd' est utilisé pour indiquer le degré du sommet.
'v' est utilisé pour indiquer le sommet.
« e » est utilisé pour indiquer les bords.
Théorème de la poignée de main :
Il y a quelques conclusions dans le théorème de la poignée de main, qui doivent être tirées, qui sont décrites comme suit :
Dans n'importe quel graphique :
- Il doit y avoir des nombres pairs pour la somme des degrés de tous les sommets.
- S’il y a des degrés impairs pour tous les sommets, alors la somme des degrés de ces sommets doit toujours rester paire.
- Si certains sommets ont un degré impair, alors le nombre de ces sommets sera pair.
Exemples de théorie de la poignée de main
Il existe divers exemples de théorie de la poignée de main, et certains d'entre eux sont décrits comme suit :
Exemple 1: Ici, nous avons un graphique qui a le degré de chaque sommet comme 4 et 24 arêtes. Nous allons maintenant découvrir le nombre de sommets dans ce graphique.
Solution: À l’aide du graphique ci-dessus, nous avons obtenu les détails suivants :
Degré de chaque sommet = 24
Nombre d'arêtes = 24
Supposons maintenant que le nombre de sommets = n
Avec l’aide du théorème de la poignée de main, nous avons les éléments suivants :
Somme d'un degré de tous les sommets = 2 * Nombre d'arêtes
Nous allons maintenant mettre les valeurs données dans la formule de négociation ci-dessus :
file d'attente et file d'attente prioritaire en Java
n*4 = 2*24
n = 2*6
n = 12
Ainsi, dans le graphe G, le nombre de sommets = 12.
Exemple 2 : Ici, nous avons un graphe qui a 21 arêtes, 3 sommets de degré 4 et tous les autres sommets de degré 2. Nous allons maintenant découvrir le nombre total de sommets dans ce graphe.
Solution: À l’aide du graphique ci-dessus, nous avons obtenu les détails suivants :
Nombre de sommets de degré 4 = 3
Nombre d'arêtes = 21
Tous les autres sommets ont le degré 2
Supposons maintenant que le nombre de sommets = n
Avec l’aide du théorème de la poignée de main, nous avons les éléments suivants :
Somme des degrés de tous les sommets = 2 * Nombre d'arêtes
Nous allons maintenant mettre les valeurs données dans la formule de négociation ci-dessus :
3*4 + (n-3) * 2 = 2*21
12+2n-6 = 42
2n = 42 - 6
2n=36
n = 18
Ainsi, dans le graphe G, le nombre total de sommets = 18.
Exemple 3 : Ici, nous avons un graphe qui a 35 arêtes, 4 sommets de degré 5, 5 sommets de degré 4 et 4 sommets de degré 3. Nous allons maintenant découvrir le nombre de sommets de degré 2 dans ce graphe.
Solution: À l’aide du graphique ci-dessus, nous avons obtenu les détails suivants :
Nombre d'arêtes = 35
Nombre de sommets de degré 5 = 4
Nombre de sommets de degré 4 = 5
Nombre de sommets de degré 3 = 4
Supposons maintenant que le nombre de sommets de degré 2 = n
Avec l’aide du théorème de la poignée de main, nous avons les éléments suivants :
Somme des degrés de tous les sommets = 2 * Nombre d'arêtes
Nous allons maintenant mettre les valeurs données dans la formule de négociation ci-dessus :
4*5 + 5*4 + 4*3 + n*2 = 2*35
20 + 20 + 12 + 2n = 70
52+2n = 70
2n = 70-52
2n = 18
n = 9
Ainsi, dans le graphe G, nombre de sommets de degré 2 = 9.
Exemple 4 : Ici, nous avons un graphe qui a 24 arêtes et le degré de chaque sommet est k. Nous allons maintenant découvrir le nombre possible de sommets à partir des options proposées.
- quinze
- vingt
- 8
- dix
Solution: À l’aide du graphique ci-dessus, nous avons obtenu les détails suivants :
Nombre d'arêtes = 24
Degré de chaque sommet = k
Supposons maintenant que le nombre de sommets = n
Avec l’aide du théorème de la poignée de main, nous avons les éléments suivants :
Somme des degrés de tous les sommets = 2 * Nombre d'arêtes
Nous allons maintenant mettre les valeurs données dans la formule de négociation ci-dessus :
si sinon java
N*k = 2*24
K = 48/environ
Il est obligatoire qu'un nombre entier soit contenu par le degré de n'importe quel sommet.
Nous pouvons donc utiliser uniquement les types de valeurs de n dans l’équation ci-dessus qui nous fournissent une valeur entière de k.
Maintenant, nous allons vérifier les options données ci-dessus en les mettant à la place de n une par une comme ceci :
- Pour n = 15, nous obtiendrons k = 3,2, qui n'est pas un nombre entier.
- Pour n = 20, nous obtiendrons k = 2,4, qui n'est pas un nombre entier.
- Pour n = 8, nous obtiendrons k = 6, qui est un nombre entier, et c'est autorisé.
- Pour n = 10, nous obtiendrons k = 4,8, qui n'est pas un nombre entier.
La bonne option est donc l’option C.