Mathématiques 2

Notations et définitions.

Les graphes sont orientés et leurs sommets sont numérotés $0, 1, 2, \dots$.

Un graphe est codé par un dictionnaire d'adjacence d : à chaque sommet s est associée la liste d[s] de ses successeurs.

Le graphe d'exemple a pour sommets $0, \dots, 6$.

Ses arcs sont $0 \to 1$, $0 \to 3$, $1 \to 2$, $2 \to 4$, $2 \to 5$, $3 \to 4$, $4 \to 1$ et $6 \to 2$.

Le sommet 5 n'a aucun successeur.

Écrivons une fonction degreMax(d) qui renvoie le plus grand des degrés sortants des sommets du graphe orienté représenté par le dictionnaire d'adjacence d.

On parcourt les sommets, c'est-à-dire les clés du dictionnaire.

Le degré sortant du sommet s est la longueur de la liste d[s].

On garde le plus grand degré rencontré, sans utiliser la fonction max.

Un degré est positif ou nul, donc l'initialisation à 0 est correcte.

À la fin de la boucle, m est le maximum des degrés sortants des sommets du graphe.

La fonction renvoie 0 pour un graphe sans sommet.