Corrig du TD N1

RALISATION DUN PROJET

(1) Graphe de Prcdence

Le Graphe de Prcdence du projet G = (X, U, v) est dfini de la faon suivante :
- lensemble, X, de ses sommets est constitu de lensemble des tches du projet
- lensemble, U, de ses arcs est lensemble des couples (x, y), plus simplement nots xy, de tches o x
doit prcder y dans le projet
- v est une valuation des arcs dfinie par v(x, y) = dx, la dure de la tche x
Cest donc un graphe simple orient valu.

Pour vrifier que le projet est viable, cest--dire quil existe un ordonnancement correct des tches
respectant les contraintes de prcdence, et avoir une bonne reprsentation graphique de G dterminons si une
dcomposition par niveaux est possible. Cette dcomposition permettra aussi dobtenir un Tri Topologique.
La donne fournit pour chaque tche les tches qui doivent lui succder, cela correspond ce que lon
appelle les listes des successeurs. partir de ces listes il est facile dobtenir les listes de prdcesseurs de la faon
suivante : on considre les tches de A jusqu L dans cet ordre et pour chaque successeur y de la tche x on rajoute
x comme prdcesseur de la tche y.
Cela nous donne les listes de prdcesseurs :

A : C, H, J E: I : G, K
B:L F:A J : E, H
C:H G : F, J K :A
D : B, C, K H: L:C

partir de ces listes on obtient la dcomposition par niveaux :

S0 = {E, H}, S1 = {C, J}, S2 = {A, L}, S3 = {B, F, K}, S4 = {D, G} et S5 = {I}
Le premier niveau contient les sources du graphe, cest--dire les sommets sans prdcesseur, ceux ci sont
limins des listes, les nouvelles sources ainsi obtenues dfinissent le deuxime niveau, elles sont nouveau
limines, do le niveau suivant et ainsi de suite jusqu lobtention de toutes les tches. Si le processus choue
cest que le graphe contient ncessairement un circuit et quil y a une incohrence dans les contraintes (voir poly).
Lordre dobtention des tches nous fournit de plus un Tri Topologique, ici : E, H, C, J, A, L, B, F, K, D,
G, I.

Le Graphe de Prcdence peut alors se reprsenter de la faon suivante :

E J A F G I

FIN

H C L B D

1
 Il est reprsent horizontalement (tous les arcs sont orients de gauche droite) et chaque arc a une
valuation gale la dure de la tche correspondant au sommet origine, par exemple 4 pour les arcs (C, A), (C,
D) et (C, L) car C est de dure 4. On rajout un sommet FIN correspondant la fin du projet et les arcs (D, FIN)
et (I, FIN) de dures respectives 1 et 4, qui sont les dures respectives de D et de I, car D et I sont sans
successeur.

(2) Arcs de Transitivit

Les arcs de transitivit sont des arcs correspondant des contraintes qui sont impliques par dautres
contraintes, on peut donc considrer ces contraintes comme redondantes, donc inutiles.
Ici ce sont les arcs (C, D), (H, A) et (J, G), on a en effet :

C < L < B < D pour (C, D)

H < J < A ou bien H < C < A pour (H, A)
J < A < F < G pour (J, G)

o < signifie est avant .

Do la reprsentation simplifie du graphe de prcdence obtenue en supprimant ces trois arcs de

transitivit, on y a rajout les valuations correspondant aux dures des tches :

E J A F G I
3 6 2 1 2
4
2 3
5 4
K 3 1 FIN

H 5 C 4 L 2 B 2 D

Une mthode possible permettant de dterminer les arcs de transitivit est la suivante : il suffit de faire
un parcours en largeur partir de chaque sommet du graphe. En effet, un parcours en largeur commenant au
sommet x stocke x puis les successeurs immdiats de x, puis les successeurs des successeurs, et ainsi de suite
jusqu obtenir tous les descendants de x dans le graphe. De cette faon si un successeur direct, y, de x, est
rencontr au moins une deuxime fois dans le parcours, il existe alors ncessairement un arc de transitivit de x
y.
Si le graphe de prcdence est reprsent par sa matrice dadjacence, un parcours peut se faire en O(n2)
donc lalgorithme global, qui ncessite n parcours, peut se faire en O(n3).

(3) Dates au plus tt et au plus tard, Marges totales, Dure Minimale du projet et Chemins Critiques
Les tches sont considres dans lordre topologique donn E, H, C, J, A, L, B, F, K, D, G, I, pour les
calculs des dates au plus tt, et dans lordre topologique inverse, pour les calculs des dates au plus tard.
Remarquons que tout autre ordre topologique convient ;

On obtient alors les intervalles de flottement suivants : [0, 2] pour E, [0, 0] pour H, [5, 7] pour C, [5,
5] pour J, [11, 11] pour A, [9, 15] pour L, [11, 17] pour B, [13, 13] pour F, [13, 13] pour K, [16, 19] pour D, [14,
14] pour G, [16, 16] pour I et [20, 20] pour le sommet FIN.

On trouve donc 20 jours comme dure minimale du projet ainsi que les deux chemins critiques (H,
J, A, F, G, I) et (H, J, A, K, I), ce sont des chemins qui vont dune tche initiale une tche finale et passant par
des tches critiques, cest--dire des taches o MT = 0 (marge totale).

2
 Le tableau ci-dessous rsume les rsultats :

A B C D E F G H I J K L FIN
t 11 11 5 16 0 13 14 0 16 5 13 9 20
t* 11 17 7 19 2 13 14 0 16 5 13 15 20
MT 0 6 2 3 2 0 0 0 0 0 0 6 0

(4) Ralisation par deux quipes

Sil ny a quune quipe excutant toutes les tches en respectant les contraintes de prcdence, chaque
tche devant tre excute dans sa continuit, alors tout ordre topologique convient et sa dure sera gale la
somme des dures de toutes les tches, soit 35.
Sil y a une quipe par tche, ce qui peut tre coteux, la dure minimale, gale 20, sera respecte si
chaque tche commence sa date au plus tt, ou au plus tard.

Montrons quen fait deux quipes, E1 et E2, suffisent pour excuter le projet en 20 jours.
Pour cela utilisons les chemins critiques.

Avec le premier chemin critique, (H, J, A, F, G, I), nous obtenons lorganisation suivante, reprsente
par un diagramme de GANTT des quipes :

E(3) --- C(4) L(2) B(2) K(3) D(1) ---

H(5) J(6) A(2) F(1) G(2) I(4)
20

La ligne du bas reprsente la succession des tches excutes par la premire quipe, elle correspond au
premier chemin critique, la ligne du haut correspond aux tches excutes par la deuxime quipe. Chaque tche
est reprsente par une bande horizontale allant du dbut de son excution sa fin, laxe horizontal reprsente le
temps.
La tche K doit tre imprativement tre excute de la date 13 la date 16, cest une tche critique.
La tche E peut commencer la date 0 ou 1 ou 2, mais elle doit se terminer 5, et C peut commencer.
De mme, D peut commencer 16 ou 17 ou 18 ou 19.

En se basant sur le deuxime chemin critique, (H, J, A, K, I), nous obtenons :

--- E(3) C(4) L(2) B(2) F(1) G(2) D(1) ---

H(5) J(6) A(2) K(3) I(4)
20

Les tches F et G sont des tches critiques : F doit commencer la date 13 et G la date 14. La tche C
ne peut commencer qu la date 5, sa date au plus tt.

Remarquons quil y a beaucoup dautres rpartitions possibles, en permutant des blocs entre les
lignes, par exemple, avec le deuxime diagramme, J et les tches C et L dans cet ordre, on peut aussi permuter
A et B, ou D et I,

3
 (5) Modification de la date de dbut de L
La date au plus tt de L est donc maintenant 14, elle a augment de 5, cette valeur est infrieure sa
marge totale qui est de 6, la dure minimale du projet nest donc pas modifie. Les dates au plus tt de B et de
D sont maintenant gales 16 et 18. Les dates au plus tard de L, B et D restent donc les mmes.
Les seuls changements portent donc sur L, B et D sans modifier la dure minimale du projet ainsi que
les chemins critiques.

Mais maintenant deux quipes ne suffisent plus, en effet on a :

L(2) B(2) D(1)

E(3) --- C(4) --- --- K(3) ---

H(5) J(6) A(2) F(1) G(2) I(4)

20

K, comme F et G successivement, doivent sexcuter dans lintervalle de temps [13, 16] , il est donc
impossible dexcuter successivement L, B et D dans lintervalle voulu, cest--dire [14, 19] .

Il faut donc une troisime quipe ou accepter une dure de 21, soit un retard de un jour, en excutant L,
puis B, puis D aprs la tche K.

La dure de K est de 5 jours

K est une tche critique donc tout retard sur K entrane un retard de la mme dure sur la dure
minimale du projet qui passe donc de 20 22. Dautre part, compte tenu de la structure du graphe de prcdence,
voir ci-dessous, laugmentation de la dure de K va modifier les dates au plus tard de B, D, F, G, I et L, et la date
au plus tt de D.

E J A F G I
3 6 2 1 2
4
2 5
5 4
K 5 1 FIN

H 5 C 4 L 2 B 2 D

Nous avons maintenant :

A B C D E F G H I J K L FIN
t 11 11 5 18 0 13 14 0 18 5 13 9 22
t* 11 19 7 21 2 15 16 0 18 5 13 17 22
MT 0 8 2 3 2 2 2 0 0 0 0 8 0

Deux quipes suffisent toujours, en effet on a :

--- E(3) C(4) L(2) B(2) F(1) G(2) --- D(1) ---
H(5) J(6) A(2) K(5) I(4)
22

4
PROMENADES EULRIENNES

(1) Ponts de KNIGSBERG

On peut envisager deux types de promenades : soit les points de dpart et darrive sont identiques, soit
ils sont diffrents. La situation tant assez simple, il est facile de voir, la main , en testant toutes les
promenades possibles quil ny a pas de solution. Si cela peut tre considr comme une preuve dans notre cas
particulier, condition de davoir rellement tout test, quen est-il dans le cas gnral ? Il faut modliser la
situation par une structure mathmatique pouvant tre utilise dans tous les cas, traduire la question pose dans
ce modle et tcher de rpondre rigoureusement en prouvant mathmatiquement telle ou telle proprit. Cest ce
que nous allons faire dans les questions suivantes.

En notant respectivement A, B, C et D la berge suprieure, lle, la presqule et la berge infrieure, on

peut modliser la situation par le graphe non orient suivant :

B C

Les sommets sont donc les quatre lieux, extrmits des ponts, et les artes reprsentent ces ponts. On
obtient alors un multigraphe connexe car entre A et B, et B et D il y a deux artes (multigraphe) et on peut aller
de tout sommet tout autre sommet via un chane dans le graphe (connexit).

Les deux cas envisags correspondent respectivement chercher soit un cycle passant par chaque arte
une et une seule fois, soit une chane passant par chaque arte une et une seule fois.

Pour quun cycle existe, il faut que tous les sommets aient un degr pair, autrement dit quen chaque
sommet il y ait un nombre pair dartes. En effet, dans un cycle tout sommet pouvant tre le point de dpart et
darrive, ds quon arrive en un sommet par une arte, on doit pouvoir en repartir par une autre arte. Nous
avons l une condition ncessaire dexistence dun cycle passant par chaque arte une seule fois. Cette
condition nous montre que dans le graphe prcdant un tel cycle nexiste pas, les degrs des sommets sont en
effet 3, 5, 3 et 3, le degr dun sommet tant le nombre dartes adjacentes ce sommet.
Pour quune chane passant par chaque arte une seule fois existe la condition ncessaire devient : tous
les sommets doivent tre de degr pair sauf deux, le sommet de dpart et le sommet darrive. Le graphe
prcdent ne vrifie pas non plus cette proprit, tous les degrs tant impairs.

Knigsberg, nom allemand de la ville, sappelle maintenant Kaliningrad, cest une enclave russe situe
entre la Pologne est la Lituanie. Cette ville, lhistoire mouvemente, a vu natre Goldbach, Kant, Hoffmann,
Kirchhoff, Hilbert, entre autres.
La rivire est la Pregolia, Pregel en allemand
Si lon vous dit Prends loseille et tire-toi , Bananas , Tout ce que vous avez toujours voulu
savoir sur le sexe (sans jamais oser le demander) , vous pensez bien sr W. Allen, et vous avez raison, qui
sappelle en effet Allan Stewart Knigsberg, pas tonnant aprs tout car il a dit : Quand jentends du Wagner,
jai envie denvahir la Pologne

(2) Problmatique Gnrale

Preuve du Thorme dEULER

Rappelons quun graphe est dit connexe sil existe toujours une chane reliant deux sommets
quelconques, donc si un graphe est eulrien alors il est ncessairement connexe car, possdant un cycle eulrien

5
C, il existe une chane reliant deux sommets quelconques, x et y. Il suffit en effet de partir de x, de cheminer le
long de C et de sarrter ds quon arrive en y.
Le fait que tous les sommets sont de degrs pairs a t tabli dans la question prcdente.
Ces deux remarques montrent la ncessit de la proprit.

Rciproquement, en supposant que G est connexe et que chacun de ses sommets est de degr pair,
montrons quil existe un cycle eulrien.
G tant connexe, il na pas de sommet isol, dautre part, on peut supposer que G a au moins trois
sommets, sinon G est rduit un seul sommet ou une simple arte. Si n = 3, le seul graphe vrifiant les
hypothses est :

Et ce graphe est eulrien.

Supposons donc la proprit vraie pour n 3 ;
Soit G est un graphe vrifiant les hypothses, alors partir dun sommet quelconque, cheminons dans le
graphe tant que lon peut sans utiliser deux fois la mme arte, mais on peut utiliser le mme sommet plusieurs
fois. Nous obtenons alors un cycle maximal C0, cest--dire quon ne peut pas augmenter. Cest bien un cycle
sinon le sommet darrive naurait t visit quun nombre impair de fois et serait prolongeable, donc C aussi,
car de degr pair.
Si C0 utilise toutes les artes de G, alors il est eulrien et le thorme est prouv, sinon considrons le
graphe G C0 obtenu en supprimant dans G toutes les artes apparaissant dans C0. Supprimer une arte xy
consiste supprimer uniquement la liaison entre x et y mais pas les sommets.
Considrons alors les composantes connexes G1, , Gk de G C0 non rduites un sommet, cest le
cas quand C0 a utilis toutes les artes adjacentes ce sommet, qui figure donc dans C0.
Dans chaque Gi, tous les degrs sont pairs car C0 a enlev un nombre pair dartes en chacun de ses
sommets. Alors en appliquant le Thorme chacun des Gi on obtient un cycle eulrien Ci (hypothse de
rcurrence).
Par construction, les artes de C0, C1, , Ck forment une partition des artes de G.
partir de C0 et de C1, , Ck on peut alors construire un cycle eulrien C de G. On parcourt C0 partir
dun sommet quelconque x0 et, en chaque sommet x, sil existe une arte adjacente nappartenant pas C0, donc
un certain Ci, on parcourt entirement Ci, jusqu revenir en x. On recommence en x tant quil existe une arte
qui nest pas dans C0, puis on continue ainsi sur C0 jusqu finalement revenir en x0.
Par construction, C est alors un cycle eulrien de G, car toutes ses artes ont t considres.

On peut illustrer cette dmonstration sur lexemple propos.

Si C0 = (3, 4, 10, 11, 6, 7, 8, 12, 9, 2, 3) alors G C0 est alors le graphe dont les artes sont en trait
plein :

2 3 4

9 10

1 5

12 11

8 7 6
Le graphe G C0 a trois composantes connexes qui donnent les cycles C1 = (1, 2, 8, 1), C2 = (4, 5, 6, 4)
et C3 = (9, 10, 12, 11, 9), en partant du sommet 3 de C0, on obtient le cycle eulrien de G :

C = (3, 4, 5, 6, 4, 10, 12, 11, 9, 10, 11, 6, 7, 8, 1, 2, 8, 12, 9, 2, 3)

6
Graphes Pseudo Eulriens

Une consquence du Thorme dEULER est bien sr :

Corollaire
Un graphe simple non orient G = (X, E) est Pseudo Eulrien si et seulement si il est connexe et a
uniquement deux sommets de degrs impairs.

Sil existe une chane eulrienne, le graphe est ncessairement connexe, largument est identique celui
de la question (1), et la proprit sur les degrs a dj t vue la question (2) sur les Ponts de Knigsberg.

Inversement, appelons x et y les deux sommets de G dont les degrs sont impairs. Considrons alors le
graphe G = G + xy, cest--dire le graphe G dans lequel on rajoute une arte reliant x y. Dans G tous les
sommets sont alors de degrs pairs, on peut donc appliquer le Thorme dEULER qui garantit lexistence dun
cycle eulrien C dans G, ce cycle, qui utilise larte xy peut schmatiquement scrire : C = (x, , y, x). On
en dduit donc lexistence dune chane eulrienne C = (x, , y) = C - xy allant de x y dans G.

Cas des Multigraphes

Les rsultats prcdents sont bien sr valables dans le cas des multigraphes, en effet tous les
raisonnements faits sont toujours valables en cas dartes multiples.
Une autre faon de rpondre la question consiste transformer le multigraphe en graphe simple en
rajoutant un sommet supplmentaire, donc de degr 2, sur chaque arte multiple.

Tous eulriens ?

Le graphe suivant que lon doit dessiner sans lever le crayon et sans passer deux fois sur le mme
trait est pseudo-eulrien :

Quen pensez-vous ? Cela ne vous rappelle til rien ?

(3) Algorithmes

Soit G = (X, E) un graphe non orient donn par sa matrice dadjacence M.

On doit dabord vrifier sa connexit, il suffit pour cela dappliquer soit un Parcours en Largeur soit
un Parcours en Profondeur partir dun sommet quelconque. Ces parcours sont des algorithmes de marquage
qui permettent dexplorer compltement un graphe :

- arriv en tout sommet le parcours en largeur le marque visit puis visite tous ses voisins non
encore visits, puis tous les voisins non visits des voisins et ainsi de suite jusqu visiter tous les
sommets du graphe, auquel cas le parcours est termin ou bien reprend en un sommet non encore
visit

- arriv en tout sommet x le parcours en profondeur le marque visit puis choisit lun de ses voisins
y non encore visit, sil en existe, quon explore de la mme faon, si y nexiste pas on repart du

7
 sommet ayant prcd x dans le parcours sil existe sinon la recherche reprend en un sommet non
encore visit ou bien se termine.

En gros le parcours en largeur correspond une exploration concentrique du graphe partir du

sommet initial alors que le parcours en profondeur explore le graphe le plus loin possible en tout sommet quitte
revenir en arrire pour continuer. Dans les deux cas, chaque sommet nest marqu quune fois.
Ces parcours permettent de vrifier la connexit dun graphe car il suffit en effet de tester si lon peut
obtenir tous les sommets du graphe partir dun sommet quelconque. Cela peut se faire en O(n2) tapes.

Il faut ensuite calculer les degrs des sommets : pour chaque sommet x, on fait la somme des lments
le la ligne correspondante de la matrice dadjacence, cest dire des M(x, y) pour chaque y de G. Lalgorithme
est en O(n2) car il faut examiner toute la matrice.

Si les degrs vrifient les conditions voulues, il faut construire le cycle ou la chane. Nous avons vu que
pour la chane on peut se ramener au cycle en rajoutant une arte entre les deux sommets ayant un degr impair,
il suffit donc de savoir construire le cycle.
La preuve que nous avons donne du Thorme dEULER, et nous lavons vu sur un exemple, est
constructive et dbouche sur une fonction rcursive que lon peut schmatiquement crire de la faon suivante :

Euler (G ; C)
Construire un cycle maximal C0 de G ne passant pas deux fois par la mme arte
si C0 contient toutes les artes de G
alors C = C0
sinon Dterminer les Composantes connexes G1, , Gk non rduites un sommet
pour i = 1 k faire Euler (Gi ; Ci)
Construire C partir de C0, C1, et Ck

La fonction Euler (G ; C) construit rcursivement un cycle eulrien C partir dun graphe G et

Construire C partir de C0, C1, et Ck se fait comme indiqu dans la preuve du Thorme.

Pour estimer sa complexit en temps, il faudrait crire en dtail les constructions de C0 et de C partir
de C0, C1, et Ck, on peut montrer quelles peuvent se faire en O(n2), ainsi que la recherche des composantes
connexes de G, voir plus haut. Globalement lalgorithme est en O(n2), donc polynomial.

Sil existe uniquement deux sommets de degrs impairs, x et y, il suffit de rechercher un cycle eulrien
C dans le graphe G = G + xy, puis de supprimer larte xy de C.

Un deuxime algorithme (construction du cycle final C)

Dans lalgorithme prcdent, le point dlicat, au niveau de la mise en uvre effective, cest dire de la
programmation, est bien sr la construction effective du cycle C partir des sous cycles C0, C1, et Ck. Nous
proposons ici un deuxime algorithme, trs proche du prcdent, mais permettant de simplifier considrablement
cette tape de construction. Il consiste grer les sommets et les artes en utilisant une pile , note P,
initialement vide.

Lide est la suivante : partant dun sommet initial quelconque x0, on construit un cycle maximal C0 ne
passant pas deux fois par la mme arte en empilant dans P les sommets dans lordre de leur rencontre et en
marquant les artes au fur et mesure. Si C0 contient toutes les artes de G, alors C = C0, sinon on dpile les
sommets et on les rajoute dans cet ordre au cycle C jusqu trouver en haut de pile un sommet ouvert x,
cest dire un sommet x adjacent une arte xy non encore utilise, cest dire non marque, le sommet y est
alors empil dans P et on continue partir de y.
Et le processus se poursuit de la mme faon tant que la pile nest pas vide.

Le cycle C ainsi construit est un des cycles eulriens possibles du graphe G, en effet, en remontant
C0, et en continuant lexploration ds quon le peut partir dun sommet de C0 vers la premire arte disponible,
on greffe naturellement, sans gestion supplmentaire, et itrativement, les autres sous cycles C1, C2, C0.

8
 Une criture possible de cet algorithme est la suivante :

Euler2 (G ; C)
C=;
P= ;
x0 = sommet quelconque de G ;
Empiler (x0) ;
x = x0 ;
tant que P faire
tant que x est ouvert faire
Choisir xy une arte libre adjacente x ;
Marquer xy non libre ;
Empiler (y) ;
x=y;
C=C+x;
Dpiler (P) ;
si P alors x = Sommet de Pile ;
Le cycle eulrien est C

C est une simple liste contenant la suite des sommets du cycle cherch. P, la pile, peut tre implmente
soit par une liste soit par un tableau, et enfin, il faut prvoir une structure permettant de marquer les artes dj
utilises. Il est facile dtablir que cet algorithme peut tre implment en O(n2) en temps et en espace.

Remarque
Le problme du Cycle Hamiltonien cest--dire de la recherche dun cycle passant une fois et une seule
par tous les sommets dun graphe est lui NP Difficile, on ne connat aucun algorithme polynomial pour le
rsoudre.

SUJETS DE RFLEXION

Graphes Orients

Dun point de vue terminologique, lorsque le graphe G est orient, on parlera de circuit au lieu de cycle
et de chemin au lieu de chane. Pour tout sommet x de G on note :

- d-(x) le degr intrieur ou degr entrant, cest--dire le nombre darcs arrivant en x

- d+(x) le degr extrieur ou degr sortant, cest--dire le nombre darcs sortant de x

Alors le Thorme dEULER et son Corollaire deviennent :

Thorme
Un graphe orient G = (X, U) est Eulrien si et seulement si le graphe non orient sous-jacent est
connexe et pour tout sommet x on a d-(x) = d+(x).

Corollaire
Un graphe orient G = (X, U) est Pseudo Eulrien si et seulement si le graphe non orient sous-jacent
est connexe et pour tout sommet x on a d-(x) = d+(x) sauf pour deux sommets y et z, le dpart et larrive, pour
lesquels on a d+(y) = d-(y) + 1 et a d-(z) = d+(z) + 1.

Les preuves ainsi que le principe de lalgorithme sont similaires celles dj faites dans le cas non
orient, en tenant bien sr compte de lorientation.

9
Problme du Postier Chinois (PPC)

Il sagit donc de dterminer un parcours ferm dun graphe non orient connexe G passant au moins une
fois par chacune de ses artes et qui soit le plus court possible en nombre dartes utilises. Si le graphe est
eulrien, la solution est bien sr un cycle eulrien, chaque arte est utilise exactement une fois, mais comment
faire dans le cas gnral ?

Rendre un Graphe Eulrien ?

La question est : tant donn un graphe non orient quelconque G, quel est le nombre minimal dartes
quil faut ajouter G pour le rendre eulrien ?
La rponse est particulirement simple sachant que dans G le nombre de sommets de degrs impairs
est toujours pair, en effet, si m est le nombre dartes, on a :

d (x) = d (x) + d (x) = 2m

x X d (x) pair d (x) impair

La somme des degrs est gale 2m car chaque arte xy sera compte exactement deux fois : une fois
avec d(x) et une fois avec d(y). On en dduit que la somme sur les sommets de degrs impairs est ncessairement

paire, ce qui nest possible que sil y a un nombre pair de sommets de degrs impairs.

Pour rendre G eulrien, il faut bien sr rendre tous les degrs pairs, il suffit donc dassocier par paires
les sommets de degrs impairs et de rajouter les artes correspondantes.

Quelques indications pour la rsolution de PPC

On peut exploiter cette ide pour rsoudre PPC, mme dans le cas o le graphe G est valu, cest
lAlgorithme de EDMONDS JOHNSON, que nous ne dmontrerons pas, il se rsume aux 4 tapes
suivantes :

tape 1 : Dterminer les sommets de degrs impairs, x1, , x2k, et, pour chaque paire {xi, xj} construire le plus
court chemin C(xi, , xj) les joignant dans G. Si G nest pas valu, chaque arte comptera pour 1

tape 2 : Construction du graphe complet K2k ayant pour sommets {x1, , x2k} et dont les artes sont values
par la longueur du plus court chemin correspondant

tape 3 : Dterminer un couplage parfait M de valeur minimale de K2k, cest--dire apparier les sommets de
K2k de sorte que la somme des valuations des k artes de M soit minimale

tape 4 : Construire le graphe G en ddoublant dans G les artes correspondant aux plus courts chemins des
artes de M, alors G est eulrien. La solution cherche est alors un cycle eulrien de G

Les sommets de degrs impairs sont facilement dterminables, les plus courts chemins sont calculables
par lalgorithme de DIJKSTRA, la construction de G est simple et nous avons vu comment on peut dterminer
un cycle eulrien. Quant au couplage minimal de K2k, il est calculable en temps polynomial mais par des
techniques assez labores. On peut dmontrer :

Thorme (EDMONDS - JOHNSON, 1973)

Lalgorithme prcdent rsout le PPC en temps polynomial

On peut tendre ce rsultat aux graphes orients mais par un algorithme assez diffrent, et il faut de plus
que le graphe soit fortement connexe, cest--dire que pour toute paire de sommets x et y du graphe, il existe un
chemin de x y et un chemin de y x.

10