Spanning Tree et Spanning Tree minimum

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:

1. Algorithme de Prim
2. 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.