Ecole Nationale Polytechnique Année universitaire : 2023/2024

2ème année Cycle Préparatoire Durée : 02 heures

Examen Final Informatique3

11 Janvier 2024

Remarque : 1- Toutes les réponses doivent être soignées et justifiées.

Partie 01 (1 5 points)
Un réseau de transport typique offre plusieurs options à un usager pour effectuer un déplacement entre
une origine et une destination. Avant d’effectuer un déplacement, le voyageur doit prendre une décision de
choix afin de trouver l’option la plus adéquate pour arriver à sa destination. En revanche, les choix de
déplacement déterminent l’état du trafic. L’état de trafic est donc un résultat des comportements des voyageurs
dans les axes du réseau. Un modèle d’affectation de voyage doit reproduire la répartition de la demande sur le
réseau qui se compose d’une part de l’infrastructure routière, des lois d’écoulement du trafic et d’autre part par
la demande de transport ainsi que le choix des usagers et les actions d’exploitation.
Dans un tel modèle, on représente le système de répartition du trafic comme un graphe de déplacement
dont on représente l’infrastructure et l’ensemble des mesures d’exploitation comme étant l’offre. Les modèles
de déplacement consistent à trouver comment les usagers choisissent leurs options de déplacement en
considérant les conditions du trafic.
Le but principal de cette étude est de voir comment fluidiser les routes et les rues et faire la gestion de
l’écoulement, la distribution, et le déplacement des usagers d’une manière optimale de l’ensemble des
véhicules à travers un ensembles de chantiers qui seront établis sur le territoire national en prenant un
échantillonnage sur la ville d’Alger.

Exercice 01 (07.00)
I. Initialement, la société qui s’occupe des différents
travaux voudrait ouvrir huit chantiers, libellés A à H
dont les différentes distances, en kilomètres, sont
données par le graphe ci-contre.

a. Donner la matrice d’incidence et le degré de

chaque sommet.
b. Quelle est la relation des degrés des sommet
avec les valeurs de la matrice d’incidence ?

Figure 01. Réseau des chantiers.

Solution :
a. La matrice d’incidence (0.50 pt), les degrés (0.50 pt).
b. La somme des éléments de la même ligne représente le degré d’un sommet. (0.50 pt).

II. Dans un réseau des chantiers déjà établi dans la question précédente, chaque chantier envoie et reçoit
des travailleurs. Pour éviter tout conflit et toute erreur lors de l’envoie et la réception de ces travailleurs
sur le réseau, la société a décidé de ne pas allouer le même nombre des travailleurs à deux chantiers
trop proches l’un de l’autre, c’est-à-dire que deux chantiers à moins de 35 km fonctionnent avec des
nombres de travailleurs différents. De plus, le coût de gestion des chantiers est une fonction croissante
du nombre de travailleurs fixé, ainsi à cause de contraintes financières, il est intéressant de minimiser
le nombre de fréquences allouées.

1
 a. Donner une description à cette problématique.
b. Proposer une solution.
c. Quel est le nombre des catégories des travailleurs allouées au réseau (c’est-à-dire est le
d. Nombre des nombre utilisés à chaque groupe de travailleurs).
Solution :

1. Il ne faut pas allouer le même nombre de travailleurs à deux chantiers à moins de 35 km =>
Deux chantiers d’au moins de 35 km doivent avoir deux
nombre différents (0,25 pt)

2. => problème de coloration de graphe. (0,25 pt)

3. Choisir les chantiers dont la distance est <= 35

km Les Sommets=> relais
Les arêtes => les liaisons inférieur à 35
Minimiser le nombre de travailleurs alloués aux différents chantiers(0,5 pt)
revient à minimiser le nombre de couleurs= Nombre chromatique.

III. Le dessin ci-dessous représente le positionnement des différentes communes d’Alger et qui sont
concernés par les travaux dont la société veut effectuer.

a) Les travailleurs souhaitent effectuer leurs travaux en visitant les communes et en franchissant chaque
frontière une fois et une seule, sans passer par la mer. Est-ce possible ? De quel commune peuvent-ils
partir? Peuvent-ils revenir à leurs points de départ ? Modélisez d'abord le problème en termes de
graphes (c'est-à-dire définissez un graphe et traduisez les questions par rapport à ce graphe), puis
répondez aux questions.

b) On veut colorier la carte de façon que deux régions ayant une frontière commune n'aient pas la
même couleur. Quel est le nombre minimal de couleurs qu'il faut utiliser ? Donnez une façon de
colorier la carte.

Figure 02. Les différents commune d’ALGER.

Solution :
1) On modélise la situation par un graphe dont les sommets sont les communes, et il y a une arête
entre deux communes s'ils ont une frontière commune. On obtient le graphe G ci-dessous. Les
questions se traduisent par : existe-t-il un chemin eulérien dans G ? De quel sommet ce chemin peut-
il partir ? ce chemin peut-il être fermé (autrement dit, est-ce un cycle eulérien) ?
On constate que G contient uniquement 2 sommets de degré impair : B et D. De plus, l'algorithme
de distance en partant de D donne les étiquettes suivantes :
D (0), C (1), E (1), H (1), I (1), J (1), K (1), A (2), B (2), G (2), L (2), F (3).
Tous les sommets ont une étiquette, donc G est connexe.
Par le théorème d'Euler, G a un chemin eulérien d'extrémités B et D, et pas de cycle eulérien.
Conclusion : on peut franchir chaque frontière une fois et une seule, en partant de B ou de D. On ne
peut pas revenir au point de départ. (01.00)

2
 2) On modélise la situation par le même graphe qu'en a). La question devient : quel est le nombre
chromatique de G ? Les sommets A, B, C, G forment un sous-graphe complet à 4 sommets, donc
nb couleur de (G) >= 4. De plus, le coloriage à 4 couleurs ci-dessus montre que nb couleur de (G)
<= 4. On en déduit que nb couleur de (G5) = 4.
Conclusion : il faut utiliser au minimum 4 couleurs pour colorier la carte. On peut la colorier ainsi :
• couleur 1 (rond noir) : C, F, I, L,
• couleur 2 (carr_e noir) : B, H, J, E
• couleur 3 (triangle noir) : A, D,
• couleur 4 (carr_e blanc) : G, K
0.25 + 0.75 =01.00
IV. Démonstration :
1. Considérons T un graphe partiel de G qui soit un arbre et supposons
que dans T, Les degrés des sommets sont soit 3 ou 1.
Si T a 10 sommets de degré 3, combien de sommets de degré 1 a-t-il ?
2. Montrer qu’un graphe G contient un arbre couvrant si et seulement si G est connexe.
Solution:
Commençons par deux rappels. On sait qu’un arbre ayant s sommets possède exactement s − 1 arêtes. On sait
aussi qu’un graphe connexe possède un sous-arbre couvrant. En particulier, un graphe connexe à n sommets
possède au moins n − 1 arêtes.

1. 10 sommets de degrés 3, x sommets de degrés 1.

3 × 10 + 𝑥 = 2(10 + 𝑥 − 1) (0,5 pt) 𝑎𝑙𝑜𝑟𝑠 30 + 𝑥 = 18 + 2𝑥
D’où 𝑥 = 12 (0,5 pt )

2. Soit t le nombre de composantes connexes de G. On sait déjà que t ≥ 2. Soient n1 , . . . , nt , les nombres de
sommets appartenant respectivement aux différentes composantes connexes. On a n = n 1 + · · · + nt . Pour
répondre à la question, supposons qu’aucune composante n’est un arbre (on procède par l’absurde). Ainsi, pour
tout i, la i-ième composante contient au moins n i arêtes (s’il s’agissait d’un arbre, on en aurait n i −1). Le
nombre total d’arêtes n−1 est la somme des nombres d’arêtes des différentes composantes. On en tire n − 1 ≥
n1 + · · · + nt = n qui est absurde. Autrement dit, au moins une des composantes est un arbre. (01.50)

Exercice 02 (02.50)
Les différents chantiers doivent échanger des
informations en eux. Pour cela, la compagnie désire
entreprendre un réseau informatique pour
l’acheminement des données sur le réseau modélisé ci-
dessous, de la station A à la station H en un temps
minimal, Où le coût des arcs représente le temps en
milliseconde (ms).

1. Donner une description à cette problématique.

2. Comment résoudre ce problème ?
3. Quel est la durée de ce routage ? Figure 03. Réseau des Stations.

3
Solution :
1 . Acheminer des données sur le réseau, de la station A à la station H en un temps minimal (0,25 pt)
est une problématique du chemin le plus court.

2 . Pour le résoudre appliquer l’algorithme de Dijkstra ou celui de Bellman Ford. (0.25 pt)
Le tableau (1.00 pt)
A B C D E F G H Sommet fixé Lmin
0 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ A 0
1 A3 A2 ∞ ∞ ∞ ∞ ∞ C 2
2 A3 6C ∞ ∞ ∞ ∞ B 3
3 5B 3B 5B ∞ ∞ E 3
4 5B 5B ∞ ∞ D 5
5 5B 9D ∞ F 5
6 6F 7F G 6
7 7F H 7
3. Durée de ce routage 7 mss ABFH (on a H FBA) (0.50 pt)
4. Il était possible si le graphe était orienté en appliquant l’algorithme de Bellman-ford, mais puisque
le graphe est non orienté, on ne peut pas. (0.50 pt)

Exercice 03 (04.25)
Parmi les projets établis par la société qui prend en
charge les différents travaux est la construction
d’autoroutes. L’entreprise étudie la capacité du réseau
routier, représenté par le graphe ci-contre, reliant la
ville E à la ville S. Pour cela, elle a évalué le nombre
maximum de véhicules qui peuvent passer par une
route par heure. Ces évaluations (capacité) sont
données en centaines de véhicule par heure.

1. Compléter le flot initial donné sur le graphe et

quel est la valeur de ce flot.
2. Est-ce que le flot initial est maximal ? justifier. Sinon, en Figure 04. Travaux de la
utilisant le flot initial précèdent comme flot de départ pour construction.
l’algorithme de Ford-Fulkerson, calculer le débit horaire
maximal de véhicules susceptibles de s’écouler entre les villes E et S ?
3. Calculer et tracer la coupe de capacité minimale du réseau et comparer la valeur de celle-ci à la valeur
du flot maximal circulant entre E et S. Qu’en déduisez-vous ?

Solution :

1. (a, c) : (7,0), (c,R) : (7,7) , (d,R) : (4,1) , (b,d) : (2,2) , (d,f):(2,2), (b,e): (1,1), (R,s): ( 10, 8) (Avec
explication bien sûr). (7* 0.25 = 1.75)
2.

4
Le flot initial est représenté sur le graphe ci-dessous.
On remarque le flot qui passe est flot complet car chaque chemin contient au moins une arrête saturé.
La valeur du flot complet est 20 véhicule/heure.
Donc, on va vérifier si ce flot est max ou non à travers l’étape de marquage.

Après marquage, on pourra constaté que le sommet puit (S), donc, le flot complet n’est pas max. (0.25)
La chaine utilisé pour marquer le sommet S est : E-e-b-c-d-R-S

La valeur de cette chaine est :

epsilon + = min{(8-5), (8-7), (1-0), (4-1), (10-8)}= 1

epsilon - = min{(1-0)} = 1

epsilon = min{ epsilon + , epsilon - }= 1

Après le rajout de la valeur de la chaine améliorante et un deuxième marquage, on obtient le réseau ci-
dessous :

5
 Le puit n’est plus marqué, donc le flot est max et sa valeur est 21. (01.00)

3. La coupe min est entre les sommets marqué est les sommets nom marqués est sa valeur est égale à
21. Les arcs concernés sont : (E,a), (E,b), (e,d), (e, f). (01.00)
La conclusion : la valeur de la coupe min représente la valeur du flot max.

4. Non ((0.25)

Exercice 04 (02.50)

L’Algérie a décidé d’exploiter une des iles qui sont près de la capitale ALGER. Cette exploitation concerne
l’aménagement de cette ile pour la culture du riz.
L’aménagement voulu sera réalisé par la même société qui
s’occupe des différents travaux précédents.
Sur cette ile se trouvent 9 champs entourés de murs et
disposés de la façon ci-contre.
La culture du riz suppose que l’on puisse périodiquement
inonder l’ensemble des champs. Cela est réalisé en ouvrant
des vannes placées dans les murs séparant les champs et le
Rhône ou les champs entre eux. Etant donné que l’installation
d’une vanne est couteuse :
Déterminer le nombre minimum de vannes et leur emplacement pour Figure 05. Les 09 champs entourés
pouvoir, quand on le désire, inonder tous les champs. de murs.

6
Solution :
Pour résoudre ce problème, on peut également considérer le graphe non orienté comportant un sommet pour
chaque champ plus un sommet représentant la méditerrané. Ce graphe comporte une arête entre deux
sommets si les champs correspondants, ou la méditerrané, sont voisins. (0,5 pt )
On obtient alors le graphe suivant : (0,5 pt )

La méditerrané

Le problème revient à chercher un graphe partiel connexe sans cycle donc un arbre couvrant (0,5 pt ). L’arbre
devra comporter 10-1=9 arêtes donc on doit installer 9 vannes (0,5 pt ). L’arbre couvrant est le suivant :
Le graphe (0,5 pt )

La méditerrané

Partie 02 (0 4 points)

Une société va ouvrir un marché « puces et brocante » sur un terrain. Il y a délimité 240 emplacements.
L'installation des exposants commencera à 6 h, le dernier exposant devra avoir fini de s'installer à 8 h. elle
prévoit que chaque exposant arrivant :

• avec une voiture, paiera 10 euros de redevance et disposera de quatre emplacements pour installer son
stand,
• avec un fourgon, paiera 16 euros de redevance et disposera de six emplacements.
Il faut en moyenne 1 min à une voiture pour se garer et 4 min à un fourgon.

7
Pour des raisons de sécurité, chaque exposant ne peut commencer à se garer que lorsque le précédent a fini de
se garer.

La société souhaite déterminer le nombre de voitures et le nombre de fourgons nécessaires pour que sa recette
soit maximale.

1. Formuler le programme linéaire correspond à ce problème.

2. Résoudre le programme avec les deux méthodes (graphique et algébrique) en comparant les résultats
obtenus.

Solution :

1. x et y sont les nombres de voitures et de fourgons, donc x >= 0 et y >= 0. (0,25 pt).
De plus, chaque exposant arrivant avec une voiture dispose de quatre emplacements, et ceux arrivant en fourgon
en disposeront de six. Il y en a 240, donc 4x + 6y <= 240.
En deux heures, soit 120 minutes, les exposants s'installent. Une voiture met une minute, et un fourgon en met
quatre, donc x + 4y <= 120.
Donc le système des contraintes est : (0,50 pt).

MAX Z = 1000x + 1600y (0,25 pt).

Le graphique est sur (0.5 pt)

La recette maximale est donnée avec x = 24 et y = 24. (0.50)

La méthode du simplex est sur 2. 00 pts