"http://www.w3.org/TR/REC-html40/loose.dtd">
Graphes, arbres, etc.Laurent Bloch |
Les lignes qui suivent empruntent beaucoup au livre d'Olivier Cogis et Claudine Robert « Au-delà des ponts de Königsberg – Théorie des Graphes » [1], qui présente une excellente introduction, rigoureuse mais acessible, ainsi qu'à Wikipédia. Cf. aussi Hopcroft et al., [2]
Un graphe G est le couple G = (X,E) où X est un ensemble non
vide fini, et E un ensemble de paires d'éléments de X. Les éléments de X sont les sommets ou les
nœuds (vertices en anglais) du graphe G, ceux de
E en sont les arêtes (edges en anglais); Si e = x,y est une arête de G, on dit que les sommets x et y,
extrémités de l'arête e, sont adjacents, ou voisins dans le graphe G,
et que l'arête e est incidente aus sommets x et y. L'ordre du graphe est le nombre de ses sommets. Le degré d'un sommet est le nombre de ses voisins. Un graphe complet est tel que tous ses sommets sont adjacents
deux à deux. Une chaîne (path) : chaque sommet est adjacent à son
prédécesseur et à son successeur, et uniquement à eux, sauf le premier
et le dernier qui n'ont qu'un seul voisin. Un cycle : chaque sommet est adjacent à son prédécesseur et
à son successeur, et uniquement à eux, sauf le premier et le dernier qui
sont de plus adjacents. Par extension : Un graphe connexe est tel qu'il existe une chaîne entre
deux quelconques de ses sommets : Voici un graphe non connexe :
1. Graphe
Définitions
Une chaîne d'un graphe G est un sous-graphe de G qui est lui-même
une chaîne.
Un cycle d'un graphe G est un sous-graphe de G qui est lui-même
un cycle.
Un parcours dans un graphe : une liste ordonnée de sommets
telle que deux sommets consécutifs soient adjacents.
Propriétés
1.0.1 Deux lemmes
Remarquons que la notion de parcours n'implique aucune restriction en termes de répétition de sommets ou d'arêtes, alors que la notion de chaîne interdit ces répétition. Le résultat suivant semble intuitif, mais l'intuition, surtout lorsqu'elle est soutenue par un dessin, peut nous abuser, alors il faut le démontrer :
S'il existe dans G un parcours reliant deux sommets x et y, alors x et y sont reliés par une chaîne de G dont les sommets et les arêtes sont des sommets et des arêtes du parcours.
Ainsi, soit le graphe suivant :
La chaîne extraite d'un parcours
fedcbabcgh est un parcours de f à h, fedcgh en est la chaîne extraite.
Proof.[Démonstration : ] S'il existe dans G un parcours P de x à y, alors il existe un parcours P' de x à y de longueur minimum h dont les sommets et les arêtes sont des sommets et des arêtes de P ; P' peut éventuellement être P. Soit :
P' = (x=x0, x1, x2, ... xh−1, xh=y) |
S'il existe deux indices i et j, tels que 0 ⩽ i < j ⩽ h et que xi et xj soient le même sommet de G, alors le parcours :
P'' = (x=x0, x1, x2, ...xi−1, xi, xj+1, ... xh−1, xh=y) |
obtenu à partir de P' en supprimant le parcours fermé entre xi et xj est encore un parcours dans G reliant x à y et dont les sommets et les arêtes sont des sommets et des arêtes de P, strictement plus court que P', ce qui contredit le choix de P' comme parcours de longueur minimum.
Par conséquent les xi, 1 ⩽ i ⩽ h, sont tous différents, et la suite P'' définit une chaîne de G qui relie x et y et dont les sommets et les arêtes sont des sommets et des arêtes du parcours, ce qui prouve le lemme.
S'il existe deux chaînes distinctes reliant deux sommets a et m d'un graphe G, alors ce graphe admet un cycle.
Cette propriété paraît si évidente que l'on hésite parfois devant la nécessité de la démontrer ; néanmoins, là aussi, l'intuition peut être détrompée ; la difficulté provient de ce que le cycle ne contient pas nécessairement a et m.
Ainsi, soit le graphe suivant :
Deux chaînes, un cycle
Proof.[Démonstration : ] S'il existe deux chaînes reliant a et m, on définit un parcours fermé en concaténant le parcours de a à m en passant par l'une des chaînes et le parcours de m à a en passant par l'autre chaîne. Soit W = ef une arête appartenant à l'un des parcours mais pas à l'autre. En supprimant W du parcours fermé on obtient un parcours P' de e à f ; le lemme de la chaîne extraite nous dit que l'on peut extraire de P' une chaîne P'' de e à f ne contenant par W. Alors P'' + W est un cycle de G.
2. Arbres
Un arbre est un graphe connexe sans cycle.
Si G est un graphe d'ordre n, G sera un arbre s'il vérifie les propriétés suivantes, dont on démontre (exercice laissé au lecteur) qu'elles sont équivalentes :
- G est connexe sans cycle ;
- quels que soient a et b, sommets de G, il existe une et une seule chaîne ab ;
- G n'est plus connexe si l'on retire une seule de ses arêtes ;
- si l'on ajoute à G une seule arête entre deux quelconques de ses sommets, on crée un cycle ;
- G est connexe et possède n−1 arêtes ;
- G est sans cycles et possède n−1 arêtes ;
Autre définition des arbres
Il est également possible de définir les arbres de la façon (récursive) suivante :
- un arbre est soit l'arbre vide soit un nœud ;
- un nœud a des fils qui sont des arbres ;
- si tous les fils d'un nœud sont l'arbre vide on dit que ce nœud est une feuille ;
- outre des fils, chaque nœud comporte une valeur ;
- si chaque nœud a n fils l'arbre est dit n-aire.
Un arbre peut en outre avoir une racine, qui est un nœud situé en haut quand on le dessine, contrairement aux arbres des forêts. Les nœuds qui ne sont pas des feuilles sont parfois appelés « nœuds intérieurs ».
Arbre binaire.
Un arbre binaire est soit une valeur particulière qu'on appelle l'arbre vide et qu'on note arbre-vide soit un triplet (valeur, fils-gauche, fils-droit) dans lesquels fils-droit et fils-gauche sont eux-même des arbres binaires.
On distingue deux sortes d'éléments dans un arbres :
- ceux qui n'ont pas de fils qu'on appellera feuilles ;
- ceux qui en ont qu'on apellera nœuds.
Dans un arbre il existe un triplet qui n'est ni le fils droit ni le fils gauche d'un autre arbre : on appelle cet arbre la racine.
Pour chaque sous-arbre on peut construire une séquence d'arbres dont le premier est la racine et dont chacun des autres est soit le fils droit soit le fils gauche du précédent dans la séquence.
Le nombre d'arbres autres que la racine présent dans un telle chaine est la profondeur à laquelle se trouve le sous-arbre. La racine est ainsi à profondeur 0, son fils droit à profondeur 1, le fils gauche de son fils droit à profondeur 2...
Combien de feuilles pour un arbre binaire complet ? Chaque nœud intérieur a deux fils, le nombre de feuilles à la profondeur h est donc 2h. La hauteur d'un arbre binaire à n feuilles est donc log2n.
Le nombre de nœuds internes d'un arbre binaire complet de hauteur h est :
|
On rappelle la démonstration de ce résultat, dit « somme de la série géométrique » ; la série géométrique de terme initial a et de raison géométrique q (réel différent de 1) est la série de terme général a.qn :
Sn = a ∑i=1n qi−1
dont la somme peut se calculer ainsi :
|
Les arbres au sens de la théorie des graphes sont des structures dotées
de propriétés mathématiques intéressantes ; l’informatique, de ce fait,
les utilise abondamment pour construire ses
structures de données. Les graphes en général sont mis à
contribution pour représenter les automates.
Références
- [1]
- Olivier Cogis Claudine Robert. Au-delà des ponts de Königsberg – Théorie des Graphes. Vuibert, Paris, 2003.
- [2]
- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Automata Theory, Languages, and Computation. Addison Wesley, 1979 – 2007.
Ce document a été traduit de LATEX par HEVEA