Dans ce didacticiel, vous découvrirez le Spanning Tree et le Spanning Tree minimum à l'aide d'exemples et de figures.
Avant d'en apprendre davantage sur les arbres couvrant, nous devons comprendre deux graphiques: les graphiques non orientés et les graphiques connectés.
Un graphe non orienté est un graphe dans lequel les arêtes ne pointent dans aucune direction (c'est-à-dire que les arêtes sont bidirectionnelles).
Graphique non dirigé
Un graphe connecté est un graphe dans lequel il y a toujours un chemin entre un sommet et n'importe quel autre sommet.
Graphique connecté
Spanning Tree
Un arbre couvrant est un sous-graphe d'un graphe connexe non orienté, qui comprend tous les sommets du graphe avec un nombre minimum d'arêtes possible. Si un sommet est manqué, alors ce n'est pas un arbre couvrant.
Des poids peuvent ou non être affectés aux arêtes.
Le nombre total d'arbres couvrant avec des nsommets pouvant être créés à partir d'un graphe complet est égal à .n(n-2)
Si c'est le cas n = 4, le nombre maximum d'arbres couvrant possibles est égal à . Ainsi, 16 arbres couvrant peuvent être formés à partir d'un graphe complet avec 4 sommets.44-2 = 16
Exemple d'un Spanning Tree
Comprenons le spanning tree avec des exemples ci-dessous:
Soit le graphique d'origine:
Graphique normal
Certains des arbres couvrant possibles qui peuvent être créés à partir du graphique ci-dessus sont:
Un Spanning Tree 
Un Spanning Tree 
Un Spanning Tree 
Un Spanning Tree 
Un Spanning Tree 
Un Spanning Tree
Arbre couvrant minimum
Un arbre couvrant minimum est un arbre couvrant dans lequel la somme du poids des arêtes est aussi minimale que possible.
Exemple d'un Spanning Tree
Comprenons la définition ci-dessus à l'aide de l'exemple ci-dessous.
Le graphique initial est:
Graphique pondéré
Les arborescences possibles du graphique ci-dessus sont:
Spanning tree minimum - 1 
Spanning tree minimum - 2 
Spanning tree 
minimum - 3 Spanning tree minimum - 4
L'arbre couvrant minimum des arbres couvrant ci-dessus est:
Arbre couvrant minimum
L'arbre couvrant minimum d'un graphe est trouvé à l'aide des algorithmes suivants:
- Algorithme de Prim
- Algorithme de Kruskal
Applications Spanning Tree
- Protocole de routage de réseau informatique
- L'analyse par grappes
- Planification du réseau civil
Applications minimum Spanning Tree
- Pour trouver des chemins sur la carte
- Concevoir des réseaux tels que des réseaux de télécommunication, des réseaux d'approvisionnement en eau et des réseaux électriques.
