Université Kasdi Merbah Ouargla Année universitaire : 2022-2023.

FNTIC Niveau : 2 ème année Licence.

Département de l’ITI Module : Théorie des graphes.

Examen Durée : 1 h 45

Nom : Num d’inscription :

Prénom : Section : Groupe :

Exercice 1 (4 points)
On considère le graphe pondéré suivant avec les poids sur les arêtes:
1) Donner l’arbre couvrant de poids minimum en appliquant
au choix l’un des algorithmes de recherche d’un arbre
couvrant de poids minimum (Kruskal ou Prim).
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
[1/4]
Exercice 2 (6 points)
Soit le graphe orienté G présenté par la figure ci dessous :
1) Donnez la matrice d’adjacence correspondante de G.
...........................................................................................................
...........................................................................................................
...........................................................................................................
...........................................................................................................
...........................................................................................................
........................................................................................................... G

2) Donner la représentation machine (tables des successeurs) correspondante de G.

..............................................................................................................................................................................
..............................................................................................................................................................................
..............................................................................................................................................................................
..............................................................................................................................................................................

3) Est-ce qu’il existe une relation de forte connexité entre le sommet 2 et le sommet 4? Justifiez votre réponse.
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
4) En appliquant l’algorithme de décomposition, décomposer le graphe G suivant en composantes fortement
connexes. Donner le graphe réduit.
..............................................................................................................................................................
..............................................................................................................................................................
..............................................................................................................................................................
..............................................................................................................................................................
..............................................................................................................................................................
..............................................................................................................................................................
..............................................................................................................................................................
..............................................................................................................................................................
..............................................................................................................................................................
..............................................................................................................................................................
..............................................................................................................................................................
..............................................................................................................................................................
[2/4]
 ..............................................................................................................................................................
..............................................................................................................................................................
..............................................................................................................................................................
..............................................................................................................................................................
Exercice 3 (5 points)
Considérons un ensemble de 5 villes nommées V1, V2, V3, V4, et V5. Les tronçons de routes reliant les villes sont
représentées par la matrice suivante telle que la case située à l'intersection de la ligne i et de la colonne j contient
un entier égal à la longueur en kilomètres du tronçon de route reliant la ville Vi avec la ville Vj (on suppose que les
routes sont en sens unique). Une case vide veut dire qu’il n’existe pas de route entre les deux villes.
1) Représenter au moyen d'un graphe cette situation (représentation graphique).
V1 V2 V3 V4 V5
..............................................................................................................................................................................
8 10
V1
5 12 20
..............................................................................................................................................................................
V2
V3 19
..............................................................................................................................................................................
V4 14 11
..............................................................................................................................................................................
V5
..............................................................................................................................................................................
..............................................................................................................................................................................
..............................................................................................................................................................................
..............................................................................................................................................................................
2) En utilisant le graphe obtenu, est il possible de partir de la ville V1 et d’y revenir en passant par chaque ville
une et une seule fois ? à quoi correspond la solution en termes de concepts liés à la théorie des graphes ?
Justifier Votre réponse.
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
3) Quel est le chemin le plus court qui relie la ville V1 avec toute les autres villes? (Utiliser l'algorithme le mieux
adapté). Justifier votre choix.
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
[3/4]
 ................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
Exercice 4 (5 points)
1. Soit G un graphe connexe eulérien.
a) Est-il toujours possible de rendre G non eulérien en lui enlevant des arêtes ? Justifiez votre réponse.
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
b) Combien d’arêtes au minimum doit-on enlever de G pour le rendre non Eulérien. Justifiez votre réponse.
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
2. Est-il possible de construire un graphe simple avec 6 sommets et 21 arêtes ? Justifier.
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
3. Est-il possible de construire un graphe 5-régulier avec 8 sommets ? Justifier.
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
................................................................................................................................................................
[4/4]
Université Kasdi Merbah Ouargla Année universitaire : 2022-2023.
FNTIC Niveau : 2 ème année Licence.
Département de l’ITI Module : Théorie des graphes.

Examen Durée : 1 h 45

Nom : Num d’inscription :

Prénom : Section : Groupe :

Exercice 1 (4 points)
On considère le graphe pondéré suivant avec les poids sur les arêtes:
1) Donner l’arbre couvrant de poids minimum en appliquant
au choix l’un des algorithmes de recherche d’un arbre
couvrant de poids minimum (Kruskal ou Prim).
Solution

Prim (0.5+2+ 1.5)

S←{1} ; P(T) ←0 ; X←φ;

S={1} : uv=13, X←X∪{13}, p(T) ← p(T)+ p(13)=0+4=4, S←S∪{3}
S={1, 3} : uv=36, X←X∪{36}, p(T) ← p(T)+ p(36) =4+1=5, S←S∪{6}
S={1, 3,6} : uv=64, X← X∪{64}, p(T) ← p(T)+ p(64) =5+7=12, S←S∪{4}
S={1, 3,6, 4} : uv=45, X← X∪{45}, p(T) ← p(T)+ p(45) =12+4=16, S←S∪{5}
S={1, 3,6, 4, 5} : uv=42, X← X∪{42}, p(T) ← p(T)+ p(42) =16+6=22, S←S∪{2}
S={1, 3,6, 4, 5,2} : uv=57, X← X∪{57}, p(T) ← p(T)+ p(57) =22+9=31, S←S∪{7}
S={1, 3,6, 4, 5,2,7} = V ⇒ fin de l’algorithme.
T=(S, X) avec S={1, 2, 3, 4, 5, 6, 7} et X={13, 36, 64, 45, 42 57}

Kruskal (0.5+2+ 1.5)

ei e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11 e12

(x,y) (3,6) (1,3) (4,5) (2,4) (4,6) (2,5) (5,7) (6,7) (2,3) (3,4) (1,2) (6,5)
P(ei) 1 4 4 6 7 8 9 10 11 12 12 13

X ←∅ ; i ←1; P(T) ←0 ;
i=1 : (V, X∪{e1}) est acyclique alors X ← X ∪{e1}; P(T)←P(T)+1=1; i←i+1 ;
i=2 : (V, X∪{e2}) est acyclique alors X ← X ∪{e2}; P(T)←1+4=5; i←i+1 ;
i=3 : (V, X∪{e3}) est acyclique alors X ← X ∪{e3}; P(T)←5+4=9; i←i+1 ;
[1/6]
i=4 : (V, X∪{e4}) est acyclique alors X ← X ∪{e4}; P(T)←9+6=15; i←i+1 ;
i=5 : (V, X∪{e5}) est acyclique alors X ← X ∪{e5}; P(T)←15+7=22; i←i+1 ;
i=6 : (V, X∪{e6}) contient un cycle ; i←i+1 ;
i=7 : (V, X∪{e7}) est acyclique alors X ← X ∪{e7}; P(T)←22+9=31; i←i+1 ;
i= : X={e1,e2,e3, e4, e5, e7} ⇒ |X| = 6 =|V|-1 alors fin de l’algorithme et le résultat est un arbre
T=(V,X) avec un poids minimum P(T)=31.
V={1, 3,6, 4, 5,2,7} ; X={36,13, 45, 24, 46, 57}

Exercice 2 (1+1+1+2+1 points)

Soit le graphe orienté G présenté par la figure ci dessous :
1) Donnez la matrice d’adjacence correspondante de G.
Solution 1 2 3 4 5
1 0 1 1 1 0
2 0 0 1 0 1
3 0 1 0 1 1
4 0 0 0 0 1
5 0 0 0 1 0

2) Donner la représentation machine (tables des successeurs) correspondante de G.

Solution

1 2 3 4 5
PS 1 4 6 9 10

1 2 3 4 5 6 7 8 9 10
LS 4 2 3 3 5 2 4 5 5 4

3) Est-ce qu’il existe une relation de forte connexité entre le sommet 2 et le sommet 4? Justifiez votre réponse.

Solution

Non il n’existe pas une relation de forte connexité entre le sommet 2 et le sommet 4 car il existe un chemin
du sommet vers le sommet 4 mais il n’existe pas un chemin du sommet 4 vers le sommet 2 et pour dire qu’il ya
une relation de forte connexité entre un sommet x et un sommet y on doit avoir un chemin de x verd y et un
chemin de y vers x.

[2/6]
4) En appliquant l’algorithme de décomposition, décomposer le graphe G suivant en composantes fortement
connexes. Donner le graphe réduit.

Solution
X ←{1, 2, 3, 4, 5} A(2) ←{2,3}
v←1 C(2) ← D(2) ∩ A(2) ={2,3}
D(1) ←{1,2,3,4,5} X←X/ C(2) ={4,5}
A(1) ←{1} v←4
C(1) ← D(1) ∩ A(1) = {1} D(4) ←{4,5}
X←X/ C(1) ={2,3,4,5} A(2) ←{4,5}
v←2 C(2) ← D(2) ∩ A(2) = {4,5}
D(2) ←{2,3,4,5} X←X/ C(2) = ∅ ⇒ fin de l’algorithme.

Graphe réduit

Exercice 3 (5 points)
Considérons un ensemble de 5 villes nommées V1, V2, V3, V4, et V5. Les tronçons de routes reliant les villes sont
représentées par la matrice suivante telle que la case située à l'intersection de la ligne i et de la colonne j contient
un entier égal à la longueur en kilomètres du tronçon de route reliant la ville Vi avec la ville Vj (on suppose que les
routes sont en sens unique). Une case vide veut dire qu’il n’existe pas de route entre les deux villes.
1) Représenter au moyen d'un graphe cette situation (représentation graphique).
Solution (1 Pts)

V1 V2 V3 V4 V5
V1 8 10
V2 5 12 20
V3 19
V4 14 11
V5

[3/6]
2) En utilisant le graphe obtenu, est il possible de partir de la ville V1 et d’y revenir en passant par chaque ville
une et une seule fois ? à quoi correspond la solution en termes de concepts liés à la théorie des graphes ?
Justifier Votre réponse.
Solution (0.25+0.25+0.5 Pts)
Non il n’est pas possible de partir de la ville V1 et d’y revenir en passant par chaque ville une et une seule
fois. La solution correspond à trouver un circuit Hamiltonien, dans le graphe de l’exemple il n’existe pas un
circuit Hamiltonien car si on prend le sommet V1 (correspondant a la ville V1) on remarque que c’est une
source donc on ne peut pas revenir a ce sommet donc impossible de construire un circuit Hamiltonien sans ce
graphe.

3) Quel est le chemin le plus court qui relie la ville V1 avec toute les autres villes? (Utiliser l'algorithme le mieux
adapté). Justifier votre choix.
Solution 1 (0.5 + 1.5 + 1 Pts)
Comme le ne contient pas de circuit on peut appliquer l’algorithme de Bellman.
Initialisation S←{V1}; π(V1)← 0; ∀x∈V, x≠ V1, π(x)←+∞; Arc←∅;
• x = V2 : π(V2)← π(V1)+l((V1,V2))]=0+8 , S←S∪{ V2},
Arc←Arc∪{(V1,V2)}.
• x = V4: π(V4)← min[π(V1)+l((V1, V4)); π(V2)+l((V2,V4))] =
π(V1)+l((V1,V4))=0+10 = 10 ; S←S∪{V4}; Arc←Arc∪{(V1, V4)};
• x = V3: π(V4)← min[π(V4)+l((V4, V3)); π(V2)+l((V2,V3))] =
π(V2)+l((V2,V3))=8+5 = 13 ; S←S∪{V3}; Arc←Arc∪{(V2, V3)};
• x = V5: π(V5)← min[π(V4)+l((V4, V5)); π(V2)+l((V2,V5));
π(V3)+l((V3,V5))] = π(V4)+l((V4,V5))=10+11 = 21 ; S←S∪{V5};
Arc←Arc∪{(V4, V5)};
• S = V Fin de l’algorithme
Arc = {(V1,V2), (V1,V4), (V2,V3), (V4,V5)}

Solution 2 (0.5 + 1.5 + 1 Pts)

Comme le graphe ne contient pas de poids négatifs on peut appliquer l’algorithme de Dijkstra.

Initialisation
S←{V1}; π(V1)← 0; ∀ x∈V, x≠ V1, π(x)←+∞; Arc(x)←∅; arrêt ← faut

Itération1 x= V1
• Y=V2 :π(V1)+l((V1,V2))=0+8=8<π(V2)=+∞⇒π(V2)←π(V1)+l((V1,V2))=8;
Arc(V2)←{(V1,V2)}.
• Y=V4 :π(V1)+l((V1,V4))=0+10=10<π(V4)=+∞⇒π(V4)←π(V1)+l((V1,V4))=10;
Arc(V4)←{(V1,V4)}.
Choisir un sommet z : z←V2 ; S← S∪{V2} ; x←V2 .

[4/6]
Itération2 x= V2
• Y=V3 :π(V2)+l((V2,V3))=8+5=13<π(V3)=+∞⇒π(V3)←π(V2)+l((V2,V3))=13;
Arc(V3)←{(V2,V3)}.
• Y=V4 :π(V2)+l((V2,V4))=8+12=20>π(V4)=10.
• Y=V5 :π(V2)+l((V2,V5))=8+20=28<π(V5)=+∞⇒π(V5)←π(V2)+l((V2,V5))=28;
Arc(V5)←{(V2,V5)}.

Choisir un sommet z : z←V4 ; S← S∪{V4} ; x←V4 .

Itération3 x= V4
• Y=V3 :π(V4)+l((V4,V3))=20+14=24>π(V3)=13
• Y=V5 :π(V4)+l((V4,V5))=10+11=21<π(V5)=28⇒π(V5)←π(V4)+l((V4,V5))=21;
Arc(V5)←{(V4,V5)}.

Choisir un sommet z : z←V3 ; S← S∪{V3} ; x←V3 .

Itération4 x= V3
• Y=V5 :π(V3)+l((V3,V5))=13+19=32>π(V5)=21
Choisir un sommet z : z←V5 ; S← S∪{V5} ; x←V5 .
S=V ⇒ arrêt ← vrai ⇒ Fin de l’algorithme.
Arc ={ (V1,V2), (V1,V4), (V2,V3), (V4,V5)}

Exercice 4 (1.25 * 4 points)

1. Soit G un graphe connexe eulérien.
a) Est-il toujours possible de rendre G non eulérien en lui enlevant des arêtes ? Justifiez votre réponse.
Solution (0.5+0.75 Pts)
Oui il est possible de rendre G non eulérien en lui enlevant des arêtes car dans un graphe eulérien tout les
sommets sont de degré pair donc il sufi de rendre des sommets de degrés pair en sommets de degré impair, si
on supprime une arête entre un sommet x et un sommet y on aura deux sommet de degrés impair de la même
manière si on enlève une deuxième arête et cela augmentera le nombre de sommets de degrés impaire dans
le graphe et le graphe n’est plus eulérien.
b) Combien d’arêtes au minimum doit-on enlever de G pour le rendre non Eulérien. Justifiez votre réponse.
Solution (0.5+ 0.75 Pts)
Le nombre d’arêtes au minimum doit-on enlever de G pour le rendre non Eulérien est une arête car la
suppression d’une arête entre un sommet x et un sommet y permet de rendre les deux sommet ayant un
degré impair et le graphe n’est plus eulérien il est semi eulérien..

2. Est-il possible de construire un graphe simple avec 6 sommets et 21 arêtes ? Justifier.

Solution (0.5+ 0.75 Pts)
Non il n’est pas possible car on a :

[5/6]
 Si le graphe est simple alors ∀x∈V, dg(x) ≤ n-1 si on somme ⇒ ∑:;<= dg(x) ≤ ∑:;<= > − 1 ⇒ 2m≤ n(n-1)
dans notre cas n=6 ⇒ 2m≤ 6*5 ⇒ 2m≤ 30 ⇒ m≤15⇒ n=6 et m=21 est une situation impossible

3. Est-il possible de construire un graphe 5-régulier avec 8 sommets ? Justifier.

Solution (0.5+ 0.75 Pts)
Oui il est possible car on a : n=8 et le graphe et 5 régulier ⇒∀x∈V, dg(x) =5 ⇒∑:;<= dg(x) =
∑@;<= 5=8*5 = 40 qui est un nombre pair ⇒ condition vérifiée.

[6/6]