# -*- coding: utf-8 -*- # Chapitre 7: Parcours de graphes #%% I. Introduction et définitions #%% Notion de Graphe et d'arbre # On appelle graphe un ensemble de sommets reliés par des arrêtes. Le dessin ci-dessous est un exemple de graphe: # ╔═══╗ # ┌────────────────╢ H ║ # │ ┌──────┐ ╚╤═╤╝ ╔═══╗ # ╔╧═╧╗ │ │ │ ║ R ║ # ║ C ╟─────┘ │ │ ╚╤══╝ #G₀: ╚╤═╤╝ ╔══╧╗│ │ # │ └────────────╢ O ╟┘ │ # │╔═══╗ ╚╤══╝ ╔══╧╗ # └╢ D ╟──────────┘ ║ Y ║ # ╚═╤═╝ ╔═══╗ ╚═══╝ # └───────╢ Q ║ # ╚═══╝ # Dans cet exemple, le graphe G₀ a 7 sommets, notés C, D, H, O, Q, R et Y. Les arrêtes qui les relient ne sont pas nécessairement des lignes droites (sur cet exemple elles sont représentées avec des angles). On note en particulier que sur cet exemple, il y a une arrête qui relie le sommet C à lui même, et qu'il y a deux arrêtes qui relient le sommet H au sommet O. # Mathématiquement, on identifie un graphe à un couple (S,A) où S est l'ensemble des sommets et A est la donnée des arrêtes. L'exemple ci-dessus correspond ainsi à S={C, D, H, O, Q, R, Y} et A=({C,C},{C,D},{C,H},{C,O},{D,O},{D,Q},{H,O},{H,O},{R,Y}). # Un arbre est un cas particulier de graphe qui est connexe et n'a pas de boucle, c'est à dire que pour tous couple (S₁,S₂) de sommets, il existe un unique chemin (sans demi-tour) qui va de S₁ à S₂. # Le graphe G₀ ci dessus n'est pas un arbre car il n'est pas connexe (par exemple il n'y a pas de chemin qui aille de H à R), et qu'il a des boucles (par exemple il y a plein de façons d'aller de C à O: de manière directe, ou en passant par D, ou en passant par H, etc). #%% Parcours de graphes "en profondeur" et "en largeur" # De nombreux problèmes concrets se ramènent à des "parcours de graphes", c'est à dire des algorithmes qui considèrent successivement les sommets (et les arrêtes) du graphe. # Il se trouve que l'on distingue deux grandes familles d'algorithmes : les algorithmes de parcours en profondeur et les algorithmes de parcours en largeur. Par exemple, si on considère l'arbre ci-dessous: # ╔═══╗ # ║ R ║ # ╚╤╤╤╝ # ┌──────┘│└──────┐ # ╔══╧╗ ╔═╧═╗ ╔╧══╗ # ║ a ║ ║ b ║ ║ c ║ # ╚╤═╤╝ ╚═══╝ ╚╤═╤╝ # A: ┌──┘ └─┐ ┌──┘ └─┐ # ╔══╧╗ ╔╧══╗ ╔══╧╗ ╔╧══╗ # ║ 1 ║ ║ 2 ║ ║ 3 ║ ║ 4 ║ # ╚═══╝ ╚═══╝ ╚╤╤╤╝ ╚═══╝ # ┌──────┘│└─────┐ # ╔══╧╗ ╔══╧╗ ╔╧══╗ # ║ X ║ ║ Y ║ ║ Z ║ # ╚═══╝ ╚═══╝ ╚═══╝ # * Un parcours "en largeur" signifierait typiquement qu'on considère d'abord le sommet R, puis les sommets a, b, et c, puis les sommets 1, 2, 3 et 4, et enfin les sommets X, Y et Z, c'est à dire qu'on regarde les lignes l'une après l'autre. # * Un parcours en profondeur signifie qu'on va jusqu'au bout d'une branche, puis jusqu'au bout de la branche suivante, etc. Sur cet exemple, cela signifie qu'on commence par les sommets R, a, et 1 puis on revient en arrière (en repassant par a) pour aller à 2, puis (en repassant passe par a et R,) on arrive à b, puis on (re)passe en R, en c, 3, X, 3, Y, 3, Z, 3, c, puis 4 (et à nouveau c et R). # Bien sur on peut aussi considérer des variantes où on ne compte pas les passages multiples au même sommet. #%% Implémentation en python: dictionnaire #%% Notion de dictionnaire # On ne cherchera pas à utiliser de module python spécifique pour la manipulation de graphes, et en choisit de représenter en python un graphe par deux dictionnaires. # Un dictionnaire contient un ensemble d'identifiants associés à des valeurs, il se manipule comme ci dessous: d={"hirondelle":"oiseau","python":"serpent","pomme":"fruit"} d["papillon"]="insecte" print(d) print('d["pomme"]='+d["pomme"]) # Dans cet exemple les identifiants sont "hirondelle", "python", "pomme", puis "papillon" (ajouté en exécutant d["papillon"]="insecte"). "oiseau" est la valeur associée à l'identifiant "hirondelle", tandis que "serpent" est la valeur associée à l'identifiant "python", etc. # Si on exécute par exemple d["oiseau"], on obtiendra un message d'erreur car "oiseau" n'est pas un des identifiants. #%% # Il est utile de savoir qu'avec un dictionnaire, on peut faire une boucle for, mais que dans ce cas on parcourt uniquement les identifiants (comme ci-dessous, où i prend pour valeurs successives les différents identifiants): for i in d: print(i+" → "+d[i]) #%% Choix d'implémentation des graphes # On choisit d'implémenter les graphes par deux dictionnaires: un dictionnaire qui a pour identifiants les sommets et pour valeurs la liste des arrêtes adjacentes à ce sommet, et un autre dictionnaire qui a pour identifiants les arrêtes et pour valeurs les sommets adjacents à chaque arrête. # Par exemple, Pour le graphe G₀ défini précédemment, ces dictionnaires sont: S={"C":["a","b","b","c","f"],"D":["f","g","h"],"H":["a","d","e"],"O":["c","d","e","g"],"Q":["h"],"R":["i"],"Y":["i"]} A={"a": ["C", "H"], "b": ["C", "C"], "c": ["C", "O"], "d": ["H", "O"], "e": ["H", "O"], "f": ["C", "D"],"g": ["D", "O"], "h": ["D", "Q"], "i": ["R", "Y"]} # Cela correspond à numéroter les arrêtes de la façon suivante: # a ╔═══╗ # ┌────────────────╢ H ║ # │ ┌──────┐ ╚╤═╤╝ ╔═══╗ # ╔╧═╧╗ │b d│ │e ║ R ║ # ║ C ╟─────┘ │ │ ╚╤══╝ #G₀: ╚╤═╤╝ c ╔══╧╗│ i│ # │ └────────────╢ O ╟┘ │ # f│╔═══╗ ╚╤══╝ ╔══╧╗ # └╢ D ╟──────────┘g ║ Y ║ # ╚═╤═╝ ╔═══╗ ╚═══╝ # └───────╢ Q ║ # h ╚═══╝ # 1. Écrire une fonction qui construit le dictionnaire des sommets à partir de celui des arrêtes . # 2. Écrire de même une fonction qui construit le dictionnaire des arrêtes à partir du dictionnaire des sommets. #%% II. Exemples de parcours de graphes #%% Parcours de labyrinthe: algorithme de Trémaux # On considère les graphes comme une façon de modéliser un labyrinthe: les sommets représentent les intersections, et les arrêtes sont les couloirs du labyrinthe. # L'algorithme de Trémaux est une méthode, permettant à quelqu'un qui explore un labyrinthe d'en visiter toutes les pièces (et le cas échéant de trouver la sortie) sans se perdre: # * La première fois qu'on parcourt un couloir on dessine une marque à chacune de ses extrémités (on sait que c'est un couloir que l'on n'avait pas encore parcouru s'il n'y a pas encore de marque à l'entrée de ce couloir). # * Quand on arrive à une intersection où l'on s'est déjà rendu, on revient en arrière par le couloir par lequel on est arrivé. # * Dans cette situation, et plus globalement à chaque fois qu'on parcours un couloir pour la deuxième fois, on appose une deuxième marque à l'entrée et à la sortie du couloir. # * Après qu'un couloir ait ainsi été marqué en double, on n'emprunte plus jamais ce couloir. # * Quand on arrive à une intersection qui n'a jamais été explorée (c'est à dire que l'on ne voit de marque à l'entrée d'aucun couloir), alors on dessine une triple marque à la sortie du couloir par lequel on est arrivé à cet intersection. # * À chaque fois qu'on arrive à intersection, on choisit d'emprunter un couloir qui n'a jamais été exploré (s'il y en a), sinon un couloir qui a une seule marque (s'il y en a plusieurs on choisit au hasard), ou en dernier recours le couloir qui a une triple marque. # 3. Écrire une fonction qui implémente cet algorithme. Vérifie que pour le graphe G₀, Si l'on commence en O, alors cet algorithme permet d'aller à n'importe quel sommet sauf R et Y. # 4. Cet algorithme correspond-il à un parcours de graphe en largeur ou en profondeur ? #%% Plus court chemin # On considère désormais que les différentes arrêtes n'ont pas toutes la même longueur. On ajoute donc un troisième dictionnaire qui indique la longueur de chaque arrête. Par exemple l={"a": 3, "b": 9, "c": 1, "d": 2, "e": 9, "f": 9, "g": 3, "h": 9, "i": 2} # qui indique que l'arrête "a" est de longueur 3, alors que "b" est de longueur 9, etc. Ces longueur peuvent par exemple correspondre à la distance à parcourir entre des villes, ou à des temps de trajet (ce qui ne revient pas au même si l'on ne vas pas à la même vitesse sur toute les routes). On suppose en tout cas que toutes les arrêtes ont un longueur positive. # On désigne par ℓ(S,T) la distance entre deux sommets, c'est à dire la longueur du plus court chemin entre ces deux sommets (où la longueur d'un chemin est la somme des longueurs des arrêtes qui le compose). S'il n'existe aucun chemin entre S et T, alors on considère que ℓ(S,T)=+∈fty. #%% # Pour déterminer la distance ℓ(S₁,S₂), on utilise l'algorithme suivant: # * Au fur et a mesure du calcul, on garde en mémoire une estimation de la distance ℓ(S₁,t) pour chaque sommet t. Initialement on sait juste que ℓ(S₁,S₁)=0 et que ∀ t≠S₁: 0⩽ℓ(S₁,t)⩽+∈fty. # On note donc mₛ=0 pour chaque sommet S, Mₜ=+∈fty pour chaque sommet t≠S₁ et Mₛ₁=0, de sorte que l'information dont l'on dispose est ∀ S: mₛ⩽ℓ(S₁,S)⩽Mₛ. # De plus, on peut affirmer dès à présent que dans la suite, on ne considérera pas les arrêtes qui reviennent au même sommet que celui dont elles sont parties (comme l'arrête "b" du graphe G₀). # * On commence par considérer le sommet S₁: # * Pour chaque arrête partant de S₁, si on note l sa longueur et t le sommet auquel elle mène, on peut affirmer que ℓ(S₁,t)⩽l, donc on réactualise Mₜ en le remplaçant par min(Mₜ,l). # * Si la plus courte arrête qui part de S₁ mène au sommet t₀ et est de longueur l₀, alors on peut être sur que ∀ S≠S₁: ℓ(S₁,t)⩾ l₀. # En effet tout chemin de S₁ à S commence par parcourir une arrête qui part de S₀ et a une longueur supérieure ou égale à l₀. # On peut donc réactualiser en remplaçant mₛ par max(mₛ,l₀), pour chaque S≠S₁. # * Combiné à l'inégalité précédente, cela donne en particulier que ℓ(S₁,t₀)= l₀. # * On considère ensuite le sommet t₀ obtenu à l'étape précédente: # * Pour chaque arrête partant de t₀, si on note l sa longueur et t le sommet auquel elle mène, on peut affirmer que ℓ(S₁,t)⩽l+l₀, donc on réactualise Mₜ en le remplaçant par min(Mₜ,l+l₀). # * Les valeurs V={Mₛ|S≠S₁, S≠t₀} sont les longueurs des plus petits chemins qui partent de S₁ et vont à un sommet distinct de t₀. On peut donc affirmer que ∀ S∉{S₁,t₀}, ℓ(S₁,S)⩾min(V). # En effet, le début du plus court chemin entre S₁ et S (jusqu'au premier sommet distinct de S₁ et de t₀) est forcément un des chemins dont la longueur appartient à V. # On peut donc réactualiser en remplaçant mₛ par max(mₛ,min(V)), pour chaque S∉{S₁,t₀}. # * On note t₁ tel que Mₜ₁=min(V). Comme mₜ₁=min(V)=Mₜ₁, on sait que ℓ(S₁,t₁)=min(V), et on va considérer le sommet t₁ à la prochaine étape. # * Plus généralement à la n-ième étape, on connaît déjà les longueurs ℓ(S₁,S₁)=0, ℓ(S₁,t₀)=l₀, ℓ(S₁,t₁)=l₁, …, ℓ(S₁,tₙ₋₁)=lₙ₋₁. # * Pour chaque arrête partant de tₙ₋₁, si on note l sa longueur et t le sommet auquel elle mène, on peut affirmer que ℓ(S₁,t)⩽l+lₙ₋₁, donc on réactualise Mₜ en le remplaçant par min(Mₜ,l+lₙ₋₁). # * Les valeurs V={Mₛ | S∉{S₁,t₀,…,tₙ₋₁} } sont les longueurs des plus petits chemins qui partent de S₁ et vont à un sommet distinct des tᵢ (pour les i