ISSAT de Sousse G.R.

O
A.U:2024-2025
ING-A1
Série: Théorie des Graphes
Exercice 1 On considère le graphe G= (S; A) tel que:
5= {1,2,3,4,5}
A= {(1,2); (1,4); (2,3); (2,4); (3,5); (4,3): (5,3)}
1. Représenter graphiquement G.
2. Donner le degré sortant de 2 et le degré entrant de 4.
3. Donner les sommets prédécesseurs de 4 et les sommets successeurs de 2.
4. Donner un graphe partiel et un sous graphe de G.
5. Donmer la matrice d'adjacence de G.
Exercice 2 Soit le graphe dont la matrice booléenne associée est le suivante:
1 0 1 0 0 1
Π 1 1 0 1 0 1
0 1 0 1 0 0 1
M= 1 1 0 0 0
0 1 0 0 1 1 0
0 1 0 O 1
0 1 0 1 0 0
- il orienté?
1. Ce graphe est
2. Préciser la valeur du degré sortant de 5. lдре
3. Préciser la valeur du degré entrant de 4. lnne
4. Dessiner le graphe.
Exercice 3 Trois pays envoient chacun à une conférence deux espions; chaque
espion doit espionner tous les espions des autres pays (mais pas son propre
collègue!).
1. Représenter cette situation par un graphe d'ordre 6 dans lequel chaque
arête reliant i et j signifie que i espionne j et que j espionne i.
2. Ce graphe est-il complet? Est-il connexe?
 3. Quel est le degré de chaque sommet? Déduisez-en le nombre d'arêtes.
traffic aérien
Exercice 4 On considère 4 villes Vi,V₂, Va,V dans un pays où le
réduit: Il existe seulement un vol direct de V vers V₂ et V, de
est encore très
V½ vers V3, de V vers V et V, de V vers V₂.
1. Représenter les donnés par un graphe convenable.
2. ce graphe.
a) Ecrire la matrice M associée à
b) Calculer M² et M3.
un vol de chaque ville V vers chaque ville
3. Vérifier qu'il existe an moins
V, avec i j, comportant au plus 2 escales
uniquer en-
Exercice 5 Cinq personnes notées A, B,C, D et E peuvent comm et C, B et
tre elles soit par téléphone, soit par courrier électronique. A et B, A
ier électronique
C peuvent se téléphoner. C pent envoyer et recevoir du courr
avec D et E.
1. Ecrire la matrice associée à cette situation.
2. construire le graphe associé à cette situa
tion.
peut communiquer avec le plus grand nombre directe-
3. Quelle personne
ment?
4. On admet que deux personnes peuvent communiquer par l'intermédiaire
d'un troisième. Si X peut communiquer directement avec Y et Y directe- 1
2 1 1
2 1 1 1
1 1 4 0 0
ment avec Z. On admet que la matrice M² est M² = 1
0
E
1 1
0 1 1
Calculer la matrice S = M+M.
5. Déduire le résultat que chacune des cinq personnes peut communiquer
avec toute autre personne directement ou indirectement.
Exercice 6 Soit le graphe G ci-contre.
A B C
F E D
1. Donner la matrice M associée à G en écrivant les sommets dans l'ordre
alphabétique
2
 mo
n ta
tré r
Le
sore s
co
n rie ac
so
nt
a
2. On
calculé les ma tr ic es M² et
2 1 0 1 M5 suivantes:
1 1
1 3
14 21 12 9
0 1 1 9 21
0 21 18 9 19
M2= 1 2 0 0 14 26
et M5
12 9 2
1 0 0 2 1
12 12 9
1
g 19 12 4
1 1 0 1 2 6 14
9 14 12 7 4
1 1 1 0 19
3
21 26 9 14 19 18
a) En déduire le nomb re de ch ai ne s de lo ngueur 2 reliant A et
écrire. D. Les
b) Entre quels sommets de
ce graphe y-a-il le plus des
longueur 2. Les écrire. chaines de
c) Entre quels sommets de ce graphe y-a-il 4 chaines de longueur 2?
d) Déterminer le nombre de chaines de long
ueur 5 reliant B et F.