Solu tions des exer cices du cha pitre 3
453
© Dunod – Toute reproduction non autorisée est un délit.
2) Sup po sons, par l’absurde, qu’il existe un graphe com por tant un seul som met (noté x 1 )
de degré impair (noté d 1 ), tan dis que les degrés des autres som mets sont pairs : d 2 + d 3 , ..., d n .
On vient de mon trer que : d 1 + (d 2 + d 3 + ... + d n ) est pair car égal à 2m ; or (d 2 + d 3 + ... + d n )
étant une somme de nombres tous pairs est paire ; par suite, la somme d 1 + (d 2 + d 3 + ... + d n )
est impaire, ce qui contre dit le résul tat du 1) : « d 1 + d 2 + ... + d n » est pair. Il est donc
impossible d’avoir un seul sommet de degré impair.
Plus géné ra le ment, on peut mon trer que, pour tout graphe, le nombre de som mets de
degré impair, est pair.
3.4 On a tracé le graphe non orienté associé à la matrice :
Figure 3.7
Figure 3.8
1) En nom mant A, B, c , I les som mets sui vant l’ordre des lignes et colonnes de la
matrice, la figure 3.7 sui vante cor res pond à un tracé du graphe. La suite des opé ra tions sui ­
vantes cor res pond à un par cours pos sible de ce graphe : A est ouvert, Β est ouvert à par tir de
A, F est ouvert à par tir de A, F est fermé, G est ouvert à par tir de Β, I est ouvert à par tir de A,
D est ouvert à par tir de G, Ε est ouvert à par tir de G, C est ouvert, H est ouvert à par tir de C.
L’ordre de Prévisite est alors (A, B, F, G, I, D, E, C, H). La forêt cor res pon dant à ce par cours
est repré sen tée par la figure 3.2. Cette forêt com pre nant deux arbo res cences, le nombre de
com po santes connexes du graphe est donc deux.
2) Pour déter mi ner les som mets d’arti cu lation, nous effec tuons un par cours en pro fon -
deur du graphe, et cal cu lons les valeurs prévisite et hau teur pour cha cun des som mets de la
manière décrite dans la par tie dédiée à ce pro blème.
Figure 3.9