Arbre couvrant minimum

Arbre couvrant minimum

Arbre couvrant de poids minimal

L'arbre couvrant de poids minimal d'un graphe planaire. Chaque arête est identifiée avec son poids qui, ici, est approximativement sa longueur.

Étant donné un graphe non orienté et connexe, un arbre couvrant de ce graphe est un sous-ensemble qui est un arbre et qui connecte tous les sommets ensemble.

Un graphe peut comporter plusieurs arbres couvrants différents. On peut associer un poids à chaque arête, ce qui est un nombre qui représente le coût de cette arête, et prendre la somme des poids des arêtes de l'arbre couvrant. Un arbre couvrant de poids minimal est un arbre couvrant dont le poids est plus petit ou égal à celui de tous les autres arbres couvrants du graphe.

Un graphe non orienté et général possède une forêt couvrante de poids minimal.

Un problème connu utilisant l'arbre du poids minimal est le suivant :

- On génère n points aléatoirement dans un carré de coté 1

- On génère le graphe complet dont les sommets sont les points générés

- On résout le problème de l'arbre de poids minimal

- On calcule Ln le poids total de l'arbre

Ce poids est asymptotiquement égal à {\beta} {\sqrt n } avec β = 0.658...


L'arbre couvrant de poids minimal est aussi connu sous certains autres noms, tel qu'arbre couvrant minimum ou encore arbre sous-tendant minimum.

Références

Voir aussi

Lien externe

Ce document provient de « Arbre couvrant de poids minimal ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Arbre couvrant minimum de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • Arbre Couvrant De Poids Minimal — L arbre couvrant de poids minimal d un graphe planaire. Chaque arête est identifiée avec son poids qui, ici, est approximativement sa longueur. Étant donné un graphe non orienté et connexe, un arbre couvrant de ce graphe est un sous ensemble qui… …   Wikipédia en Français

  • Arbre couvrant — de poids minimal L arbre couvrant de poids minimal d un graphe planaire. Chaque arête est identifiée avec son poids qui, ici, est approximativement sa longueur. Étant donné un graphe non orienté et connexe, un arbre couvrant de ce graphe est un… …   Wikipédia en Français

  • Arbre couvrant minimal — Arbre couvrant de poids minimal L arbre couvrant de poids minimal d un graphe planaire. Chaque arête est identifiée avec son poids qui, ici, est approximativement sa longueur. Étant donné un graphe non orienté et connexe, un arbre couvrant de ce… …   Wikipédia en Français

  • Arbre couvrant de poids minimal — L arbre couvrant de poids minimal d un graphe planaire. Chaque arête est identifiée avec son poids qui, ici, est approximativement sa longueur. Étant donné un graphe non orienté et connexe, un arbre couvrant de ce graphe est un sous ensemble qui… …   Wikipédia en Français

  • Arbre (probabilité) — Pour les articles homonymes, voir Arbre (homonymie). En théorie des probabilités un arbre aléatoire est un arbre défini en utilisant une loi de probabilité sur un ensemble d arbres (au sens de graphe). Par exemple, un arbre aléatoire à n nœuds… …   Wikipédia en Français

  • Forêt couvrante de poids minimal — Arbre couvrant de poids minimal L arbre couvrant de poids minimal d un graphe planaire. Chaque arête est identifiée avec son poids qui, ici, est approximativement sa longueur. Étant donné un graphe non orienté et connexe, un arbre couvrant de ce… …   Wikipédia en Français

  • Algorithme de Kruskal — Arbre couvrant de poids minimum L algorithme de Kruskal est un algorithme de recherche d arbre recouvrant de poids minimum (ARPM) ou arbre couvrant minimum (ACM) dans un graphe connexe valué et non orienté. Il a été conçu en 1956 par Joseph… …   Wikipédia en Français

  • Algorithme De Kruskal — Arbre couvrant de poids minimum L algorithme de Kruskal est un algorithme de recherche d arbre recouvrant de poids minimum (ARPM) ou arbre couvrant minimum (ACM) dans un graphe connexe valué et non orienté. Sommaire …   Wikipédia en Français

  • Algorithme de kruskal — Arbre couvrant de poids minimum L algorithme de Kruskal est un algorithme de recherche d arbre recouvrant de poids minimum (ARPM) ou arbre couvrant minimum (ACM) dans un graphe connexe valué et non orienté. Sommaire …   Wikipédia en Français

  • Liste De Problèmes NP-Complets — Ceci est une liste des problèmes NP complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d un problèmes de la décision. Puisqu on connaît plus de 3000 problèmes NP complets, cette liste n est pas exhaustive …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”