Choisir sa représentation, dossier chiffré

Les graphes : modèle et représentations · niveau 2

Énoncé

Sélectionner et justifier la représentation pour : (a) un réseau social ( $n = 1 0^{9}$ sommets, degré moyen $= 200$ ), (b) un tournoi complet de 300 joueurs, (c) le réseau routier français ( $n = 1 0^{7}$ sommets, degré moyen $\approx 3$ ) où l'on réalise de nombreux tests d'existence de routes.

Corrigé

(a) Listes d'adjacence : Graphe extrêmement creux ( $1 0^{11}$ arcs vs $1 0^{18}$ pour la matrice). La matrice d'adjacence sature instantanément la mémoire physique disponible.
(b) Matrice d'adjacence : Graphe dense complet. Le nombre d'arcs est maximal ( $m \approx n^{2} /2 \approx 45000$ ). La matrice de dimensions $300 \times 300$ n'engendre aucune perte de place et permet un test direct en $O (1)$ .
(c) Listes d'adjacence : Bien que l'on teste l'existence d'arcs, la matrice requiert $1 0^{14}$ cases. Le test d'existence d'arête v in G[u] sur les listes d'adjacence ne prend qu'un temps au pire proportionnel au degré du sommet. Le degré moyen routier étant borné ( $\leq 5$ ), cette recherche s'exécute en fait en temps constant $O (1)$ en pratique.

Énoncé

Corrigé

Exercices semblables