ESI /2021-2022 1 CS/ ROP

Série d’Exercices n°1

MODÉLISATION

Exercice 1:
Le conseil municipal d'une ville comprend 7 commissions, qui obéissent aux règles
suivantes: Règle 1 : tout conseiller municipal fait partie de 2 commissions exactement.
Règle 2 : deux commissions quelconques ont exactement un conseiller en commun;
Modéliser cette situation à l’aide d’un graphe pour savoir combien y a-t-il de membres dans
le conseil municipal ?

Exercice 2
Construire un graphe orienté dont les sommets sont les entiers compris entre 1 et 12 et dont
les arcs représentent la relation « être diviseur de »

Exercice 3 :
Il existe quatre groupes sanguins :
- AB pour les personnes ayant des antigènes A et B,
- A pour les personnes ayant des antigènes A mais pas d’antigènes B,
- B pour les personnes ayant des antigènes B mais pas d’antigènes A,
- O pour les personnes n’ayant ni d’antigènes A ni d’antigènes B.
Il existe également deux rhésus sanguins :
- positif (+),
- négatif (-).
On admet que les seuls interdits biologiques pour recevoir du sang sont les suivants :
- recevoir du sang possédant un antigène dont on est dépourvu,
- recevoir du sang ayant un rhésus positif si on est rhésus négatif.
a) Tracer le graphe orienté représentant les possibilités de dons de sang sans violer les
interdits biologiques.

NOTIONS GÉNÉRALES DE LA THÉORIE DES GRAPHES

Exercice 4
1. Donner les matrices d’adjacence, d’incidence, et la
liste d’adjacence du graphe suivant.
2. Déterminer le degré de chacun de ses sommets.
3. Quel est le type de ce graphe?

Exercice 5
On reprend le graphe de l’exercice 3 (Groupes sanguins). Soit G le graphe obtenu.
a) Donner la matrice d’adjacence et la matrice d’incidence de G.
b) Donner le demi-degré sortant d+(v) et le demi-degré entrant d-(v) de chaque noeud v.
c) Donner l’ensemble des successeurs succ(v) et l’ensemble des prédécesseurs préd(v)
de chaque nœud v.
d) Que représente la liste des successeurs (resp. prédécesseurs) de chaque sommet.

1/6
ESI /2021-2022 1 CS/ ROP
Série d’Exercices n°1

Exercice 6
Soit G=(X,E) un graphe non orienté et simple :
1. Montrer que :∑ ( ) | |
2. En déduire que le nombre de sommets de degré impair est pair.
3. Supposons que G a 15 arêtes, 3 sommets de degré 4 et tous les autres de degré 3.
Quel est l’ordre de ce graphe?
4. Est-il possible d’avoir un groupe de 9 personnes telles que chaque personne soit
compatible (d’humeur) aves exactement 5 personnes de ce même groupe.
5. Lors d’une réception dans laquelle il y a au moins deux personnes, toutes les personnes
qui se connaissent se sont serré la main. Montrer qu’il existe deux personnes qui ont
serré la main au même nombre de personnes.
6. Montrer que ∑ ( ) ∑ ( ) (G est un graphe orienté et simple).

Exercice 7
On s’intéresse aux graphes dont tous les sommets sont de degré trois.
1. Construisez de tels graphes ayant 4 sommets, 5 sommets, 6 sommets, 7sommets.
2. Qu’en déduisez-vous ? Prouvez-le!

Exercice 8
Peut-on construire un graphe simple ayant :
a) 4 sommets et 7arêtes b) 5 sommets et 11arêtes c) 10 sommets et 46 arêtes?

Exercice 9
a) Construire le graphe biparti complet K2,3 et compter son nombre d’arêtes.
b) Combien le graphe biparti complet Km,n possède-t-il d’arêtes ? (m; n = 1)
c) Construire le graphe triparti complet K2,3,2 et compter son nombre d’arêtes.
d) Combien le graphe triparti complet Kl,m,n; possède-t-il d’arêtes ? (l, m , n = 1)

Exercice 10
On appelle un graphe simple non orienté « k-régulier » si tous ses sommets sont de degré k.
Pour chacun des graphes simples non orientés suivants, donner un exemple d’existence
ou prouver l’inexistence.
a) Un graphe biparti 3-régulier de 8 noeuds
b) Un graphe biparti 4-régulier de 11 noeuds.

Exercice 11
On considère la matrice A=  0 11 0 1 
 
 1 0 111 
 11 0 1 0 
 
 0 11 0 0 
 11 0 0 0 
 
Les graphes ci-dessous peuvent-ils être associés à A ? Dans les deux cas, expliquer pourquoi.

2/6
 ESI /2021-2022 1 CS/ ROP
Série d’Exercices n°1

NOTIONS : CONNEXITÉ ET COMPOSANTES FORTEMENT CONNEXES, DISTANCE,

DIAMETRE

Exercice 12
Etant donné un groupe de dix personnes, le tableau suivant indique les paires de
personnes qui ont une relation d'amitié.

I 1 2 3 4 5 6 7 8 9 10
amis de i 3,6,7 6,8 1,6,7 5,10 4,10 1,2,3,7 1,3,6 2 4,5
1. Représenter cette situation par un graphe d'ordre 10 dans lequel une arête entre les
sommets i et j signifie qu'il y a une relation d'amitié entre i e j.
2. Ce graphe est-il complet ? est-il connexe ? justifier
3. Si l'adage "les amis de nos amis sont nos amis" était vérifié, que pourrait-on en
conclure sur la structure du graphe?

Exercice 13
1. Quel est le diamètre du graphe ci-contre?
2. Combien d'arêtes (et lesquelles) faut-il enlever pour que son
diamètre soit de 3?

Exercice 14
1. Quels sont les graphes de diamètre 1?
2. Donner les diamètres des graphes ci-dessous.

Exercice 15
Deux maires souhaitent refaire la peinture des quartiers
de leurs communes respectives. Les quartiers reliés par
un circuit doivent être peints avec la même couleur
Quel est le nombre de couleurs que chaque maire doit
utiliser ?

3/6
 ESI /2021-2022 1 CS/ ROP
Série d’Exercices n°1

Exercice 16
1. Trouver les composantes fortement connexes du graphe orienté suivant en utilisant
l’algorithme de Tarjan:

Considérons maintenant le graphe simple non orienté associé en remplaçant les arcs par des
arêtes.
2. Le graphe obtenu est-il connexe?
3. Expliquer comment trouver les composantes connexes en utilisant le même algorithme.

NOTIONS : COLORATION DE GRAPHES

Exercice 17
Le schéma suivant représente un carrefour. Le tableau suivant précise les franchissements»
possibles de ce carrefour. (La circulation de A vers E est considérée comme un
franchissement» même si on ne traverse pas le carrefour).

Les franchissements AC et BE ainsi que les franchissements AE et BE

ne peuvent pas être autorisés simultanément sous peine de collision.
En outre, les franchissements AD et DA sont autorisés.

1. Modélisez cette situation à l’aide d’un graphe dont:

a. Les sommets représentent les franchissements possibles
b. Les arêtes reliant les sommets représentant des franchissements ne
peuvent pas être simultanées sous peine de collision.
2. Proposer une coloration du graphe du graphe obtenu. En déduire son nombre
chromatique. Que représente ce nombre ( par rapport au problème du carrefour)

Exercice 18 ( CC 2017)
Le sudoku, est un jeu en forme de grille défini en 1979 et inspiré du carré latin ainsi que du
problème des 36 officiers du mathématicien suisse Leonhard Euler. Le but du jeu est
de remplir une grille avec des chiffres en respectant certaines contraintes, quelques
chiffres étant déjà disposés dans la grille. Dans sa version la plus répondue, cette
grille de jeu est un carré de neuf cases de côté, subdivisé en autant de carrés
identiques, appelés régions. La règle du jeu est simple : chaque ligne, colonne et

4/6
 ESI /2021-2022 1 CS/ ROP
Série d’Exercices n°1

région ne doit contenir qu'une seule fois tous les chiffres de un à neuf.
Nous voulons modéliser ce jeu à l’aide d’un graphe afin de résoudre n’importe quelle grille
donnée.
a- Proposer une modélisation pour le cas d’un jeu de 4 case/ 4 chiffre (voir la grille ci-
contre) par un graphe.
b- La résolution de ce jeu revient à la résolution de quel problème de la théorie des graphes.
c- Proposer un (ou plusieurs) algorithme(s) de résolution
d- Déduire comment peut-on procéder pour résoudre n’importe quelle grille donnée (sans
déroulement l’idée suffit)

Exercice 19 (CC 2019)

On veut organiser un planning d’examen comportant, outre les matières communes, six autres
matières optionnelle : Français (F), Anglais (A), Mécanique (M), Dessin industriel (D),
Informatique (I) , Sport (S). Les profils des candidats à option multiple sont : F-A-M, D-S, I-S, et
I-M.
1. Modélisez cette situation par un graphe, en définissant les sommets et les arêtes.
2. Quel est le nombre maximum d’épreuves qui peuvent se dérouler en parallèle? Justifiez
votre réponse.
3. Quel est le nombre maximum d’épreuves qui ne peuvent pas se dérouler en parallèle?
Justifiez votre réponse
4. En supposant qu’une épreuve dure une demi-journée, et que les épreuves commencent
dimanche matin, proposez un planning d’examen utilisant un nombre minimal de plages
horaires.
5. On veut planifier uniquement l’épreuve de sport dans la dernière plage horaire. Ceci est-
t-il possible ? justifiez votre réponse.

Exercice 20
1. Quel est le plus grand nombre de sommets adjacents deux à deux dans ces graphes?
2. Trouver quand il est possible le nombre minimum de couleur nécessaire pour colorer ces
graphes?

Exercice 21
Un concert de solidarité est organisé dans une grande salle de spectacle. A ce concert sont
conviés sept artistes de renommée internationale : (A), (B), (C), (D), (E), (F) et (G).
Les différents musiciens invités refusant de jouer avec certains autres, l'organisateur
du concert doit prévoir plusieurs parties de spectacle. Les arêtes du

5/6
 ESI /2021-2022 1 CS/ ROP
Série d’Exercices n°1

graphe Γ ci-dessous indiquent quels sont les

musiciens qui refusent de jouer entre eux.
1. Quelle est la nature du sous-graphe de Γ
constitué des sommets A, E, F et G?
2. Que peut-on en déduire pour le nombre
chromatique (χ) du graphe Γ?
3. Quel est le sommet de plus haut degré de Γ ?
En déduire un encadrement de (χ).
4. Quel est le sommet de plus haut degré de Γ
? En déduire un encadrement de (χ).
5. Après avoir classé l'ensemble des sommets
de Γ par ordre de degré décroissant, colorier le grap
6. Combien de parties l'organisateur du concert
doit-il prévoir?
7. Proposer une répartition des musiciens pour chacune de ces parties.

NOTIONS : ARBRES ET ARBORESCENCE

Exercice 22
Appliquer l’algorithme de Prim, puis de kruskal au
graphe suivant pour trouver un arbre couvrant de
poid minimum.

Exercice 23
Appliquer l’algorithme de Prim (en commençant par le sommet x)
puis de kruskal au graphe suivant pour trouver un arbre couvrant de
poid minimum.

Exercice 24
Soit le graphe G = (V, U) suivant qui présente un réseau de connexion entre un ensemble des villes.

Soit G1 le graphe non orienté correspondant à G.

Un Fournisseur d’Accès à Internet (FAI) veut
installer un nouveau réseau très haut débit à
moindre coût sur ce réseau (G1). Si le poids des
arêtes représente le coût d’installation de liaison
entre deux villes :
1. Quel est le problème formel associé à la
nouvelle installation?
2. Donner la structure du nouveau réseau ainsi
que le coût d’installation correspondant

6/6
 ESI /2021-2022 1 CS/ ROP
Série d’Exercices n°1

Exercice 25
1. Montrer que dans un arbre la moyenne des degrés est < 2
2. Montrer que le graphe obtenu à partir d’un arbre, en supprimant ou en rajoutant un sommet
pendant est aussi un arbre
1. Montrer que si toutes les évaluations des arêtes d’un graphe sont distinctes, alors il possède un
unique arbre couvrant de poids minimal

Exercice 26
Pour chacun des graphes suivants :

1. Trouver un arbre couvrant de poids maximum (resp. minimum), en utilisant l’algorithme de Prim
en partant du sommet x. L’arbre trouvé est-il unique.
2. Trouvez tous les arbres couvrants de poids maximum (resp. minimum) en utilisant l’algorithme de
Kruskal.

7/6