Institut Supérieur d’Informatique (ISI) de Dakar
Année académique : 2023-2024
Niveau : Licence 2 Réseaux Informatique (RI)
Département : Réseaux et système
Enseignant : Dr Cheikh GUEYE
Nom :........................ Prénom :....................
Devoir Théorie des Graphes
PROBLÈME 01.
Consigne : Il est attendu que les réponses fournies soient clairement justifiées.
La clarté, la rédaction et la justification des réponses fournies interviennent
dans la cotation.
• Attention : Il y a toujours au moins une réponse correcte, mais pour cer-
taines questions, il peut y en avoir plusieurs.
• Notation : G est un graphe, S est l’ensemble des sommets du graphe et A est
l’ensemble des arêtes ou arcs du graphe.
• Pour certaines questions, vous devez cocher une ou plusieurs cases qui
correspondent à une réponse correcte.
• Attention à bien cocher les cases, éviter les ratures, les débordements et
l’usage de produits de correction.
• Pour certaines questions, dites vrai ou faux avec correction de celle qui est
fausse.
Bon travail !
1
Questions Réponses
1. Dans la matrice d’adjacence d’un graphe ä Vrai
orienté, la somme des éléments sur la colonne i
ou sur la ligne i indique le degré du sommet i ä Faux
2. Le nombre de sommets d’un graphe indique ä Vrai
son degré ä Faux
3. Un graphe eulérien est un graphe ä Vrai
comportant un chemin qui passe par tous les
ä Faux
arcs sans répétitions
4. Quelle matrice peut-on utiliser pour le calcul ä Matrice d’adjacence S × S
du degré d’un sommet ? ä Matrice d’incidente S × A
ä Les deux
ä Aucune
5. Un chemin élémentaire peut passer plusieurs ä Vrai
fois par le même arc ä Faux
6. Soit un graphe G=(S, A). Une matrice ä S et A
d’adjacence représente une fonction définie ä S et S
entre les ensembles
ä A et A
7. Un graphe orienté est dit complet si et ä Vrai
seulement si pour tout couple de sommets (x,
y), il existe un chemin de x à y. ä Faux
8. Parmi les éléments suivants, quels sont ceux ä Sommets
absolument nécessaires pour définir un graphe ä Arêtes
orienté ? ä Arcs
ä Boucles
9. Dans un graphe non orienté, on appelle ä Deux sommets consécutifs sont adjacents
chaîne une suite de sommets dans laquelle : ä Deux sommets consécutifs sont égaux
ä Deux cotés égaux sont adjacents
ä Deux sommets consécutifs sont parallèles
10. L’algorithme de Dijkstra ä a bcp de similitudes avec le parcours en
largeur
ä ne fonctionne que sur des graphes acycliques
ä ne fonctionne que sur des arbres
ä doit s’implémenter avec une file de priorité
2
Questions Réponses
1. Deux sommets reliés par une arête sont dits : ä Colinéaires
ä Parallèles
ä Adjacents
ä Républicains
2. Un graphe est qualifié de complet si : ä Toutes ses arêtes sont colinéaires
ä Tous ses sommets sont deux à deux adjacents
ä Il est composé de droites
ä Il est orienté
3. Un graphe est orienté lorsque toutes ses arêtes sont ä Un point et une abscisse
définies par : ä Une origine et une abscisse
ä Une origine et une extrémité
ä Un point et un angle droit
PROBLÈME 02.
Partie I
On donne le tableau suivant :
Sommets A B C D E
Sommets Adjacents B, D A, C, E B, E A, E B, C, D
1. Tracer le graphe correspondant.
2. Donner la nature de ce graphe.
Partie II
n o
On considère le graphe orienté G = (S, A) tel que S = 1, 2, 3, 4, 5 et
n o
A = (1, 2), (1, 4), (2, 2), (2, 3), (2, 4), (3, 5), (4, 3), (5, 3) .
1. Tracer le graphe G.
2. Donner les sommets prédécesseurs de 4 et les sommets successeurs de 2,
3. Donner un sous-graphe de ce graphe.
Partie III
Dessiner un graphe non orienté complet à 4 sommets.
1. Quel est le degré des sommets de ce graphe ?
3
2. Combien d’arêtes possède-t-il ?
PROBLÈME 03. Une agence de voyages organise différentes excursions dans
une région du monde et propose la visite de sites incontournables, nommés
A, B, C, D, E et F.
Ces excursions sont résumées sur le graphe ci-dessous dont les sommets dé-
signent les sites, les arêtes représentent les routes pouvant être empruntées
pour relier deux sites et le poids des arêtes désigne le temps de transport (en
heures) entre chaque site
Un touriste désire aller du site A au site F en limitant au maximum les temps
de transport.
1. En utilisant un algorithme, déterminer la plus courte chaîne reliant le som-
met A au sommet F.
2. En déduire le temps de transport minimal pour aller du site A au site F.
BONNE CHANCE ! ! !