Spanning Tree - Spanning tree

Un arbre couvrant (bords épais bleus) d'un graphique en grille

Dans le mathématique domaine de la théorie des graphes , un arbre couvrant T d'un graphe non orienté G est un sous - graphe qui est un arbre qui comprend tous les sommets du G . En général, un graphe peut avoir plusieurs arbres couvrants, mais un graphe qui n'est pas connecté ne contiendra pas d'arbre couvrant (voir forêts couvrantes ci-dessous). Si toutes les arêtes de G sont également des arêtes d'un arbre couvrant T de G , alors G est un arbre et est identique à T (c'est-à-dire qu'un arbre a un arbre couvrant unique et c'est lui-même).

Applications

Plusieurs algorithmes de recherche de chemin , y compris l'algorithme de Dijkstra et l' algorithme de recherche A* , construisent en interne un arbre couvrant comme étape intermédiaire dans la résolution du problème.

Afin de minimiser le coût des réseaux électriques, des connexions de câblage, de la tuyauterie, de la reconnaissance vocale automatique, etc., les gens utilisent souvent des algorithmes qui construisent progressivement un arbre couvrant (ou plusieurs de ces arbres) comme étapes intermédiaires dans le processus de recherche de l' arbre couvrant minimum. .

Internet et de nombreux autres réseaux de télécommunications ont des liaisons de transmission qui relient les nœuds entre eux dans une topologie maillée qui comprend des boucles. Afin d'éviter des boucles de pont et les boucles de routage , de nombreux protocoles de routage conçus pour ces réseaux, y compris le protocole Spanning Tree , Open Shortest Path First , protocole de routage Link-état , le routage basé sur des arbres Augmentée , etc., exigent que chaque routeur se souvenir d' un Spanning Tree.

Un type spécial d'arbre couvrant, l' arbre de Xuong , est utilisé dans la théorie des graphes topologiques pour trouver des plongements de graphes de genre maximum . Un arbre Xuong est un arbre couvrant tel que, dans le graphe restant, le nombre de composants connectés avec un nombre impair d'arêtes est aussi petit que possible. Un arbre Xuong et un plongement de genre maximum associé peuvent être trouvés en temps polynomial .

Définitions

Un arbre est un connecté graphe non orienté sans cycles . C'est un arbre couvrant d'un graphe G s'il s'étend sur G (c'est-à-dire qu'il inclut chaque sommet de G ) et est un sous-graphe de G (chaque arête de l'arbre appartient à G ). Un arbre couvrant d'un graphe connecté G peut également être défini comme un ensemble maximal d'arêtes de G qui ne contient aucun cycle, ou comme un ensemble minimal d'arêtes qui relient tous les sommets.

Cycles fondamentaux

L'ajout d'une seule arête à un arbre couvrant créera un cycle ; un tel cycle est appelé cycle fondamental . Il existe un cycle fondamental distinct pour chaque arête ne faisant pas partie de l'arbre couvrant ; ainsi, il existe une correspondance biunivoque entre les cycles fondamentaux et les arêtes qui ne se trouvent pas dans l'arbre couvrant. Pour un graphe connexe avec V sommets, tout arbre couvrant aura V  − 1 arêtes, et donc, un graphe de E arêtes et l'un de ses arbres couvrants aura E  −  V  + 1 cycles fondamentaux (Le nombre d'arêtes soustrait par le nombre de arêtes incluses dans un arbre couvrant ; donnant le nombre d'arêtes non incluses dans l'arbre couvrant). Pour tout arbre couvrant donné, l'ensemble de tous  les cycles fondamentaux E  −  V +1 constitue une base de cycle , une base pour l' espace des cycles .

Cutsets fondamentaux

À la notion de cycle fondamental s'ajoute la notion d'ensemble fondamental . En supprimant une seule arête de l'arbre couvrant, les sommets sont partitionnés en deux ensembles disjoints. Le cutset fondamental est défini comme l'ensemble des arêtes qui doivent être supprimées du graphe G pour accomplir la même partition. Ainsi, chaque arbre couvrant définit un ensemble de V  − 1 cutsets fondamentaux, un pour chaque bord de l'arbre couvrant.

La dualité entre les cutsets fondamentaux et les cycles fondamentaux est établie en notant que les arêtes de cycle ne faisant pas partie du spanning tree ne peuvent apparaître que dans les cutsets des autres arêtes du cycle ; et vice versa : les arêtes d'un cutset ne peuvent apparaître que dans les cycles contenant l'arête correspondant au cutset. Cette dualité peut également être exprimée en utilisant la théorie des matroïdes , selon laquelle un arbre couvrant est une base du matroïde graphique , un cycle fondamental est le circuit unique au sein de l'ensemble formé en ajoutant un élément à la base, et des cutsets fondamentaux sont définis de la même manière du double matroïde .

Forêts étendues

Dans les graphes qui ne sont pas connectés, il ne peut y avoir d'arbre couvrant, et il faut plutôt envisager de couvrir les forêts . Ici, il y a deux définitions concurrentes :

• Certains auteurs considèrent qu'une forêt couvrante est un sous-graphe acyclique maximal du graphe donné, ou de manière équivalente un graphe constitué d'un arbre couvrant dans chaque composant connecté du graphe.
• Pour d'autres auteurs, une forêt couvrante est une forêt qui s'étend sur tous les sommets, ce qui signifie seulement que chaque sommet du graphe est un sommet de la forêt. Pour cette définition, même un graphe connecté peut avoir une forêt couvrante déconnectée, telle que la forêt dans laquelle chaque sommet forme un arbre à sommet unique.

Pour éviter toute confusion entre ces deux définitions, Gross & Yellen (2005) suggèrent le terme « forêt couvrante complète » pour une forêt couvrante avec la même connectivité que le graphe donné, tandis que Bondy & Murty (2008) appellent plutôt ce type de forêt un « forêt couvrante maximale".

Compter les arbres couvrants

La formule de Cayley compte le nombre d'arbres couvrants sur un graphique complet. Il y a des arbres dans , des arbres dans et des arbres dans .${\style d'affichage 2^{2-2}=1}$${\displaystyle K_{2}}$${\style d'affichage 3^{3-2}=3}$${\displaystyle K_{3}}$${\style d'affichage 4^{4-2}=16}$${\displaystyle K_{4}}$

Le nombre t ( G ) d'arbres couvrants d'un graphe connexe est un invariant bien étudié .

Dans des graphiques spécifiques

Dans certains cas, il est facile de calculer t ( G ) directement :

• Si G est lui-même un arbre, alors t ( G ) = 1 .
• Lorsque G est le graphe cyclique C _n à n sommets, alors t ( G ) =  n .
• Pour un graphe complet à n sommets, la formule de Cayley donne le nombre d'arbres couvrants sous la forme n ^{n  − 2} .
• Si G est le graphe bipartite complet , alors .${\displaystyle K_{p,q}}$${\style d'affichage t(G)=p^{q-1}q^{p-1}}$
• Pour le graphe hypercube à n dimensions , le nombre d'arbres couvrants est . ${\displaystyle Q_{n}}$${\displaystyle t(G)=2^{2^{n}-n-1}\prod _{k=2}^{n}k^{n \choose k}}$

Dans des graphiques arbitraires

Plus généralement, pour tout graphe G , le nombre t ( G ) peut être calculé en temps polynomial comme le déterminant d'une matrice dérivée du graphe, en utilisant le théorème de l'arbre matriciel de Kirchhoff .

Concrètement, pour calculer t ( G ), on construit la matrice laplacienne du graphe, une matrice carrée dans laquelle les lignes et les colonnes sont toutes deux indexées par les sommets de G . L'entrée dans la ligne i et la colonne j est l'une des trois valeurs :

• Le degré du sommet i , si i  =  j ,
• −1, si les sommets i et j sont adjacents, ou
• 0, si les sommets i et j sont différents l'un de l'autre mais non adjacents.

La matrice résultante est singulière , donc son déterminant est nul. Cependant, la suppression de la ligne et de la colonne pour un sommet choisi arbitrairement conduit à une matrice plus petite dont le déterminant est exactement  t ( G ).

Suppression-contraction

Si G est un graphe ou un multigraphe et e est une arête arbitraire de G , alors le nombre t ( G ) d'arbres couvrants de G satisfait la récurrence délétion-contraction t ( G ) =  t ( G  −  e ) +  t ( G / e ), où G  −  e est le multigraphe obtenu en supprimant e et G / e est la contraction de G par e . Le terme t ( G  −  e ) dans cette formule compte les arbres couvrants de  G qui n'utilisent pas l' arête  e , et le terme t ( G / e ) compte les arbres couvrants de  G qui utilisent  e .

Dans cette formule, si le graphe donné G est un multigraphe , ou si une contraction provoque la connexion de deux sommets par plusieurs arêtes, les arêtes redondantes ne doivent pas être supprimées, car cela conduirait à un total erroné. Par exemple, un graphe de liaisons reliant deux sommets par k arêtes a k arbres couvrants différents, chacun constitué d'une seule de ces arêtes.

Polynôme de Tutte

Le polynôme de Tutte d'un graphe peut être défini comme une somme, sur les arbres couvrants du graphe, de termes calculés à partir de « l'activité interne » et « l'activité externe » de l'arbre. Sa valeur aux arguments (1,1) est le nombre d'arbres couvrants ou, dans un graphe déconnecté, le nombre de forêts couvrantes maximales.

Le polynôme de Tutte peut également être calculé à l'aide d'une récurrence de suppression-contraction, mais sa complexité de calcul est élevée : pour de nombreuses valeurs de ses arguments, le calculer exactement est #P-complet , et il est également difficile à approximer avec un rapport d'approximation garanti . Le point (1,1), auquel il peut être évalué en utilisant le théorème de Kirchhoff, est l'une des rares exceptions.

Algorithmes

Construction

Un seul arbre couvrant d'un graphique peut être trouvé en temps linéaire par une recherche en profondeur d'abord ou une recherche en largeur d'abord . Ces deux algorithmes explorent le graphe donné, à partir d'un sommet arbitraire v , en parcourant les voisins des sommets qu'ils découvrent et en ajoutant chaque voisin inexploré à une structure de données à explorer ultérieurement. Ils diffèrent selon que cette structure de données est une pile (dans le cas d'une recherche en profondeur d'abord) ou une file d'attente (dans le cas d'une recherche en largeur d'abord). Dans les deux cas, on peut former un arbre couvrant en connectant chaque sommet, autre que le sommet racine v , au sommet à partir duquel il a été découvert. Cet arbre est appelé arbre de recherche en profondeur d'abord ou arbre de recherche en largeur d'abord selon l'algorithme d'exploration de graphe utilisé pour le construire. Les arbres de recherche en profondeur d'abord sont un cas particulier d'une classe d'arbres couvrants appelés arbres de Trémaux , du nom du découvreur du XIXe siècle de la recherche en profondeur d'abord.

Les arbres couvrants sont importants dans l'informatique parallèle et distribuée, comme moyen de maintenir les communications entre un ensemble de processeurs ; voir par exemple le protocole Spanning Tree utilisé par les dispositifs de couche liaison OSI ou le Shout (protocole) pour l'informatique distribuée. Cependant, les méthodes en profondeur d'abord et en largeur d'abord pour la construction d'arbres couvrants sur des ordinateurs séquentiels ne sont pas bien adaptées aux ordinateurs parallèles et distribués. Au lieu de cela, les chercheurs ont conçu plusieurs algorithmes plus spécialisés pour trouver des arbres couvrants dans ces modèles de calcul.

Optimisation

Dans certains domaines de la théorie des graphes, il est souvent utile de trouver un arbre couvrant minimum d'un graphe pondéré . D'autres problèmes d'optimisation sur les arbres couvrants ont également été étudiés, notamment l'arbre couvrant maximum, l'arbre couvrant au moins k sommets, l' arbre couvrant avec le moins d'arêtes par sommet , l' arbre couvrant avec le plus grand nombre de feuilles , l'arbre couvrant avec le moins de feuilles (étroitement lié au problème du chemin hamiltonien ), l'arbre couvrant le diamètre minimum et l'arbre couvrant la dilatation minimale.

Des problèmes d'arbre couvrant optimal ont également été étudiés pour des ensembles finis de points dans un espace géométrique tel que le plan euclidien . Pour une telle entrée, un arbre couvrant est à nouveau un arbre qui a pour sommets les points donnés. La qualité de l'arbre est mesurée de la même manière que dans un graphique, en utilisant la distance euclidienne entre les paires de points comme poids pour chaque arête. Ainsi, par exemple, un arbre couvrant minimum euclidien est le même qu'un arbre couvrant minimum de graphe dans un graphe complet avec des poids d'arête euclidiens. Cependant, il n'est pas nécessaire de construire ce graphe pour résoudre le problème d'optimisation ; le problème de l'arbre couvrant minimum euclidien, par exemple, peut être résolu plus efficacement en un temps O ( n  log  n ) en construisant la triangulation de Delaunay , puis en appliquant un algorithme d'arbre couvrant minimum à graphe planaire linéaire à la triangulation résultante.

Randomisation

Un arbre couvrant choisi au hasard parmi tous les arbres couvrants avec une probabilité égale est appelé un arbre couvrant uniforme . L'algorithme de Wilson peut être utilisé pour générer des arbres couvrants uniformes en temps polynomial en effectuant une marche aléatoire sur le graphique donné et en effaçant les cycles créés par cette marche.

Un modèle alternatif pour générer des arbres couvrants aléatoirement mais pas uniformément est l' arbre couvrant minimal aléatoire . Dans ce modèle, les bords du graphique sont affectés de poids aléatoires, puis l' arbre couvrant minimum du graphique pondéré est construit.

Énumération

Comme un graphe peut avoir un nombre exponentiel d'arbres couvrants, il n'est pas possible de tous les lister en temps polynomial . Cependant, des algorithmes sont connus pour répertorier tous les arbres couvrants en temps polynomial par arbre.

Dans les graphes infinis

Tout graphe connexe fini a un arbre couvrant. Cependant, pour les graphes connectés infinis, l'existence d'arbres couvrants est équivalente à l' axiome du choix . Un graphe infini est connexe si chaque paire de ses sommets forme la paire d'extrémités d'un chemin fini. Comme pour les graphes finis, un arbre est un graphe connexe sans cycles finis, et un arbre couvrant peut être défini soit comme un ensemble maximal d'arêtes acycliques, soit comme un arbre contenant chaque sommet.

Les arbres dans un graphe peuvent être partiellement ordonnés par leur relation de sous-graphe, et toute chaîne infinie dans cet ordre partiel a une limite supérieure (l'union des arbres dans la chaîne). Le lemme de Zorn , l'un des nombreux énoncés équivalents à l'axiome du choix, requiert qu'un ordre partiel dans lequel toutes les chaînes sont majorées a un élément maximal ; dans l'ordre partiel sur les arbres du graphe, cet élément maximal doit être un arbre couvrant. Par conséquent, si le lemme de Zorn est supposé, chaque graphe connecté infini a un arbre couvrant.

Dans l'autre sens, étant donné une famille d'ensembles , il est possible de construire un graphe infini tel que chaque arbre couvrant du graphe correspond à une fonction de choix de la famille d'ensembles. Par conséquent, si chaque graphe connecté infini a un arbre couvrant, alors l'axiome du choix est vrai.

Dans les multigraphes dirigés

L'idée d'un arbre couvrant peut être généralisée aux multigraphes orientés. Étant donné un sommet v sur un multigraphe orienté G , un arbre couvrant orienté T dont la racine est v est un sous-graphe acyclique de G dans lequel tout sommet autre que v a un degré supérieur 1. Cette définition n'est satisfaite que lorsque les "branches" de T pointent vers v .

Voir également

• Algorithme d'inondation
• Bon spanning tree – Spanning tree pour graphe planaire intégré

Les références