Modéliser, c'est choisir — trois énoncés, trois graphes

Exercice · informatique (tronc commun des prépas scientifiques), chapitre 12 — Les graphes : modèle et représentations

Énoncé

Définir le modèle de graphe (sommets et arcs) pour : (a) le trajet de métro le plus rapide avec coût de correspondance, (b) la détection de dépendances circulaires entre modules de code, (c) la suggestion d'amis d'amis.

Corrigé

(a) Graphe du métro : Sommets $=$ couple (station, ligne) afin de distinguer une même station physique desservie par plusieurs lignes. Arêtes $=$ tronçons inter-stations pondérés par le temps de parcours, et arêtes internes de transfert reliant les sommets doublons d'une même station physique pondérées par le temps de marche de correspondance. Représentation en listes d'adjacence pondérées.
(b) Graphe des dépendances : Sommets $=$ modules. Arcs orientés $u \to v$ si le module $u$ importe le module $v$ . La présence de dépendances circulaires correspond à l'existence de cycles dans ce graphe orienté. Représentation en listes d'adjacence non pondérées.
(c) Graphe social (Amis d'amis) : Sommets $=$ comptes. Arêtes non orientées. La proposition "amis d'amis" correspond à l'ensemble des sommets situés à une distance minimale égale à 2 de l'origine (accessibles en 2 étapes, exclus les voisins directs et le sommet de départ). Listes d'adjacence.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.