Création d'un arbre par les graphes

Equivalence des définitions d'arbres

Les arbres tels qu'ils sont décrits au programme de l'option Informatique sont ce qui est nommé dans Introduction à l'algorithmique [4], à la page 88, « des arbres enracinés ». La définition de départ est Graphe Non Orienté Connexe Acyclique (ou GNOCA).

Un graphe est un couple $(\ensuremath{\mathcal{E}}, \ensuremath{\mathcal{R}})$ où est un ensemble et une relation sur . Les éléments de sont dits sommets, les couples en relation sont joints par un arc. Le graphe est non orienté si on suppose la relation symétrique. Il est acyclique s'il n'y a pas de cycle, c'est-à-dire qu'il n'existe pas de liste $s_1,\ldots,s_n\ (n\ge 3)$ de sommets distincts telle que $s_k$ soit relié à $s_{k+1}$ pour tout $k$ et $s_n$ relié à $s_1$.

Théorème : On a alors l'équivalence des définitions suivantes :

1. est un arbre (GNOCA).
2. est un GNO et deux quelconques sommets sont toujours reliés par un unique chemin injectif.
3. est un GNOC et toute suppression d'arêtes le « déconnecte ».
4. est un GNOC et $card(Arcs) = card(Sommets) - 1$.
5. est un GNOA et $card(Arcs) = card(Sommets) - 1$.
6. est un GNOA et tout ajout d'arête le « désacyclise ».

Preuve :

(vi) (i) : Si est non connexe, $x$ et $y$ sont non reliés. Alors, l'ajout de l'arête $(x, y)$ ne le rendrait pas non acyclique, d'où une contradiction.

(i) (ii) : L'existence d'un chemin injectif résulte de connexe (il existe un chemin) et de la finitude (on prend un chemin de longueur minimum, il est « donc » injectif). Si on a deux chemins injectifs $a_1,\ldots,a_m$ et $\alpha_1,\ldots,\alpha_n$ joignant $(a, b)$ qui divergent au $p+1$-ième sommet, on peut définir : $q = min\,\{ k\ /\ k\ge p+1\ et\ a_k \in \{\alpha_{p+1},\ldots,\alpha_n \} \}$ ($q$ existe car $a_m = \alpha_n = b$). On a un unique $i$ tel que $\alpha_i = a_q$ et on a ainsi constitué un cycle $a_p,a_{p+1},\ldots,a_q,\alpha_{i-1},\ldots,\alpha_{p+1}$, d'où une contradiction.

(ii) (iii) : est connexe par l'existence d'un chemin et si l'on supprime l'arête $(a, b)$, alors on ne peut plus joindre $a$ à $b$ à cause de l'unicité du chemin entre les sommets.

(iii) (iv) : Une relation symétrique est un ensemble de cases cochées dans un tableau (une partie de $\ensuremath{\mathcal{E}}\times \ensuremath{\mathcal{E}}$).

Soit $s$ le nombre de sommets et $a$ le nombre d'arcs.

Si on avait $a \le s-2$, une colonne serait vide et le graphe non connexe. On a donc $a\ge s-1$. Prouvons $\{ a \le s-1 \}$ par récurrence sur le nombre de sommets $n$ : la relation est vraie pour $n=1$. Soit un graphe à $n+1$ sommets. En ôtant une arête, on le déconnexifie. On obtient $k$ composantes connexes ($k \ge 2$) qui vérifient toutes les hypothèses de (iii) et ont au maximum $n$ sommets. Pour chacune, $a_i \le s_i-1$. On somme ces relations et en ajoutant l'arête enlevée au début, on obtient la relation pour .

(iv) (v) : On a connexe et $\vert\textrm{arcs}\vert=\vert\textrm{sommets}\vert-1$. On veut acyclique.

S'il existe un cycle , il a $p$ arêtes et $p$ sommets donc $\ensuremath{\mathcal{C}}\neq \ensuremath{\mathcal{A}}$. Il existe donc un sommet qui n'est pas dans et comme est connexe, il existe un sommet adjacent. Mais ce nouveau vérifie les mêmes hypothèses : on recommence jusqu'à avoir en totalité et $\vert\textrm{arcs}\vert=\vert\textrm{sommets}\vert$, d'où une contradiction.

(v) (vi) : a $k$ composantes connexes et chacune vérifie donc $\vert\textrm{arcs}\vert=\vert\textrm{sommets}\vert-1$ car ce sont des arbres. On ajoute et on a donc $k=1$ : est donc connexe.

On a donc (i), donc (ii), donc si on ajoute une arête, on crée un cycle.

Test de connexité

Après avoir dessiné un graphe, il est nécessaire de savoir s'il s'agit vraiment d'un arbre. Pour cela, il suffit (cf. 2.3.1) de savoir si $card(\textrm{Arcs})= card(\textrm{Sommets}) - 1$ et si le graphe est connexe. Le premier test est assez facile. Quant au deuxième, il est un peu plus délicat mais reste quand même plus aisé que le test d'acyclicité.

Pour savoir si (S1,...,Sn) est connexe (Sk sommets du graphe), on définit la liste [V1;...;Vn] des voisins de Sk. On initialise un tableau de n booléens et on met le premier à true, car S1 touche S1. Puis, on met à true tous ceux que Sk touche en enregistrant ceux que l'on n'a jamais vus dans une liste. On recommence avec les nouveaux tant que la listen'est pas vide. Quand elle est vide, on regarde si tous les éléments du tableau ont la valeur true.

Cette méthode donne le test décrit par le PROGRAMME 2.3. La fonction traite permet de savoir s'il existe dans tab un élément qui n'a pas la valeur true. La fonction cree_voisins rend la liste des voisins de t. Les fonctions union et subtract sont des fonctions définis dans CAML qui réalisent l'union et la différence de deux listes au sens ensembliste.

PROGRAMME 2.3: Test de connexité

Définition de l'arbre à partir du graphe

Pour passer du graphe à l'arbre, il faut avoir d'abord écrit une fonction de dessin qui permettra de définir le graphe et qui rendra les sommets, les liaisons et la racine du « futur » arbre. Il faut aussi définir un autre type d'arbre, qui, contrairement au précédent, permettra un accès direct aux fils d'un noeud (cf. PROGRAMME 2.4).

PROGRAMME 2.4: Un autre type d'arbre

Pour créer l'arbre, on définit la matrice de voisinage du graphe : un élément v.(i).(j) est initialisé à 1 si les sommets i et j sont reliés, 0 sinon. On part alors de la racine du futur arbre et on définit ses fils comme étant ses voisins. On « coche » les voisins dans la matrice en transformant, sur la ligne qui leur correspond, les 1 en 2. Puis on recommence avec les fils de la racine. On obtient alors la fonction de transformation d'un graphe en arbre (cf. PROGRAMME 2.5).

PROGRAMME 2.5: Transformation d'un graphe en arbre