Overblog Suivre ce blog
Editer l'article Administration Créer mon blog
18 juillet 2011 1 18 /07 /juillet /2011 12:00

Cet article suit Somme des degrés impairs

 

La propriété vue dans l'article cité plus haut est la suivante :

 

Propriété 1. Dans un graphe la somme de degré impairs est un nombre pair.

 

Autrement dit, en ne considérant que les sommets ayant un degré impair, on obtient un nombre pair en faisant leur somme. Mais, alors cela implique que le nombre de ces sommets de degré impair est nécessairement pair. Cela provient de la propriété suivante concernant les nombres entiers pairs et impairs.

Propriété 2. Une somme de nombres impairs est impaire si et seulement si ces nombres sont en quantité impaire.

Preuve.
Considérons r nombres impairs n1, n2, ......, nr . Comme ces nombres sont impairs, on peut écrire

n1=2k1+1, n2=2k2+1, ....., nr=2kr+1k1, k2, ...., kr sont des entiers.

Alors n1+ n2+ ......+ nr =  2k1+1+2k2+1+....+2kr+1 = 2(k1 + k2+ ....+ kr) + 1+...+1=2(k1 + k2+ ....+ kr) + r

Donc n1+ n2+ ......+ nr = 2m + r, où m=k1 + k2+ ....+ kr .

Si r est impair : r=2p+1 pour un entier p et n1+ n2+ ......+ nr = 2m + 2p+1=2(m+p)+1=2m'+1, avec m'=m+p. Dans ce cas, la somme est impaire.
Sinon, r est impair pair : r=2p et n1+ n2+ ......+ nr = 2m + 2p+1=2(m+p) =2m'  . Dans ce cas la somme est paire. 

FIN DE LA PREUVE.

 

 

Remarque : Même si cela ne sert pas dans la propriété qui suit, les entiers n1, n2, ......, nr ne sont pas nécessairement positifs.

 

On en déduit donc le résultat suivant : 

 

Propriété 3. Dans un graphe le nombre de sommets ayant un degré impair est pair.

 

En gardant l'exemple de mes amis Facebook, je peux construire un graphe composé de ces amis. Il y a une arête lorsque deux de mes amis sont amis entre eux. Le degré d'un ami est donc le nombre d'amis qu'il a en commun avec moi. De la propriété 3, on déduit que j'ai un nombre pair d'amis Facebook ayant un nombre impair d'amis communs avec moi.

 

Autres articles concernant les graphes pour débutants.

Partager cet article

Repost 0
Published by Maths_Buchwald - dans Graphes
commenter cet article

commentaires

Maths_Buchwald 18/03/2012 16:14


J'ai effacé par erreur le commenaire laissé par un visiteur. Il m'a signalé une erreur et je l'ai corrigée. Merci ! Poster d'autres commentaires de ce genre s'il vous plait.

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