Enraciner un arbre donné par un graphe
🏷️ On considère ici des arbres étiquetés non ordonnés.
Dans cet exercice les étiquettes sont les entiers de 1 à \(n\), la taille du graphe qui est aussi un arbre.
À retenir :
- Une étiquette peut donc servir de clé de dictionnaire pour identifier un sommet.
Nonepeut servir à désigner le parent de la racine... qui n'existe pas !
Construire un arbre enraciné à partir d'un graphe
Un graphe est donné par un dictionnaire d'adjacences :
-
Les clés de ce dictionnaire sont les étiquettes des sommets du graphe.
-
La valeur associée à une clé est la liste des sommets adjacents à la clé, dans un ordre quelconque.
Tous les graphes ne sont pas des arbres
On rappelle qu'un arbre est un graphe, à la fois
- acyclique : il n'y a pas de cycle dans un arbre.
- connexe : un arbre est d'un seul morceau.
Dans cet exercice, tous les graphes donnés en paramètre sont des arbres, et il est inutile de le vérifier. Sur le chapitre sur les graphes, il y aura des exercices pour vérifier si un graphe est bien un arbre ; ce seront des algorithmes sur les graphes...
Un exemple simple
Le dictionnaire d'adjacences en Python graphe = {1: [2, 3], 2: [1], 3: [1]} représente le graphe suivant, qui est non enraciné.
graph LR
3("3") --- 1("1")
1 --- 2("2")Si on souhaite l'enraciner en 1, on obtient l'unique arbre enraciné non ordonné suivant que l'on peut dessiner de deux manières :
flowchart TB
subgraph "Dessin 2"
direction TB
A("1")-->B("3")
A("1")-->C("2")
end
subgraph "Dessin 1 "
direction TB
E("1")-->F("2")
E("1")-->G("3")
endChacune des deux réponses suivantes sont donc acceptées.
[1, [[2, []], [3, []]]]
[1, [[3, []], [2, []]]]
Ce qui explique le dernier test public
graphe = {1: [2, 3], 2: [1], 3: [1]}
arbre = enracine(graphe, 1)
assert (
arbre == [1, [[2, []], [3, []]]]
) or (
arbre == [1, [[3, []], [2, []]]]
)
Les tests privés utiliseront la fonction sont_similaires qu'il est conseillé de construire avant.
Exercice
Coder une fonction enracine qui prend un graphe et une racine en paramètres et qui renvoie un arbre étiqueté associé au graphe et à la racine désignée.
Un tel arbre théorique est non ordonné, ainsi la liste des enfants pourra être donnée dans n'importe quel ordre. Les tests accepteront toute variation.
Indice
On pourra compléter le code suivant :
def enracine(graphe, racine):
"Renvoie un arbre enraciné issu de racine à partir de graphe"
# fonction intérieure récursive
def construit(racine, parent):
"""Renvoie l'arbre associé à graphe dont
la racine et son parent sont donnés
"""
enfants = []
for sommet in graphe[racine]:
if ...:
enfants.append(...)
return [racine, enfants]
# La racine n'a pas de parent
return construit(racine, None)
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)