Overblog Suivre ce blog
Editer l'article Administration Créer mon blog
12 juin 2011 7 12 /06 /juin /2011 12:00

Cet article suit : Graphes : degré d'un sommet

 

 

Dans un graphe composé de N arêtes, on a la formule suivante, appelé lemme des poignées de mains :

Autrement formulé, cela signifie que dans un graphe, la somme des degrés est un nombre pair, plus précisément, c'est le double du nombre d'arêtes.

 

Conséquence.  La somme de degrés impairs d'un graphe est paire. Pourquoi ?

 

Réponse. Dans un graphe, il y deux sortes de sommets, ceux dont le degré est pair et ceux dont le degré est impair. On peut donc associer les degré pair et les degré impair pour faire la somme :

Une somme de nombres pairs est un nombre pair, en y ajoutant un nombre impair, on obtiendrait un nombre impair, donc la seconde somme du terme de droite est un nombre pair.

Fin de la PREUVE.

 

Pourquoi le lemme s'appelle-t-il lemme des poignées de mains ?

 

Considérons le graphe comme décrivant les relations entre les personnes d'un groupe. On peut imaginer que chaque sommet du graphe est une personne et que si cette personne connait une autre personne, elle lui sert à main, autrement dit, qu'il y a une arête entre-elles. Le degré d'une personne est le nombre de connaissances qu'elle a dans le groupe.

 

Voici la reformulation du lemme et de la conséquence:

  1. Lemme : Dans un groupe de personnes, si l'on fait la somme des personnes connues par chaque individu, on obtient le double du nombre de connaissances au sein du groupe.

  2. Conséquence : Dans un groupe de personnes, si les personnes connaissant un nombre impair d'individus font la somme des personnes qu'elles connaissent, alors le total obtenu est un nombre pair.

 

 

Sur Facebook, si je demande à mes amis de me dire combien ils ont d'amis communs avec moi, et que je fais la somme des réponses obtenues, alors le résultat sera pair. Il sera le double du nombre de relations d'amitié Facebook existant parmi mes amis, moi exclus.

 

Suite : Lemme des poignées de main : conséquence

Partager cet article

Repost 0
Published by Maths_Buchwald - dans Nombres
commenter cet article

commentaires

Présentation

  • : Maths Otak'
  • Maths Otak'
  • : Au départ, j'ai créé ce blog pour y publier des articles reliant Maths et histoire de l'art et la culture. Maintenant, il me permet d'aborder des sujets simples de la culture mathématique. J'aime parler de jeux vidéos. Vous trouverez aussi sur ce site des fiches de maths et Histoire des Arts de 2009-2010 au format *.pdf. Je ne sais pas où me mène ce blog donc il ne sera sans doute plus le même si je continue à l'alimenter dans un an. N'hésitez pas à laisser des commentaires.
  • Contact

Twitter

Recherche

Mes vidéos

Catégories