Chapitre 16 — Représentation des graphes
Modéliser des relations, choisir une structure adaptée et préparer les parcours de graphes SOMMETS → ARÊTES / ARCS → MATRICE → LISTES → DEGRÉS → APPLICATIONS |
Fiche pédagogique du chapitre
Objectifs d’apprentissage
À la fin de ce chapitre, l’étudiant devra être capable de :
• définir précisément les notions de sommet, arête, arc, chemin et cycle ;
• distinguer un graphe orienté, non orienté et pondéré ;
• représenter un même graphe par une matrice d’adjacence, une liste d’adjacence et une liste d’arêtes ;
• analyser le coût mémoire et le coût des opérations dans chaque représentation ;
• calculer le degré d’un sommet ainsi que les degrés entrant et sortant ;
• identifier les sommets isolés et vérifier les relations fondamentales sur les degrés ;
• choisir une représentation adaptée à un réseau routier, social ou informatique ;
• modéliser un ensemble de prérequis par un graphe orienté.
Prérequis
• tableaux et matrices ;
• listes chaînées et dictionnaires ;
• complexité temporelle et spatiale ;
• types abstraits de données ;
• boucles, fonctions et procédures.
Organisation indicative
Activité | Volume conseillé | Finalité |
|---|---|---|
| Cours | 4 à 5 h | Maîtriser le vocabulaire et les représentations. |
| Travaux dirigés | 4 h | Convertir, calculer des degrés et comparer les structures. |
| Travaux pratiques | 4 à 6 h | Implémenter un TAD Graphe et tester ses opérations. |
| Évaluation | 1 à 2 h | Modélisation, choix de structure et analyse de complexité. |
Idée directrice Un graphe décrit des objets et les relations qui les relient. Le dessin aide à comprendre, mais l’algorithme a besoin d’une représentation structurée en mémoire. • La matrice privilégie les tests d’adjacence rapides. • La liste d’adjacence privilégie les graphes peu denses. • La liste des arêtes privilégie les traitements centrés sur les relations. |
Introduction générale
Les graphes constituent un modèle fondamental de l’informatique. Ils permettent de représenter des routes entre des villes, des amitiés entre des personnes, des connexions entre des machines, des dépendances entre des tâches ou encore des prérequis entre des cours.
Un graphe peut être dessiné, mais un programme doit le stocker dans une structure de données. Le choix de cette structure influence directement la mémoire utilisée et l’efficacité des opérations : tester une relation, parcourir les voisins, compter les connexions ou analyser toutes les arêtes.
Modèle mathématique Un graphe est souvent noté G = (V, E) dans le cas non orienté ou G = (V, A) dans le cas orienté. • V est l’ensemble des sommets. • E est l’ensemble des arêtes non orientées. • A est l’ensemble des arcs orientés. |
Figure 16.1 — Un graphe non orienté à cinq sommets et six arêtes.
16.1 Définitions
16.1.1 Sommet
Un sommet, également appelé nœud, représente une entité du problème. Il peut s’agir d’une ville, d’un utilisateur, d’un ordinateur, d’une tâche ou d’un cours. Chaque sommet possède généralement un identifiant unique et peut porter des informations supplémentaires.
Domaine | Exemple de sommet | Informations possibles |
|---|---|---|
| Réseau routier | Ville | Nom, coordonnées, population |
| Réseau social | Utilisateur | Identifiant, profil, statut |
| Réseau informatique | Routeur | Adresse, capacité, état |
| Formation | Cours | Code, intitulé, semestre |
16.1.2 Arête
Une arête relie deux sommets sans imposer de direction. L’arête {u, v} signifie que la relation peut être considérée dans les deux sens. Dans un réseau social symétrique, si u est ami avec v, alors v est ami avec u.
16.1.3 Arc
Un arc possède une origine et une destination. L’arc (u, v) est différent de l’arc (v, u). Cette distinction est essentielle pour représenter une route à sens unique, un abonnement sur un réseau social ou un prérequis pédagogique.
Relation | Notation | Sens |
|---|---|---|
| Arête | {u, v} | u et v sont reliés symétriquement |
| Arc | (u, v) | la relation part de u vers v |
16.1.4 Graphe non orienté
Dans un graphe non orienté, toutes les relations sont des arêtes. La matrice d’adjacence est symétrique et chaque arête contribue au degré de ses deux extrémités.
16.1.5 Graphe orienté
Dans un graphe orienté, les relations sont des arcs. Un sommet peut recevoir de nombreux arcs sans en émettre, ou inversement. On distingue alors le degré entrant et le degré sortant.
16.1.6 Graphe pondéré
Un graphe pondéré associe une valeur à chaque arête ou arc. Cette valeur peut représenter une distance, un coût, une durée, une capacité, une probabilité ou une priorité.
Figure 16.2 — Exemple d’un graphe orienté pondéré : les poids peuvent représenter des durées de trajet.
Poids | Interprétation possible | Objectif algorithmique |
|---|---|---|
| Distance | Kilomètres | Trouver un trajet court |
| Durée | Minutes | Minimiser le temps |
| Coût | Montant | Minimiser une dépense |
| Capacité | Débit maximal | Acheminer un flot |
16.1.7 Chemin
Un chemin est une suite de sommets dans laquelle deux sommets consécutifs sont reliés. Dans un graphe orienté, l’orientation de chaque arc doit être respectée. La longueur d’un chemin peut désigner son nombre d’arêtes ou, dans un graphe pondéré, la somme de ses poids.
Notion | Définition |
|---|---|
| Marche | Suite de sommets pouvant répéter des arêtes et des sommets. |
| Chemin simple | Chemin ne répétant aucun sommet. |
| Longueur non pondérée | Nombre d’arêtes ou d’arcs. |
| Coût pondéré | Somme des poids utilisés. |
16.1.8 Cycle
Un cycle est un chemin fermé qui revient à son sommet de départ. Dans un cycle simple, les autres sommets ne sont pas répétés. Les cycles peuvent traduire une boucle de dépendances, un circuit routier ou une redondance dans un réseau.
Vocabulaire complémentaire • Deux sommets sont adjacents s’ils sont directement reliés. • Une arête est incidente à chacun de ses deux sommets. • Un graphe simple ne contient ni boucle sur un sommet ni arêtes multiples entre la même paire. • Un graphe est connexe lorsqu’un chemin existe entre toute paire de sommets. |
ZONE DE PSEUDO-CODE — Déterminer si deux sommets sont voisins dans un dessin logique Fonction SontAdjacents(G, u, v) : Booléen Pour chaque relation r de G Faire Si r relie u et v Alors Retourner Vrai FinSi FinPour Retourner Faux FinFonction Ce pseudo-code conceptuel sera optimisé selon la représentation choisie. |
16.2 Représentations
Un même graphe peut être stocké de plusieurs façons. Aucune représentation n’est universellement meilleure : le choix dépend de la densité du graphe et des opérations dominantes.
16.2.1 Matrice d’adjacence
Pour un graphe possédant n sommets, la matrice d’adjacence M est une matrice n × n. La case M[i][j] indique si une relation existe du sommet i vers le sommet j.
A / B | A | B | C | D | E |
|---|---|---|---|---|---|
| A | 0 | 1 | 1 | 0 | 0 |
| B | 1 | 0 | 1 | 1 | 0 |
| C | 1 | 1 | 0 | 0 | 1 |
| D | 0 | 1 | 0 | 0 | 1 |
| E | 0 | 0 | 1 | 1 | 0 |
Cette matrice représente le graphe de la figure 16.1. Comme le graphe est non orienté, M[i][j] = M[j][i] : la matrice est symétrique.
Type de graphe | Valeur de M[i][j] |
|---|---|
| Non pondéré | 1 si la relation existe, 0 sinon. |
| Pondéré | Poids de la relation ; une valeur spéciale représente l’absence. |
| Orienté | M[i][j] décrit uniquement l’arc i → j. |
| Boucle | Une valeur non nulle peut apparaître sur la diagonale. |
ZONE DE PSEUDO-CODE — Ajouter une relation dans une matrice Procédure AjouterRelationMatrice(M, u, v, poids, oriente) M[u][v] ← poids Si NON oriente Alors M[v][u] ← poids FinSi FinProcédure Pour un graphe non pondéré, le poids vaut généralement 1. |
ZONE DE PSEUDO-CODE — Tester une adjacency dans une matrice Fonction SontAdjacentsMatrice(M, u, v) : Booléen Retourner M[u][v] ≠ ABSENCE FinFonction Le test est effectué en temps O(1). |
Avantages et limites de la matrice
Aspect | Avantage | Limite |
|---|---|---|
| Test d’adjacence | Accès direct O(1) | Aucune |
| Mémoire | Simple et contiguë | O(n²), même si peu d’arêtes |
| Parcours des voisins | Structure régulière | Il faut parcourir toute une ligne : O(n) |
| Ajout d’un sommet | Conceptuellement simple | Nécessite souvent de redimensionner la matrice |
16.2.2 Liste d’adjacence
Une liste d’adjacence associe à chaque sommet la collection de ses voisins. Elle peut être construite avec un tableau de listes, un dictionnaire de listes ou une table de hachage.
ZONE DE PSEUDO-CODE — Liste d’adjacence du graphe fil rouge A : [B, C] B : [A, C, D] C : [A, B, E] D : [B, E] E : [C, D] Dans un graphe non orienté, chaque arête apparaît dans les listes de ses deux extrémités. |
ZONE DE PSEUDO-CODE — Ajouter une relation dans une liste d’adjacence Procédure AjouterRelationListe(L, u, v, poids, oriente) Ajouter (v, poids) à L[u] Si NON oriente Alors Ajouter (u, poids) à L[v] FinSi FinProcédure Le poids peut être omis pour un graphe non pondéré. |
ZONE DE PSEUDO-CODE — Afficher les voisins d’un sommet Procédure AfficherVoisins(L, u) Pour chaque voisin v dans L[u] Faire Afficher v FinPour FinProcédure Le coût est proportionnel au nombre de voisins de u. |
Avantages et limites de la liste d’adjacence
Aspect | Avantage | Limite |
|---|---|---|
| Mémoire | O(n + m) | Moins compacte pour les graphes très denses |
| Parcours des voisins | O(degré(u)) | Aucune |
| Test d’adjacence | Possible dans la liste de u | O(degré(u)) sans structure auxiliaire |
| Ajout de sommet | Facile | La structure doit créer une nouvelle liste |
16.2.3 Liste des arêtes
La liste des arêtes stocke directement chaque relation sous forme d’un couple (u, v) ou d’un triplet (u, v, poids). Elle est simple, compacte et adaptée aux algorithmes qui parcourent ou trient toutes les relations.
ZONE DE PSEUDO-CODE — Liste des arêtes du graphe fil rouge E ← [(A,B), (A,C), (B,C), (B,D), (C,E), (D,E)] Chaque arête non orientée n’est stockée qu’une seule fois. |
ZONE DE PSEUDO-CODE — Parcourir toutes les arêtes Procédure AfficherAretes(E) Pour chaque (u, v, poids) dans E Faire Afficher u, v, poids FinPour FinProcédure Le coût est O(m), où m est le nombre de relations. |
Opération | Coût typique avec une liste d’arêtes |
|---|---|
| Parcourir toutes les relations | O(m) |
| Tester si u et v sont adjacents | O(m) |
| Obtenir tous les voisins de u | O(m) |
| Trier les arêtes par poids | O(m log m) |
16.2.4 Comparaison des représentations
Critère | Matrice d’adjacence | Liste d’adjacence | Liste des arêtes |
|---|---|---|---|
| Mémoire | O(n²) | O(n + m) | O(m) |
| Test u-v | O(1) | O(degré(u)) | O(m) |
| Voisins de u | O(n) | O(degré(u)) | O(m) |
| Parcours de toutes les relations | O(n²) | O(n + m) | O(m) |
| Graphe dense | Très adaptée | Possible | Possible |
| Graphe creux | Souvent coûteuse | Très adaptée | Adaptée |
| Algorithmes centrés sur les arêtes | Moyenne | Bonne | Très bonne |
Densité d’un graphe Pour un graphe non orienté simple à n sommets, le nombre maximal d’arêtes est n(n − 1)/2. Un graphe est dit creux lorsque m est très inférieur à ce maximum, et dense lorsque m en est proche. |
ZONE DE PSEUDO-CODE — Choisir une représentation Fonction ChoisirRepresentation(n, m, operationsDominantes) : Texte Si operationsDominantes contient "test adjacency intensif" Alors Retourner "Matrice adjacency" SinonSi m est très inférieur à n² Alors Retourner "Liste adjacency" SinonSi operationsDominantes contient "tri des arêtes" Alors Retourner "Liste des arêtes" Sinon Retourner "Choix à valider expérimentalement" FinSi FinFonction Le choix réel dépend également du langage, des constantes et des mises à jour prévues. |
16.2.5 Conversion entre représentations
ZONE DE PSEUDO-CODE — Convertir une matrice en liste d’adjacence Fonction MatriceVersListes(M, n) : Listes Créer L contenant n listes vides Pour i allant de 0 à n - 1 Faire Pour j allant de 0 à n - 1 Faire Si M[i][j] ≠ ABSENCE Alors Ajouter (j, M[i][j]) à L[i] FinSi FinPour FinPour Retourner L FinFonction La conversion parcourt n² cases : O(n²). |
ZONE DE PSEUDO-CODE — Convertir une liste d’adjacence en matrice Fonction ListesVersMatrice(L, n) : Matrice Créer M[n][n] initialisée à ABSENCE Pour u allant de 0 à n - 1 Faire Pour chaque (v, poids) dans L[u] Faire M[u][v] ← poids FinPour FinPour Retourner M FinFonction Le coût d’initialisation est O(n²), puis le remplissage dépend du nombre de relations. |
16.3 Degré
16.3.1 Degré d’un sommet dans un graphe non orienté
Le degré deg(v) d’un sommet v est le nombre d’arêtes incidentes à ce sommet. Une boucle, lorsqu’elle est autorisée, contribue deux fois au degré car elle possède deux extrémités sur le même sommet.
Sommet | Voisins dans le graphe fil rouge | Degré |
|---|---|---|
| A | B, C | 2 |
| B | A, C, D | 3 |
| C | A, B, E | 3 |
| D | B, E | 2 |
| E | C, D | 2 |
Lemme de la poignée de main Dans tout graphe non orienté, la somme des degrés est égale à deux fois le nombre d’arêtes : Σ deg(v) = 2m. Conséquence : le nombre de sommets de degré impair est toujours pair. |
ZONE DE PSEUDO-CODE — Calculer les degrés avec une liste d’adjacence Fonction DegreListe(L, u) : Entier Retourner Longueur(L[u]) FinFonction Le degré est disponible en O(1) si la longueur de la liste est maintenue. |
ZONE DE PSEUDO-CODE — Calculer le degré avec une matrice Fonction DegreMatrice(M, u, n) : Entier degre ← 0 Pour v allant de 0 à n - 1 Faire Si M[u][v] ≠ ABSENCE Alors degre ← degre + 1 FinSi FinPour Retourner degre FinFonction Le coût est O(n) car toute la ligne est parcourue. |
16.3.2 Degré entrant
Dans un graphe orienté, le degré entrant deg⁻(v) est le nombre d’arcs dont v est la destination. Il peut représenter le nombre de liens reçus, de dépendances entrantes ou de connexions dirigées vers v.
16.3.3 Degré sortant
Le degré sortant deg⁺(v) est le nombre d’arcs dont v est l’origine. Il peut représenter le nombre de liens émis, d’actions possibles ou de dépendances générées par v.
Propriété | Relation |
|---|---|
| Somme des degrés sortants | Σ deg⁺(v) = m |
| Somme des degrés entrants | Σ deg⁻(v) = m |
| Somme totale | Σ (deg⁺(v) + deg⁻(v)) = 2m |
ZONE DE PSEUDO-CODE — Calculer les degrés entrants et sortants dans une matrice Procédure CalculerDegresOrientes(M, n, entree, sortie) Initialiser entree et sortie à 0 Pour u allant de 0 à n - 1 Faire Pour v allant de 0 à n - 1 Faire Si M[u][v] ≠ ABSENCE Alors sortie[u] ← sortie[u] + 1 entree[v] ← entree[v] + 1 FinSi FinPour FinPour FinProcédure Le parcours complet de la matrice coûte O(n²). |
ZONE DE PSEUDO-CODE — Calculer les degrés entrants et sortants dans une liste Procédure CalculerDegresListes(L, n, entree, sortie) Initialiser entree et sortie à 0 Pour u allant de 0 à n - 1 Faire sortie[u] ← Longueur(L[u]) Pour chaque voisin v dans L[u] Faire entree[v] ← entree[v] + 1 FinPour FinPour FinProcédure Le coût est O(n + m). |
16.3.4 Sommet isolé
Un sommet isolé ne possède aucune relation. Son degré vaut 0 dans un graphe non orienté. Dans un graphe orienté, ses degrés entrant et sortant sont tous deux nuls.
ZONE DE PSEUDO-CODE — Rechercher les sommets isolés Fonction SommetsIsoles(L, n) : Liste isoles ← liste vide Pour u allant de 0 à n - 1 Faire Si Longueur(L[u]) = 0 Alors Ajouter u à isoles FinSi FinPour Retourner isoles FinFonction Pour un graphe orienté, il faut également vérifier qu’aucun arc n’entre dans le sommet. |
Autres sommets particuliers • Sommet pendant : degré égal à 1 dans un graphe non orienté. • Source : degré entrant nul dans un graphe orienté. • Puits : degré sortant nul dans un graphe orienté. |
Exemple fil rouge — Une même structure sous trois formes
Figure 16.3 — Graphe utilisé pour comparer les représentations.
Matrice d’adjacence
A / B | A | B | C | D | E |
|---|---|---|---|---|---|
| A | 0 | 1 | 1 | 0 | 0 |
| B | 1 | 0 | 1 | 1 | 0 |
| C | 1 | 1 | 0 | 0 | 1 |
| D | 0 | 1 | 0 | 0 | 1 |
| E | 0 | 0 | 1 | 1 | 0 |
Liste d’adjacence
ZONE DE PSEUDO-CODE — Représentation par voisins A : [B, C] B : [A, C, D] C : [A, B, E] D : [B, E] E : [C, D] |
Liste des arêtes
ZONE DE PSEUDO-CODE — Représentation par relations [(A,B), (A,C), (B,C), (B,D), (C,E), (D,E)] |
Vérifications
Mesure | Valeur | Vérification |
|---|---|---|
| Nombre de sommets n | 5 | A, B, C, D, E |
| Nombre d’arêtes m | 6 | Six couples dans la liste |
| Somme des degrés | 12 | 2 + 3 + 3 + 2 + 2 |
| 2m | 12 | 2 × 6 |
Conclusion de l’exemple Les trois structures décrivent exactement le même graphe. Elles ne modifient pas le problème, mais elles modifient le coût des opérations. Le choix d’une représentation est donc un choix algorithmique. |
Applications
Application 1 — Réseau routier
Les sommets représentent des intersections ou des villes. Les arêtes représentent des routes à double sens et les arcs des voies à sens unique. Les poids peuvent indiquer la distance, la durée ou le coût du trajet.
• Représentation conseillée : liste d’adjacence pondérée pour un grand réseau peu dense.
• Matrice utile : lorsque le réseau contient peu de sommets et de nombreux liens.
Figure 16.4 — Modélisation simplifiée d’un réseau routier.
Application 2 — Réseau social
Dans un réseau d’amitié, les relations sont généralement non orientées. Dans un réseau d’abonnement, la relation est orientée : suivre une personne ne signifie pas être suivi par elle.
Indicateur | Interprétation |
|---|---|
| Degré | Nombre de relations directes |
| Degré entrant | Nombre d’abonnés |
| Degré sortant | Nombre de comptes suivis |
| Sommet isolé | Compte sans relation |
Application 3 — Réseau informatique
Les sommets peuvent représenter des machines, routeurs ou services. Les relations représentent des liaisons physiques ou logiques. Un poids peut décrire la latence, le débit, le coût ou le taux d’erreur.
• Une liste d’adjacence permet de parcourir efficacement les voisins de chaque équipement.
• Une matrice facilite les tests rapides dans un petit réseau très interconnecté.
Application 4 — Prérequis entre cours
Chaque cours est un sommet. Un arc A → B signifie que A doit être validé avant B. Ce modèle doit normalement être acyclique : un cycle signalerait des prérequis impossibles à satisfaire.
Figure 16.5 — Exemple de graphe orienté de prérequis.
ZONE DE PSEUDO-CODE — Construire la liste des prérequis directs Procédure AjouterPrerequis(G, coursAvant, coursApres) Ajouter coursApres à G[coursAvant] FinProcédure Le tri topologique, étudié ultérieurement, permettra d’obtenir un ordre de suivi valide. |
Application | Orientation | Pondération | Représentation souvent adaptée |
|---|---|---|---|
| Routes | Selon les voies | Distance ou durée | Liste d’adjacence pondérée |
| Réseau social | Amitié ou abonnement | Facultative | Liste d’adjacence |
| Réseau informatique | Souvent orienté | Latence ou capacité | Liste d’adjacence pondérée |
| Prérequis | Orienté | Généralement non | Liste d’adjacence |
Méthode de modélisation d’un problème par un graphe
1. Identifier les entités qui deviendront les sommets.
2. Identifier les relations qui deviendront des arêtes ou des arcs.
3. Déterminer si les relations sont symétriques ou orientées.
4. Déterminer si une valeur doit être associée à chaque relation.
5. Estimer le nombre de sommets n et de relations m.
6. Lister les opérations les plus fréquentes.
7. Choisir la représentation offrant le meilleur compromis.
8. Construire de petits jeux d’essai et vérifier les degrés.
Questions à poser avant l’implémentation • Le graphe est-il orienté ? • Est-il pondéré ? • Les sommets sont-ils connus à l’avance ? • Le graphe est-il creux ou dense ? • Doit-on tester souvent l’existence d’une relation ? • Doit-on parcourir souvent les voisins ? |
Erreurs fréquentes
Erreur | Conséquence | Correction |
|---|---|---|
| Oublier la symétrie d’un graphe non orienté | Une arête n’est visible que dans un sens | Mettre à jour les deux directions. |
| Confondre 0 et absence dans un graphe pondéré | Impossible de représenter un poids nul | Utiliser une constante ABSENCE. |
| Compter deux fois les arêtes | Valeur m incorrecte | Diviser par deux dans une liste non orientée. |
| Utiliser une matrice pour un immense graphe creux | Mémoire excessive | Préférer une liste d’adjacence. |
| Confondre degré et poids | Mesure incohérente | Le degré compte les relations, pas leur poids. |
| Ignorer l’orientation dans un chemin | Chemin invalide | Respecter chaque arc. |
Travaux dirigés
TD 1 — Reconnaissance du vocabulaire
Pour le graphe fil rouge, identifier les sommets, les arêtes, les voisins de B, un chemin de A vers E et un cycle.
TD 2 — Construction d’une matrice
Construire la matrice d’adjacence du graphe non orienté V = {1,2,3,4} et E = {{1,2},{1,3},{2,4},{3,4}}.
TD 3 — Construction d’une liste d’adjacence
Transformer la matrice suivante en liste d’adjacence : [[0,1,0],[1,0,1],[0,1,0]].
TD 4 — Liste des arêtes et pondération
Donner la liste des arêtes pondérées d’un réseau contenant A-B de poids 4, A-C de poids 2 et C-B de poids 1.
TD 5 — Calcul des degrés
Calculer les degrés des sommets du graphe du TD 2 et vérifier le lemme de la poignée de main.
TD 6 — Graphe orienté
Pour les arcs A→B, A→C, C→B, B→D et D→C, calculer les degrés entrants et sortants.
TD 7 — Choix d’une représentation
Choisir une représentation pour : a) un réseau social de dix millions de comptes avec peu de relations par compte ; b) un graphe dense de 100 sommets avec tests d’adjacence fréquents ; c) un algorithme qui trie toutes les arêtes par poids.
TD 8 — Réseau routier
Modéliser quatre villes et cinq routes pondérées. Préciser si le graphe est orienté, puis proposer la représentation la plus adaptée.
TD 9 — Prérequis pédagogiques
Construire un graphe orienté pour les dépendances suivantes : Algorithmique avant Structures ; Structures avant Graphes ; Complexité avant Graphes ; Graphes avant Optimisation.
TD 10 — Interface d’un TAD Graphe
Proposer une interface contenant au minimum : AjouterSommet, AjouterRelation, SupprimerRelation, SontAdjacents, Voisins, Degre et NombreRelations.
Corrigés indicatifs des travaux dirigés
Correction du TD 1
• Sommets : A, B, C, D, E.
• Arêtes : AB, AC, BC, BD, CE, DE.
• Voisins de B : A, C et D.
• Chemin A-C-E.
• Cycle A-B-C-A.
Correction du TD 2
| 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 1 | 0 | 1 | 1 | 0 |
| 2 | 1 | 0 | 0 | 1 |
| 3 | 1 | 0 | 0 | 1 |
| 4 | 0 | 1 | 1 | 0 |
Correction du TD 3
ZONE DE PSEUDO-CODE — Liste obtenue 0 : [1] 1 : [0, 2] 2 : [1] |
Correction du TD 4
ZONE DE PSEUDO-CODE — Liste des arêtes pondérées [(A, B, 4), (A, C, 2), (C, B, 1)] |
Correction du TD 5
Les degrés sont deg(1)=2, deg(2)=2, deg(3)=2 et deg(4)=2. La somme vaut 8. Comme m=4, 2m=8 : la relation est vérifiée.
Correction du TD 6
Sommet | Degré entrant | Degré sortant |
|---|---|---|
| A | 0 | 2 |
| B | 2 | 1 |
| C | 2 | 1 |
| D | 1 | 1 |
La somme des degrés entrants et celle des degrés sortants valent toutes deux 5, soit le nombre d’arcs.
Correction du TD 7
Situation | Choix | Justification |
|---|---|---|
| Très grand réseau social creux | Liste d’adjacence | Mémoire O(n+m) et accès direct aux voisins. |
| Graphe dense avec nombreux tests | Matrice | Test d’adjacence en O(1). |
| Tri de toutes les arêtes | Liste des arêtes | Structure directe pour le tri. |
Correction du TD 8
Une solution possible utilise les villes A, B, C et D avec les routes A-B(5), A-C(2), B-C(1), B-D(4) et C-D(7). Si toutes les routes sont à double sens, le graphe est non orienté. Une liste d’adjacence pondérée est adaptée.
Correction du TD 9
ZONE DE PSEUDO-CODE — Liste d’adjacence des prérequis Algorithmique : [Structures] Structures : [Graphes] Complexité : [Graphes] Graphes : [Optimisation] Optimisation : [] |
Correction du TD 10
ZONE DE PSEUDO-CODE — Interface possible du TAD Graphe CréerGraphe(oriente, pondere) AjouterSommet(G, sommet) AjouterRelation(G, u, v, poids) SupprimerRelation(G, u, v) SontAdjacents(G, u, v) : Booléen Voisins(G, u) : Liste Degre(G, u) : Entier NombreSommets(G) : Entier NombreRelations(G) : Entier |
Travail pratique — Bibliothèque de représentation des graphes
Objectif
Développer un petit module capable de stocker un graphe orienté ou non orienté, pondéré ou non, et de produire plusieurs représentations cohérentes.
Fonctionnalités demandées
1. Créer un graphe et préciser ses propriétés.
2. Ajouter des sommets et des relations.
3. Afficher la matrice d’adjacence.
4. Afficher la liste d’adjacence.
5. Afficher la liste des arêtes ou arcs.
6. Tester l’adjacence de deux sommets.
7. Calculer les degrés et détecter les sommets isolés.
8. Comparer la mémoire estimée des trois représentations.
ZONE DE PSEUDO-CODE — Structure principale du module Type Graphe oriente : Booléen pondere : Booléen sommets : Liste adjacency : Dictionnaire<SOMMET, Liste<(SOMMET, POIDS)>> FinType |
ZONE DE PSEUDO-CODE — Ajouter une relation dans le module Procédure AjouterRelation(G, u, v, poids) Si u ou v n’existe pas Alors Signaler "Sommet inconnu" FinSi Ajouter (v, poids) à G.adjacency[u] Si NON G.oriente Alors Ajouter (u, poids) à G.adjacency[v] FinSi FinProcédure |
ZONE DE PSEUDO-CODE — Produire la liste des arêtes sans doublon Fonction ListeRelations(G) : Liste resultat ← liste vide Pour chaque sommet u de G Faire Pour chaque (v, poids) dans G.adjacency[u] Faire Si G.oriente OU u < v Alors Ajouter (u, v, poids) à resultat FinSi FinPour FinPour Retourner resultat FinFonction La condition u < v évite de dupliquer une arête non orientée lorsque les identifiants sont comparables. |
Jeux d’essai
Test | Entrée | Résultat attendu |
|---|---|---|
| Graphe non orienté | A-B, A-C, B-C | Matrice symétrique ; degrés 2,2,2. |
| Sommet isolé | Ajouter D sans relation | D apparaît dans la liste des isolés. |
| Graphe orienté | A→B, C→B | Entrée(B)=2 ; Sortie(B)=0. |
| Graphe pondéré | A-B de poids 0 | La relation existe malgré le poids nul. |
| Relation invalide | Ajouter A-Z sans Z | Erreur contrôlée. |
Livrables
• code ou pseudo-code structuré ;
• rapport expliquant les choix de représentation ;
• captures ou sorties des jeux d’essai ;
• tableau comparatif des coûts ;
• conclusion sur le choix selon la densité.
Grille d’évaluation
Critère | Points |
|---|---|
| Modélisation du TAD Graphe | 4 |
| Ajout et gestion des relations | 4 |
| Conversions et affichages | 4 |
| Calcul des degrés et tests | 3 |
| Jeux d’essai | 3 |
| Qualité et justification | 2 |
Synthèse du chapitre
Notion | Idée essentielle |
|---|---|
| Sommet | Entité du problème. |
| Arête | Relation symétrique. |
| Arc | Relation orientée. |
| Poids | Valeur associée à une relation. |
| Chemin | Suite de relations valides. |
| Cycle | Chemin fermé. |
| Matrice | O(n²), test d’adjacence O(1). |
| Liste d’adjacence | O(n+m), adaptée aux graphes creux. |
| Liste des arêtes | O(m), adaptée aux traitements des relations. |
| Degré | Nombre de relations incidentes. |
| Degrés entrant/sortant | Nombre d’arcs reçus/émis. |
| Sommet isolé | Aucune relation. |
À retenir La représentation est une décision algorithmique. Un bon choix tient compte de la densité, de la mémoire disponible et des opérations qui seront réellement exécutées. |
Glossaire
Terme | Définition |
|---|---|
| Adjacence | Relation directe entre deux sommets. |
| Arc | Relation orientée. |
| Arête | Relation non orientée. |
| Cycle | Chemin fermé. |
| Degré | Nombre d’arêtes incidentes. |
| Densité | Proportion des relations présentes. |
| Graphe creux | Graphe comportant relativement peu d’arêtes. |
| Pondération | Association d’une valeur aux relations. |
| Sommet isolé | Sommet de degré nul. |
| Voisin | Sommet directement relié. |
Auto-évaluation
Je sais… | Oui | À revoir |
|---|---|---|
| distinguer arête et arc | ☐ | ☐ |
| reconnaître les graphes orientés et pondérés | ☐ | ☐ |
| construire une matrice d’adjacence | ☐ | ☐ |
| construire une liste d’adjacence | ☐ | ☐ |
| produire une liste d’arêtes | ☐ | ☐ |
| comparer les coûts mémoire | ☐ | ☐ |
| calculer les degrés | ☐ | ☐ |
| choisir une représentation adaptée | ☐ | ☐ |
| modéliser une application réelle | ☐ | ☐ |
Fin du chapitre 16 — Représentation des graphes.