FACULTE DES SCIENCES DE TUNIS 26/06/2020

Dépt des Sciences de l'Informatique

EXAMEN
Session Principale

Section : INFO 3
Epreuve : Graphes & Flots
Durée : 1 Heure 30 mns
Documents Non Autorisés
------------------------------------------------------------------------------------------------------------------------
Le barème est à titre indicatif

Toutes les réponses doivent être justifiées

Exercice : (7 Pts)
Le directeur technique d’une usine doit réaliser aujourd’hui six tâches Ti (i = 1,…,6) d’une durée chacune
une heure. Chaque tâche nécessite la mise en commun d'un certain nombre d’ouvrier Oj, comme indiqué au
tableau ci-dessous :

O1 O2 O3 O4 O5 O6
T1 X X X
T2 X X X
T3 X X
T4 X X X
T5 X X
T6 X X X

Par exemple, l’exécution de la tâche T1 nécessite les ouvriers O1, O3 et O5.

Problème : (13 Pts)

Un parc à Tunis propose à ses visiteurs des parcours de santé modélisés par le graphe G ci-dessous.
Chaque parcours est représenté par une arête et peut être réalisé dans les deux sens.
A côté de chaque arête on a porté la longueur du parcours exprimée en mètres.

1
 B G
30 70
30 20 E
70
C 50
A
20 40
10
H

D
60 20
F
40 I

Aux croisements des parcours (c’est-à-dire aux sommets du graphe G), le propriétaire a installé des fontaines
d’eau.

1) a) Est-il possible que Faouzi puisse réaliser un itinéraire complet, c’est-à-dire un itinéraire empruntant
une fois et une seule chaque parcours ? Justifier la réponse.
b) Faouzi souhaiterait réaliser un itinéraire empruntant au moins une fois chaque parcours. Déterminer
les parcours où il pourra passer deux fois afin de minimiser la distance totale de son itinéraire.
c) Donner la longueur minimale, exprimée en mètres, d’un tel itinéraire. Proposer un itinéraire possible.

2) L’organisateur du parc de santé voudrait moderniser, en trois étapes, les différents parcours de son parc.
Il envisage de le faire en modernisant à chaque étape, un tiers des parcours. Pendant les travaux seuls les
parcours à moderniser sont inaccessibles. Lors de la première étape il souhaite laisser accessibles des
parcours reliant toutes les fontaines entre elles et minimisant la distance totale.
a) Déterminer les parcours qu’il est possible de rénover lors de la première étape.
b) Faouzi voudrait, dans ces conditions, réaliser un itinéraire passant par toutes les fontaines et qui
emprunte chacun des parcours disponibles une fois et une seule. Est-ce possible ? Si oui, par
quelle(s) fontaine(s) Faouzi peut-il commencer son itinéraire ? Donner la longueur d’un tel itinéraire.

Faouzi BEN CHARRADA

2
FACULTE DES SCIENCES DE TUNIS 26/06/2020
Dépt. INFORMATIQUE

Correction de l’Examen IF3

Exercice : (7 Pts)

On associe à chaque tâche un sommet. et deux sommets sont adjacents si les tâches correspondantes ont au
moins un ouvrier en commun. La durée minimum d’exécution des tâches n’est autre que le nombre chromatique
du graphe G ci-dessous noté :

T3 T5

T1

T6

T4 T2

G contient un sous graphe complet d’ordre 4 (K4) qui est engendré par les sommets {T1 ;T2 ;T4 ;T6}, donc :
γ(G) ≥ 4. On a pu le colorier par 4 couleurs, donc γ(G) = 4, c’est-à-dire que la durée minimum d’exécution des
tâches est quatre heures.
On donne ci-dessous et à titre d’exemple, un calendrier d’exécution des tâches :
1ère heure : T2 et T3
2ème heure : T5 et T6
3ème heure : T1
4ème heure : T4

3
Problème : (13 Pts)

1) a) Les sommets de degré impairs sont : B, D, F et H. D’après le théorème du cours, pour qu’il existe un
itinéraire empruntant une et une seule fois chaque parcours (Cycle ou chaine eulérienne), il faut qu’il
existe dans le graphe au plus 2 sommets de degré impairs, ce qui n’est pas le cas.

b) La chaine la plus courte (ou de poids minimum) entre deux sommets de degré impair parmi B, D, F et
H est celle qui relie B et D. Nous en avons deux qui sont C1 = (B, A, D) et C2 = (B, C, D) de longueur
chacune 40 m. Dupliquons une parmi elles, supposons C1. Le graphe G’ obtenu après duplication de C1
contient exactement deux sommets de degré impairs qui sont F et H. G’ admet donc une chaîne
eulérienne qui commence par F ou H. Les arêtes dupliquées sont celles de C1, c’est-à-dire (AB) et (AD).
c) La longueur de l’itinéraire est la somme des longueurs de toutes les arêtes de G auquel on ajoute la
longueur de C1 c’est-à-dire (460 + 30 + 10) = 500 m.
Pour obtenir un tel itinéraire, il faut commencer par F ou H. Ci-dessous un tel itinéraire possible :
Exemple : F ; I ; H ; G ; E ; B ; A ; D ; A ; B ; C ; D ; F ; E ; H.

2) a) Le fait que l’organisateur souhaite laisser accessibles des parcours reliant toutes les fontaines entre
elles, revient à trouver un graphe partiel G’ de G qui est connexe et dont la somme de ses arêtes est
minimum. Le problème consiste donc à trouver un arbre de poids minimum. En appliquant l’algorithme
de KRUSKAL, l’arbre obtenu est :

B G
30
E
20 70

C 40
A
H

10 20 20
D
F I
40

Les parcours à rénover à la 1ère étape correspondent aux arêtes supprimées qui sont : (AB) ; (DF) ; (EG) et (EH).

b) La réponse est OUI ; et il peut commencer son itinéraire par A ou G. Un tel itinéraire est donné à la figure ci-
dessus. Cet itinéraire est de longueur 250 m.

4
 BAREME

Exercice : (7 Pts)

Modélisation : 1 Pt
Construction du graphe : 2 Pts
Détermination de γ(G) : 1 Pt
Justification de l’optimalité : 2 Pts
Proposition d’un calendrier : 1 Pt

Problème : (13 Pts)

1) 7 Pts
a) 2 Pts (1 + 1 justification)
b) Le parcours dupliqué : 1 Pt
Explication : 2 Pts
c) Longueur itinéraire : 1 Pt
Exemple d’itinéraire : 1 Pt

2) 6 Pts
a) * Arbre de poids minimum : 2 Pts
• Parcours à rénover : 1 Pts

b) 3Pts (1 +1 +1)