Chapitre 3 • Éléments de la théorie des graphes
96
on vérifie que pour tout arc (x i ,
x j ), on a bien : i < j.
ExEr cicEs
*3.1 Voca bu laire et concepts de base des graphes
Soit le graphe G ci- dessous
1. Don ner G
1
1 A2 , G
1
1 B2 , G
2
1 A 2 , G
2
1 B 2 .
2. Don ner les demi- degrés inté rieurs et
exté rieurs des som mets A et B. Don ner les
éven tuelles entrée(s) et sor tie(s) de G.
3. Don ner un exemple de che min simple
mais non élé men taire.
4. Existe- t-il un cir cuit hamiltonien dans
G ? Un che min hamiltonien ?
5. G est- il for te ment connexe ? Jus ti fier en
détail.
6. Don ner plu sieurs arbo res cences dif fé -
rentes, de racine B, extraites du graphe.
**3.2 Pro blème des 7 ponts de Königsberg (cF. 3.1.1.)
On peut asso cier le dia gramme ci- dessous, à ce pro blème :
B
A
C
D
1. Que repré sentent les som mets ? Les arêtes ?
2. Cal cu ler le degré de chaque som met, puis en déduire l’impos si bi lité du
pro blème.
3. Que se passerait- il si on ajou tait un 8
ème
pont, joi gnant direc te ment la
rive nord A et la rive sud D de la rivière ?
*3.3 Degrés des sommets d’un graphe non orienté
1. Montrer que la somme des degrés de tous les sommets de G est un
nombre pair
2. Montrer qu’il n’existe pas de graphe ayant un seul sommet de degré impair
x 8
x 9
x 10
x 6
x 3
x 5
x 4
x 7
x 2
x 1
Figure 3.32
B
A
F
E
C
D