SPANNING TREE - TUTORIEL DS

Dans cet article, nous aborderons le spanning tree et le spanning tree minimum. Mais avant de passer directement au Spanning Tree, voyons d'abord une brève description du graphe et de ses types.

Graphique

Un graphe peut être défini comme un groupe de sommets et d’arêtes pour relier ces sommets. Les types de graphiques sont donnés comme suit -

Graphique non orienté :Un graphe non orienté est un graphe dans lequel toutes les arêtes ne pointent vers aucune direction particulière, c'est-à-dire qu'elles ne sont pas unidirectionnelles ; ils sont bidirectionnels. Il peut également être défini comme un graphe avec un ensemble de sommets V et un ensemble d'arêtes E, chaque arête reliant deux sommets différents.Graphique connecté :Un graphe connecté est un graphe dans lequel un chemin existe toujours d'un sommet à n'importe quel autre sommet. Un graphe est connecté si nous pouvons atteindre n’importe quel sommet à partir de n’importe quel autre sommet en suivant les arêtes dans les deux sens.Graphique dirigé:Les graphes orientés sont également appelés digraphes. Un graphe est un graphe orienté (ou digraphe) si toutes les arêtes présentes entre les sommets ou nœuds du graphe sont dirigées ou ont une direction définie.

Passons maintenant à l'arbre couvrant les sujets.

Qu’est-ce qu’un arbre couvrant ?

Un arbre couvrant peut être défini comme le sous-graphe d'un graphe connecté non orienté. Il comprend tous les sommets ainsi que le moins d’arêtes possible. Si un sommet est manqué, ce n’est pas un arbre couvrant. Un arbre couvrant est un sous-ensemble du graphique qui ne comporte pas de cycles et qui ne peut pas non plus être déconnecté.

Un arbre couvrant se compose de (n-1) arêtes, où « n » est le nombre de sommets (ou nœuds). Les bords de l'arbre couvrant peuvent ou non se voir attribuer des poids. Tous les arbres couvrant possibles créés à partir du graphe G donné auraient le même nombre de sommets, mais le nombre d'arêtes dans l'arbre couvrant serait égal au nombre de sommets dans le graphe donné moins 1.

Un graphe complet non orienté peut avoir n^n-2 nombre d'arbres couvrants où n est le nombre de sommets dans le graphique. Supposons que si n = 5 , le nombre d'arbres couvrant maximum possible serait 5^5-2= 125.

Applications de l'arbre couvrant

Fondamentalement, un arbre couvrant est utilisé pour trouver un chemin minimum pour connecter tous les nœuds du graphe. Certaines des applications courantes du Spanning Tree sont répertoriées comme suit :

L'analyse par grappes
Planification du réseau civil
Protocole de routage de réseau informatique

Maintenant, comprenons le Spanning Tree à l'aide d'un exemple.

Exemple d'arbre couvrant

Supposons que le graphique soit -

Comme indiqué ci-dessus, un arbre couvrant contient le même nombre de sommets que le graphique, le nombre de sommets dans le graphique ci-dessus est de 5 ; par conséquent, l'arbre couvrant contiendra 5 sommets. Les arêtes de l'arbre couvrant seront égales au nombre de sommets du graphique moins 1. Il y aura donc 4 arêtes dans l'arbre couvrant.

Certains des arbres couvrants possibles qui seront créés à partir du graphique ci-dessus sont donnés comme suit :

Propriétés du spanning-tree

Certaines des propriétés de l'arbre couvrant sont données comme suit -

Il peut y avoir plus d’un arbre couvrant d’un graphe connecté G.
Un arbre couvrant n'a pas de cycles ni de boucles.
Un arbre couvrant est peu connecté, donc supprimer une arête de l’arborescence rendra le graphique déconnecté.
Un arbre couvrant est acyclique au maximum, donc l'ajout d'un bord à l'arbre créera une boucle.
Il peut y avoir un maximum n^n-2 nombre d'arbres couvrants pouvant être créés à partir d'un graphique complet.
Un arbre couvrant a n-1 arêtes, où « n » est le nombre de nœuds.
Si le graphe est un graphe complet, alors l'arbre couvrant peut être construit en supprimant le nombre maximum d'arêtes (e-n+1), où « e » est le nombre d'arêtes et « n » est le nombre de sommets.

Ainsi, un arbre couvrant est un sous-ensemble du graphe connecté G, et il n'y a pas d'arbre couvrant d'un graphe déconnecté.

Arbre couvrant minimum

Un arbre couvrant minimum peut être défini comme l'arbre couvrant dans lequel la somme des poids de l'arête est minimale. Le poids de l'arbre couvrant est la somme des poids attribués aux bords de l'arbre couvrant. Dans le monde réel, ce poids peut être considéré comme la distance, la charge de trafic, la congestion ou toute autre valeur aléatoire.

Exemple d'arbre couvrant minimum

Comprenons l'arbre couvrant minimum à l'aide d'un exemple.

La somme des arêtes du graphique ci-dessus est de 16. Maintenant, certains des arbres couvrants possibles créés à partir du graphique ci-dessus sont -

Ainsi, l'arbre couvrant minimum sélectionné parmi les arbres couvrant ci-dessus pour le graphique pondéré donné est -

Applications de l'arbre couvrant minimum

Les applications de l'arbre couvrant minimum sont données comme suit -

L'arbre couvrant minimum peut être utilisé pour concevoir des réseaux d'approvisionnement en eau, des réseaux de télécommunications et des réseaux électriques.
Il peut être utilisé pour trouver des chemins sur la carte.

Algorithmes pour l'arbre couvrant minimum

Un arbre couvrant minimum peut être trouvé à partir d'un graphique pondéré en utilisant les algorithmes donnés ci-dessous -

L'algorithme de Prim
L'algorithme de Kruskal

Voyons une brève description des deux algorithmes répertoriés ci-dessus.

L'algorithme de Prim - Il s’agit d’un algorithme glouton qui commence avec un arbre couvrant vide. Il est utilisé pour trouver l’arbre couvrant minimum à partir du graphique. Cet algorithme trouve le sous-ensemble d'arêtes qui inclut chaque sommet du graphique de telle sorte que la somme des poids des arêtes puisse être minimisée.

liste immuable

Pour en savoir plus sur l'algorithme de prim, vous pouvez cliquer sur le lien ci-dessous - https://www.javatpoint.com/prim-algorithm

L'algorithme de Kruskal - Cet algorithme est également utilisé pour trouver l'arbre couvrant minimum pour un graphe pondéré connecté. L'algorithme de Kruskal suit également une approche gloutonne, qui trouve une solution optimale à chaque étape au lieu de se concentrer sur un optimal global.

Pour en savoir plus sur l'algorithme de prim, vous pouvez cliquer sur le lien ci-dessous - https://www.javatpoint.com/kruskal-algorithm

Donc, c'est tout à propos de l'article. J'espère que l'article vous sera utile et informatif. Ici, nous avons discuté de l'arbre couvrant et de l'arbre couvrant minimum ainsi que de leurs propriétés, exemples et applications.