Exercices: Graphes et parcours

Un graphe non orienté a pour sommets A, B, C, D et pour arêtes : A–B, A–C, B–C, C–D.

1. a) Donner la matrice d'adjacence (sommets dans l'ordre A, B, C, D).

1. b) Donner la liste d'adjacence de chaque sommet.

1. c) Donner le degré de chaque sommet.

Un graphe orienté a pour sommets 0, 1, 2, 3 et pour arcs : 0→1, 0→2, 1→3, 2→3, 3→0.

1. a) Donner la liste des successeurs de chaque sommet.

1. b) Donner la liste des prédécesseurs de chaque sommet.

1. c) Écrire la matrice d'adjacence et expliquer pourquoi elle n'est pas symétrique.

Soit le graphe orienté défini par le dictionnaire Python g = {0: [1, 2], 1: [2], 2: [0, 3], 3: []}.

1. a) Dessiner (décrire) ce graphe.

1. b) Indiquer si les chemins 0→1→2→3 et 3→2→0 existent.

1. c) Citer un cycle de ce graphe.

Soit le graphe non orienté défini par g = {"A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D", "E"], "D": ["B", "C"], "E": ["C"]}.

1. a) Donner le parcours en largeur à partir de A (en visitant les voisins dans l'ordre alphabétique).

1. b) Donner le parcours en profondeur à partir de A (même convention).

1. c) Donner un chemin de A à E de longueur minimale.

Un réseau de métro simplifié à Lyon relie les stations Bellecour (Be), Perrache (Pe), Cordeliers (Co), Hôtel de Ville (Ho) et Part-Dieu (Pa) : Be–Pe, Be–Co, Co–Ho, Be–Ho, Ho–Pa.

1. a) Représenter ce réseau par une matrice d'adjacence.

1. b) Donner le nombre minimal de liaisons (arêtes) à parcourir pour aller de Pe à Pa et un chemin correspondant.

1. c) Écrire une fonction Python degre(matrice, i) qui renvoie le degré du sommet i.

On souhaite détecter un cycle dans un graphe non orienté à l'aide d'un parcours en profondeur.

1. a) Expliquer le principe : que signifie rencontrer un sommet déjà visité qui n'est pas le parent du sommet courant ?

1. b) Appliquer ce principe au graphe d'arêtes 1–2, 2–3, 3–4, 4–2, 4–5.

1. c) Le graphe d'arêtes 1–2, 2–3, 2–4, 4–5 possède-t-il un cycle ? Justifier.

Écrire en Python une fonction parcours_largeur(g, s) qui prend un graphe g sous forme de dictionnaire de listes d'adjacence et un sommet s, et renvoie la liste des sommets visités dans l'ordre d'un parcours en largeur.

1. a) Préciser la structure de données utilisée et justifier ce choix.

1. b) Écrire la fonction.

1. c) Montrer que chaque sommet est visité au plus une fois et donner le coût en fonction du nombre de sommets $n$ et d'arêtes $m$.

1. d) Expliquer comment adapter la fonction pour obtenir la distance minimale (en nombre d'arêtes) entre s et chaque sommet.

Un graphe orienté représente des dépendances entre modules d'un programme : un arc $X \to Y$ signifie que $X$ doit être chargé avant $Y$. Les arcs sont : M1→M2, M1→M3, M2→M4, M3→M4, M4→M5.

1. a) Donner un ordre de chargement valide.

1. b) On ajoute l'arc M5→M2. Montrer qu'il n'existe plus d'ordre valide.

1. c) Expliquer en quoi cette situation est analogue à un interblocage entre processus, et comment détecter ce problème par un parcours de graphe.

Dans un réseau, les routeurs R1 à R5 sont reliés ainsi, avec le coût de chaque liaison (OSPF) : R1–R2 : 1 ; R1–R3 : 4 ; R2–R3 : 2 ; R2–R4 : 7 ; R3–R5 : 3 ; R4–R5 : 1.

1. a) Déterminer le chemin de coût minimal de R1 à R4 en détaillant les étapes de l'algorithme de Dijkstra.

1. b) Expliquer en quoi RIP (qui compte le nombre de sauts) choisirait éventuellement un autre chemin ; donner ce chemin.

1. c) Expliquer le lien entre protocole de routage et recherche d'un chemin dans un graphe pondéré.