Exercice 1 :

Trois enseignants E1, E2, E3 devront donner Dimanche prochain un certain

nombre de séances de cours pour trois groupes C1, C2, C3:
E1 doit enseigner C1 pendant 2 heures et C2 pendant 1 heure;
E2 doit enseigner C1 pendant 1 heure, C2 pendant 1 heure et C3 pendant 1
heure;
E3 doit enseigner C1 pendant 1 heure, C2 pendant 1 heure et C3 pendant 2
heures.
Propose un graphe pour représenter cette situation? Quel est le type de
graphe?
Donner le nombre minimal des créneaux horaires?
En utilisant le graphe, proposer un emploi du temps
Solution
On remarque qu’on a deux sous ensembles de sommets les enseignants E et les groupes C,
toutes les relations (arêtes) relient un sommet de E avec un sommet de C, dans ce cas on un
graphe bi-parti.
On commence par relier les éléments de E avec les éléments de C avec des artes on obtient
le graphe suivant:
E1 C1 Le nombre max de créneaux horaires correspond au
nombre max d’heures que peut dispenser un
E2 C2 enseignant qui est le degré max des éléments de E
Max(d(Ei))=d(E3)=4; donc il ne faut quatre heures
E3 C3 dans notre emploi du temps.

On adopte la convention suivante:

E1 C1
1ère heure en rouge,2ème en vert, 3ème
en bleu et la 4ème en noir, on
commence par affecter la 1ère heure E2 C2
(arbitrairement) puis la 2ème, la 3ème et
enfin la 4ème comme dans le graphe à E3 C3
droite:
On obtient le planning suivant

E1 E2 E3
1ère heure(rouge) C1 C3 C2
2ème heure(vert) C1 C2 C3
3ème heure (bleu) C2 C1 C3
4ème heure (noir) C1
Exercice 2 :
On considère le graphe orienté G = (S, A) tel que
S = {1, 2, 3, 4, 5}, A = {(1, 2),(1, 4),(2, 2),(2, 3),(2, 4),(3, 5),(4, 3),(5, 3)}
1. Tracer le graphe G.
2. Donner le demi-degré extérieur de 2 et le demi-degré intérieur de 4,
3. Donner les sommets prédécesseurs de 4 et les sommets successeurs de 2,
4. Construire un graphe partiel et un sous-graphe de ce graphe.

1 3 5

4
 2 2

1 3 5 1 3 5

4 4

d +(2)=3 d -(4)=2
- arcs en rouge partants du sommet 2 arcs en bleu arrivants au sommet 4

2 2

1 3 5 1 3 5

4
4

Pred(4)={1,2}  sommets si tel que Succ(2)= {2,3,4}  sommets sj tel que

(Si,4)  A (2,Sj)  A

2
2
1 3 5
1 3 5
Exemple de sous graphe obtenu par la
4 suppression du nœuds 4 et par
Exemple de graphe partiel obtenu par la conséquent, tous les arcs ayant le nœud 4
suppression comme extrémité.
Des arcs: {(1, 4),(2, 2),(2, 4),(3, 5),(4, 3)}
Exercice 3 :
Dessiner un graphe non orienté complet à 4 sommets.
Quel est le degré des sommets de ce graphe ?
Combien d’arêtes possède-t-il ?
Généralisez ces résultats à un graphe simple complet ayant n sommets.

1 3 -Le degré de chacun des 4 sommets du graphe est 3

- Le graphe comporte 6 arêtes.
- Si on a n sommet d’un graphe complet, le degré de chaque
sommet est de n-1, chaque arête participe au degré de ses
2 4
extrémités et donc génère 2 degrés supplémentaires.
La somme des degrés de tous les sommets est de n(n-1).
Le nombre d’arêtes est déduit par |A|=n(n-1)/2 (puisque chaque
arête augmente la somme des degrés par 2.
N.B: la propriété |A=n(n-1)/2 des graphes simples complets peut
être prouvée par récurrence.
 Exercice 4:
- Donnez les représentations par matrice d’adjacence et listes d’adjacence du
graphe non-orienté (A) et du graphe orienté (B):

Graphe non orienté A Graphe orienté

Solution:
Pour les graphes non orientés, la matrice d’adjacence doit être forcément une matrice
carrée symétrique (aij=aji). Son rang est de NxN ou N est le nombre de sommets du
graphe. M(i,j)=M(j,i)=1 si aij  A, M(i,j)=M(j,i)=0 si aij  A. Pour la représentation par liste
d’adjacence on donne pour chaque sommet Si la liste des nœuds Sj tel que aij  A.

M 1 2 3 4 5
1 0 1 0 0 1
L1={2,5}
2 1 0 1 1 1 L2={1,3,4,5}
3 0 1 0 1 0 L3={2,4}
4 0 1 1 0 1 L4={2,3,5}
L5={1,2,4}
5 1 1 0 1 0
Pour les graphes orientés (comme B), la matrice d’adjacence n’est pas forcément
symétrique. Son rang est NxN ou N est le nombre de sommets du graphe.
M(i,j)=1 si aij  A, M(i,j)=0 si aij  A.
M 1 2 3 4 5 6
1 0 1 0 1 0 0
2 0 0 0 0 1 0
3 0 0 0 0 1 1 Graphe orienté
4 1 1 0 0 0 0
5 0 0 0 1 0 0
6 0 0 0 0 0 2
La représentation en listes d’adjacence se fait de la même manière (avec des arcs).

L(1)={2,4}
L(2)={5}
L(3)={5,6}
L(4)={1,2}
L(5)={4}
L(6)={6}
Exercice 5:
Montrer que le graphe suivant est eulérien

-Le degré de chacun des 4 sommets du graphe est 3

- Le graphe comporte 6 arêtes.
- Si on a n sommet d’un graphe complet, le degré de chaque
sommet est de n-1, chaque arête participe au degré de ses
extrémités et donc génère 2 degrés supplémentaires.
La somme des degrés de tous les sommets est de n(n-1).
Le nombre d’arêtes est déduit par |A|=n(n-1)/2 (puisque chaque
arête augmente la somme des degrés par 2.
N.B: la propriété |A=n(n-1)/2 des graphes simples complets peut
être prouvée par récurrence.
Exercice 6:
On considère le graphe non orienté suivant :

Combien faut-il enlever d’arêtes à ce

graphe pour le transformer en arbre
? Donnez un graphe partiel de ce
graphe qui soit un arbre.

Solution:
Soient |A| et |S| respectivement, le nombre
d’arêtes et de sommets d’un graphe G
G un graphe  |A|=|S|-1
Dans notre cas on a |S|=7, pour que G soit un arbre il faut que |A|=7-1=6
Et comme |A|=11 donc il faut enlever au minimum 11-6=5 arêtes.
Les deux graphes ci-dessous représentent deux graphes partiaux de G et qui
sont des arbres
Exercice 7:
Montrer que le graphe suivant est planaire :
- Solution:
-Le degré est planaire si n’a pas de mineurs (sous
graphe obtenu par fusion ou suppression de
sommets) isomorphe à K3,3 ou K5
-Le graphe ci-dessus n’a pas de sous graphe de
K3,3 du fait que son nombre de sommet est 5 (un
K3,3 est un graphe de 6 sommets),
- Le graphe n’est pas isomorphe avec K5 du fait
que l’arête ab est inexistante.
- Le graphe ci-dessus est donc planaire, en effet il
peut être redessiner comme suit:

Exercice 8:
Vérifiez la formule d’Euler dans le cas d’un arbre.
Solution:
Nombre de faces d’un arbre=1 (sans cycle) et le nombre d’arêtes= s-1,
f+s=1+(a+1)=a+2.
Exercice 9:
Montrez, en utilisant la
formule d’Euler que le graphe
suivant n’est pas planaire.

Solution:
f: nombre de faces, a: nombre d’arêtes et s: nombre de sommets
G est simle (pas d’arêtes multiples ni de boucles). Chaque face est délimitée au
moins de trois arêtes.
Si on compte f faces on va compter au moins 3f arêtes, certaines arêtes étant
communes, mais pas toutes(les isthmes). D'où l'inégalité:
3f<=2a …….. (1)
et comme f+s=a+2 (formule d’euler) on a f=a+2-s  3f=3a-3s+6 …. (2)
De (1) et (2) on a
3a-3s+6 <=2a  a+6<=3s …(3)
Pour le graphe (K5) de l’exercice on a=10 et s=5 on remplaçant dans (3) on
trouve
16<=15 (contradiction) donc K5 n’est pas planaire.
Exercice 10:
Est-il possible de dessiner sans
lever la main un lacet (cordon)
qui traverse chaque arête de
ce graphe planaire une et une
seule fois ?

Solution:
Considérons le graphe G’ obtenu comme suit:
- À chaque face fi de G correspond un sommet si dans G’
- À chaque arête de G frontière entre entre deux faces fi et fk correspond
une arête aik reliant les sommets si et sk

Traverser toutes les arêtes de G

revient à trouver une chaine
Eulérienne dans G’ or on a 4
sommets de G’ de degré impair
(1,2,3 et 5) donc pas de chaine
Eulérienne et le problème n’admet
pas desolution,
Exercice 11:
5 étudiants (Dupont, Dupond, Durand, Duval et Duduche) doivent passer
certains examens. Les examens que doivent passer chaque étudiant sont
récapitulés dans le tableau suivant :
Dupond Français, anglais, mécanique
Dupont Dessin, Couture
Durand Anglais, Solfège
Duval Dessin, Couture, Mécanique
Duduche Dessin, Solfège

On désire que tous les étudiants devant subir une même épreuve le fassent
en même temps. Chaque étudiant ne peut se présenter qu’à une épreuve
au plus par jour. Quel est le nombre minimal de jours nécessaires à
l’organisation de toutes les épreuves ?

Solution:
Solution (11):
Après représentation par graphe, le problème revient au coloriage de ce
graphe (trouver le nombre chromatique) qui est de 3
Dupond Francais

Dupont Anglais

Durand Mécanique
Duval
Dessin
Duduche
Couture

Solfège
Exercice 12:
Trouvez les plus courts chemins partants de A (à partir de A):
Solution 12:
D(i): Distance depuis le nœuds initial (ici le nœud A) vers le nœud i
P(i) : Prédécesseur de i qui offre la meilleure distance D(i) à une étape donnée,

Rappels: Principe de l’algorithme de Dijkstra

1- On part avec l’ensemble N={A} (le nœud qu’on veut calculer les chemins les plus courts
avec les autres), pour tous les autres nœuds on ini alise leurs distances D à ∞ et leur
prédécesseur à néant (le tiret -)
Itérations:
2- On choisi un nœud i qui n’appartient pas à l’ensemble N et avec le minimum de
distance D(i) et on le met dans N
3- Pour tous les successeurs de i: Mettre à jour les distances et les prédécesseurs comme
suit: soit j un successeur de i
D(j)=min (D(j), D(i)+W(i,j)) W(i,j) est le poid de l’arête a(i,j),
Si D(i)+W(i,j)<D(j) alors P(j)=i
4-Répéter 2 et 3 jusqu’à ce qu’il ne reste aucun nœud de G non inclus dans N

On appliquant l’algorithme sur le graphe G on obtient le tableau ci après:

Etape N D(A), D(B), D(C), D(D), D(E), D(F), D(G), D(H),
P(A) P(B) P(C) P(D) P(E) P(F) P(G) P(H)
Initialisatio {} 0,- ∞,- ∞,- ∞,- ∞,- ∞,- ∞,- ∞,-
n
Etape 1 {A} 7,A ∞,- ∞,- 14,A ∞,- ∞,- ∞,-

Etape 2 {A,B} 15,B ∞,- 14,A ∞,- ∞,- ∞,-

Etape 3 {A,B,E} 15,B ∞,- 33,E ∞,- ∞,-

Etape 4 {A,B,E,C} 21,C 33,E ∞,- ∞,-

Etape 5 {A,B,E,C,D} 33,E ∞,- ∞,-

32,D
Etape 6 {A,B,E,C,D,F} 36,F 45,F

Etape 7 {A,B,E,C,D,F,G} 45,F

44,G
Exercice 13: Trouver les plus courts chemins à partir de A (Algorithme de Bellman-
Ford)

A B C D E

V0 0 ∞ ∞ ∞ ∞

V1 0 -1 4 ∞ ∞

V2 -1 4 1 1
2
On a V4=V3 donc on arrive à la fin,
V3 -1 2 1 1
-2
V4 -1 2 -2 1
Exercice 14: Appliquer l’algorithme de Kruskal pour construire un arbre couvrant
de poids minimal
Exercice 15: Déterminer le flot maximal à partir du graphe de flot ci-dessous
(Algorithme de Ford-Fulkerson)