EPFL RECHERCHE OPÉRATIONNELLE

Institut de Mathématiques IN/MA

J.-F. Hêche HIVER 2002/2003

CORRIGÉ DE LA SÉRIE D’EXERCICES 10

Les énoncés des séries et leurs corrigés ainsi que les copies des présentations sont disponibles
sur le site du cours : roso.epfl.ch/cours/ro/2002-2003.

Problème 1

a) i) Non, le graphe n’est pas connexe.

ii) Oui, le graphe est connexe et il y a exactement 2 sommets de degré impair.
iii) Non, il y a 4 sommets de degré impair.
iv) Non, il y a 4 sommets de degré impair.
b) Un graphe G = (V,E) est eulérien ⇔ il est connexe et a 0 ou 2 sommets de degré impair.
Justification :
⇒ G est eulérien ⇒ ∃ une chaı̂ne ou un cycle eulérien ⇒ le graphe est connexe.
S’il s’agit d’un cycle ⇒ tous les sommets de G sont de degré pair.
S’il s’agit d’une chaı̂ne ⇒ seuls les sommets terminaux de la chaı̂ne sont de degré
impair.
⇒ G possède 0 ou 2 sommets de degré impair.
⇐ Supposons le théorème vérifié pour tout graphe G satisfaisant |E| < m et montrons
qu’il l’est également pour graphe G avec |E| = m.
Par hypothèse, G est connexe et possède soit aucun soit 2 sommets de degré impair.
Soient a et b les deux sommets de G de degré impair ou deux sommets confondus
quelconques si G ne possède pas de tels sommets.
Parcourons G en partant de a et en n’empruntant que des arêtes qui n’ont pas été
parcourues. Ce parcourt se terminera au sommet b formant ainsi une chaı̂ne ou un
cycle µ.
Considérons le graphe partiel G0 = (V,E \ { arêtes de µ}). Considérons les compo-
santes connexes G01 , . . . ,G0p de G0 possédant au moins une arête. Chacune de ces com-
posantes contient moins de m arêtes et ne possède que des sommets de degré pair.
Par hypothèse, ces composantes sont donc eulériennes et leurs arêtes sont contenues
dans des cycles eulériens µi (i = 1, . . . ,p).
D’autre part, µ touche chacune de ces composantes par connexité de G. Suppo-
sons les composantes G0i indicées dans l’ordre dans lequel µ les touche et soit x i
un point de contact de µ avec la composante G 0i . Considérons maintenant la chaı̂ne
µ[a,x1 ] ∪ µ1 ∪ µ[x1 ,x2 ] ∪ µ2 ∪ . . . ∪ µp ∪ µ[xp ,b]} (où µ[x,y] dénote la sous-chaı̂ne de µ
reliant x et y). Cette chaı̂ne contient les arêtes de µ et de G 0 donc c’est une chaı̂ne
eulérienne de G et G est eulérien.
Le théorème étant facilement vérifié pour m = 1 (m = 0 trivial), il est démontré pour
tout m ≥ 1.
c) Un graphe orienté G = (V,E) est eulérien ⇔ G est connexe et deg + (v) = deg− (v),∀v ∈ V
où deg+ (v) dénote le nombre d’arcs issus de v et deg − (v) le nombre d’arcs se terminant
en v.
Justification :
⇒ Les deux conditions sont clairement nécessaires.

1
 ⇐ La preuve est similaire à celle du cas non orienté. On construit un circuit initial µ et on
considère le graphe partiel G0 obtenu en retirant les arcs de µ. Chaque composante
connexe de G0 satisfait deg+ (v) = deg− (v) en chacun de ses sommets et est donc
eulérienne par hypothèse de récurrence. Il est alors facile de reconstruire un circuit
eulérien complet pour G.

Problème 2

a) Un camion de hauteur x peut effectuer la livraison si et seulement si la chaı̂ne de section

maximale reliant A et B a une section supérieure ou égale à x. ( Évidemment, la section
d’une chaı̂ne est définie, ici, comme le plus petit poids des arêtes la formant.) Le problème
posé se ramène donc à un problème de chaı̂ne de section maximale entre A et B. La
livraison n’étant possible que si la section maximale est d’au plus x mètres, la hauteur du
camion.
b) L’arbre recouvrant de poids maximum fournit des chaı̂nes de section maximale entre toutes
les paires de sommets d’un graphe. Pour déterminer un tel arbre on peut appliquer l’algo-
rithme de Kruskal (glouton) ou de Prim.
c) Appliquons l’algorithme de Kruskal. Après avoir numéroté les arêtes e k du réseau par
ordre non-croissant de leur poids c(e k ), on introduit successivement ces arêtes dans l’arbre
maximal de poids maximum T pour autant qu’elles ne forment pas de cycle avec les arêtes
s’y trouvant déjà.

k ek c(ek ) ∈ T
1 {A,5} 900 X
2 {5,6} 870 X
3 {2,3} 860 X
4 {1,2} 500 X
5 {4,B} 490 X
6 {A,1} 450 X
7 {3,4} 435 X
8 {3,6} 425
9 {4,8} 390 X
10 {4,7} 340 X
11 {1,5} 335
12 {8,B} 325
13 {2,7} 310
14 {A,3} 120
L’arbre recouvrant de poids maximum T est représenté dans le réseau ci-dessous en traits
pleins. L’unique chaı̂ne reliant A et B dans l’arbre optimal est représentée en gras. Il s’agit
d’une chaı̂ne de section maximale entre ces deux sommets. La section de cette chaı̂ne étant
égale à 4.35 mètres, la livraison est possible, si le camion mesure au plus 4.35 mètres de
hauteur.

2
 1 335 5
870
6 B
450 900
425
500 A 120 3
490 325
860 435

2 4 390 8
310 340
7

La chaı̂ne de section maximale fournit l’itinéraire réalisable suivant :

A −→ 1 −→ 2 −→ 3 −→ 4 −→ B.

Problème 3

a) Preuve par induction : pour n = 1 on a A, la matrice d’adjacence sommets-sommets du

graphe G(V,E). Par définition

1 s’il existe dans G un arc (chemin de longueur 1) reliant v i à vj
aij =
0 sinon
Supposons que l’hypothèse soit vraie pour n − 1 et montrons qu’elle l’est pour n :
An = An−1 A.
|V |
(n) (n−1)
X
aij = aik akj
k=1
 (n−1)

 1 si aik 6= 0 et akj 6= 0
i.e. s’il existe un chemin de longueur n − 1 reliant v i à vk



(n−1)
aik akj = et un chemin de longueur 1 reliant vk à vj ,
donc un chemin de longueur n de vi à vj (passant par vk )





0 sinon
En faisant la somme sur tous les k = 1, . . . ,|V | et en utilisant la règle 1 + 1 := 1, on a bien
(n)
que aij est égal à 1 dès qu’il existe un chemin de longueur n de v i à vj .
(n)
b) Le coefficient aij de la matrice An obtenue avec la règle d’addition usuelle représente le
nombre de chemins de longueur n de vi à vj .
Preuve par induction : pour n = 1 on a A, la matrice d’adjacence sommets-sommets du
graphe G(V,E). Par définition

1 s’il existe dans G un arc (chemin de longueur 1) reliant v i à vj
aij =
0 sinon
Supposons que l’hypothèse soit vraie pour n − 1 et montrons qu’elle l’est pour n :
An = An−1 A.
|V |
(n) (n−1)
X
aij = aik akj
k=1

(n−1) s s’il existe un chemin de longueur 1 reliant v k à vj
aik akj =
0 sinon

3
 où s, par hypothèse, est le nombre de chemins de longueur n − 1 de v i à vk . En faisant la
somme de tous les chemins de vi à tous les vk et en comptant ceux qui se prolonge de v k
(n)
à vj , on a bien que aij est le nombre de chemins de longueur n de v i à vj .

Problème 4 (MA)
Considérons les composantes connexes C 1 ,...,Cp de G (c’est-à-dire les composantes connexes du
graphe non-orienté tiré de G en enlevant l’orientation des arcs). On note pour tout i ∈ {1,...,p},
Ci = (Vi ,Ei ) avec ni = |Vi | et mi = |Ei |. Ordonnons les sommets de G de la manière suivante :

v1 , . . . ,vn1 ∈ V1
vn1 +1 , . . . ,vn1 +n2 ∈ V2
... ... ...
vn1 +...+np−1 +1 , . . . ,vn1 +...+np ∈ Vp

et les arcs de G comme :

e1 ,...,em1 ∈ E1
em1 +1 ,...,em1 +m2 ∈ E2
... ... ...
em1 +...+mp−1 +1 ,...,em1 +...+mp ∈ Ep

Autrement dit, on numérote en premier les sommets et les arcs du sous-graphe C 1 , puis ceux de
C2 et ainsi de suite jusqu’à Cp . Alors selon cette numérotation la matrice d’incidence sommets-
arcs A de G est une matrice diagonale par blocs où les blocs diagonauxPsont les matrices d’inci-
dence sommets-arcs Ai des sous-graphes Ci . Le rang de A vaut donc pi=1 rang(Ai ). Montrons
alors que pour tout i ∈ {1,...,p}, le rang de A i vaut ni −1. Fixons donc i. Puisque Ci est connexe,
il existe un graphe partiel Ti de Ci qui est un arbre. La matrice d’incidence sommets-arcs de
Ti est de rang ni − 1, ce qui implique que la matrice d’incidence sommets-arcs A i de Ci est de
rang supérieur ou égal à ni − 1. Comme cette matrice ne peut pas avoir rang n i (la somme de
ses lignes est nulle) on a donc rang(A i ) = ni − 1, et :
p
X p
X
rang(A) = rang(Ai ) = (ni − 1) = n − p.
i=1 i=1

Problème 5 (MA)
Afin de démontrer que tout graphe orienté G = (V,E) connexe vérifiant deg + (v) = deg− (v),∀v ∈
V est fortement connexe, nous allons démontrer la contraposée. Tout graphe orienté G = (V,E)
non fortement connexe est soit non connexe soit ne vérifie pas deg + (v) = deg− (v),∀v ∈ V .
Considérons un graphe G = (V,E) non fortement connexe. Il existe donc dans G deux sommets
a et b pour lesquels il n’existe aucun chemin de a vers b. Soit V 0 l’ensemble des sommets de
G accessibles depuis a et V̄ 0 = V \ V 0 son complément. Ces deux ensembles sont non vides
0 et b ∈ V̄ 0 . Soit encore C(V 0 ,V̄ 0 ) = (v ,v ) ∈ E | v ∈ V 0 et v ∈ V̄ 0 et C(V̄ 0 ,V 0 ) =

car a ∈ V i j i j
(vi ,vj ) ∈ E | vi ∈ V̄ 0 et vj ∈ V 0 les coupes orientées entre V 0 et V̄ 0 . Par définition de V 0 nous


avons C(V 0 ,V̄ 0 ) = ∅. Soit c la cardinalité de C(V̄ 0 ,V 0 ), deux cas sont à distinguer :

1. c = 0 : Il n’existe aucun arc entre les sommets de V 0 et de V̄ 0 , ni dans un sens ni dans

l’autre. Les ensembles V 0 et V̄ 0 étant non vides, le graphe G n’est pas connexe.
2. c > 0 : Notant E 0 l’ensemble des arcs du sous-graphe induit par V 0 , nous avons :
X
deg+ (v) = (vi ,vj ) | (vi ,vj ) ∈ E 0 + (vi ,vj ) | vi ∈ V 0 ,vj ∈ V̄ 0 = E 0 + 0
 

v∈V 0

4
 et
X
(vi ,vj ) | (vi ,vj ) ∈ E 0 (vi ,vj ) | vi ∈ V̄ 0 ,vj ∈ V 0 = E0 + c
 
deg− (v) = +
v∈V 0

Ainsi, X X
deg+ (v) − deg− (v) = −c < 0
v∈V 0 v∈V 0

et il existe au moins un sommet v dans V 0 ne satisfaisant pas deg+ (v) = deg− (v).

10 janvier 2003 – JFH/ms