Arbre de poids minimal-ro et théorie des graphes
Description
Pour être clair dés le départ, je présente la source pour ceux qui connaissent un peu de recherche opérationnelle et de la théorie des graphes, puis pour ceux qui n'en connaissent rien du tout:
PCQCUP: Il s'agit de trouver l'arbre de poids minimal dans un graphe dont les sommets sont des points du plan. Chaque sommet est relié avec tout autre sommet par une arrête qui a un coût égal à la distance entre ces 2 point. L'algorithme utilisé est celui de Kruskal.
PCQNCRDT: On a n points dans le plan, il faut les relier avec (n-1) segments (chaque segment relie 2 points), de sorte qu'on ait un réseau, c'est à dire que chaque point doit communiquer avec tout autre. Le probléme est de minimiser la somme des longueurs des segments (Imaginez qu'on doit connecter des postes avec du cablage, il faudrait minimiser le cout des cables donc utiliser le minimum possible)
Ce qu'on peut remarquer, c'est qu'en placant ALEATOIREMENT n point, on aura un cout de l'arbre qui n'est pas du tout aléatoire.
J'attends vos commentaires.
PCQCUP: Il s'agit de trouver l'arbre de poids minimal dans un graphe dont les sommets sont des points du plan. Chaque sommet est relié avec tout autre sommet par une arrête qui a un coût égal à la distance entre ces 2 point. L'algorithme utilisé est celui de Kruskal.
PCQNCRDT: On a n points dans le plan, il faut les relier avec (n-1) segments (chaque segment relie 2 points), de sorte qu'on ait un réseau, c'est à dire que chaque point doit communiquer avec tout autre. Le probléme est de minimiser la somme des longueurs des segments (Imaginez qu'on doit connecter des postes avec du cablage, il faudrait minimiser le cout des cables donc utiliser le minimum possible)
Conclusion :
Ce qu'on peut remarquer, c'est qu'en placant ALEATOIREMENT n point, on aura un cout de l'arbre qui n'est pas du tout aléatoire.
J'attends vos commentaires.
Codes Sources
A voir également
- Arbre de poids minimal-ro et théorie des graphes
- Arbre de tournoi - Forum PHP
- Calculer la hauteur d'un arbre ✓ - Forum C / C++ / C++.NET
- Comment dessiner un arbre généalogique - Forum PHP
- Comment dessiner un arbre facilement - Forum Java
- Stockage de graphes - Forum Java
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.