Structure de données et algorithmes - Spanning Tree

Un arbre couvrant est un sous-ensemble du graphe G, qui a tous les sommets couverts avec un nombre minimum d'arêtes possible. Par conséquent, un Spanning Tree n'a pas de cycles et il ne peut pas être déconnecté.

Par cette définition, nous pouvons tirer la conclusion que chaque graphe G connecté et non dirigé a au moins un arbre couvrant. Un graphe déconnecté n'a pas d'arbre couvrant, car il ne peut pas être étendu à tous ses sommets.

Nous avons trouvé trois arbres couvrant un graphique complet. Un graphe non orienté complet peut avoir un maximumnn-2 nombre d'arbres couvrant, où nest le nombre de nœuds. Dans l'exemple abordé ci-dessus,n is 3, Par conséquent 33−2 = 3 couvrant les arbres sont possibles.

Propriétés générales de Spanning Tree

Nous comprenons maintenant qu'un graphique peut avoir plus d'un arbre couvrant. Voici quelques propriétés de l'arbre couvrant connecté au graphe G -

  • Un graphe connexe G peut avoir plus d'un arbre couvrant.

  • Tous les arbres couvrant le graphe G, ont le même nombre d'arêtes et de sommets.

  • L'arbre couvrant n'a pas de cycle (boucles).

  • La suppression d'un bord de l'arbre couvrant rendra le graphe déconnecté, c'est-à-dire que l'arbre couvrant est minimally connected.

  • L'ajout d'un bord à l'arbre couvrant créera un circuit ou une boucle, c'est-à-dire que l'arbre couvrant est maximally acyclic.

Propriétés mathématiques de Spanning Tree

  • Spanning Tree a n-1 bords, où n est le nombre de nœuds (sommets).

  • À partir d'un graphique complet, en supprimant le maximum e - n + 1 bords, nous pouvons construire un arbre couvrant.

  • Un graphique complet peut avoir un maximum nn-2 nombre d'arbres couvrant.

Ainsi, nous pouvons conclure que les arbres couvrants sont un sous-ensemble du graphique G connecté et que les graphiques déconnectés n'ont pas d'arbre couvrant.

Application de Spanning Tree

Le Spanning Tree est essentiellement utilisé pour trouver un chemin minimum pour connecter tous les nœuds d'un graphe. Les applications courantes des arbres couvrants sont -

  • Civil Network Planning

  • Computer Network Routing Protocol

  • Cluster Analysis

Comprenons cela à travers un petit exemple. Considérez le réseau de la ville comme un énorme graphique et envisage maintenant de déployer des lignes téléphoniques de telle sorte que, en lignes minimum, nous puissions nous connecter à tous les nœuds de la ville. C'est là que l'arbre couvrant entre en scène.

Arbre couvrant minimum (MST)

Dans un graphique pondéré, un arbre couvrant minimum est un arbre couvrant qui a un poids minimum que tous les autres arbres couvrant du même graphique. Dans des situations réelles, ce poids peut être mesuré en tant que distance, encombrement, charge de trafic ou toute valeur arbitraire indiquée sur les bords.

Algorithme Spanning-Tree minimum

Nous allons découvrir ici deux algorithmes d'arbre couvrant les plus importants -

Les deux sont des algorithmes gourmands.