Merci pour votre commentaire ! Si le sujet des arbres de poids min. vous intéresse, je vous invite à regarder aussi celle sur l'algorithme de Kruskal (un autre algorithme. pour en construire un). Du même coup, je vous invite à regarder toutes les autres de vidéos de la chaine... si vous avez du temps...
Rien que pour ça le pouce bleu ? :-) Merci ! Regardez l'autre vidéo sur le même sujet qui présente un autre algorithme. Mais je ne sais pas s'il y a des flammes...
En fin de compte, je vais en faire une sur Kruskal. Les slides sont faits mais il faut que je l'enregistre. Elle devrait sortir dans une semaine environ. La prochaine est sur le TSP (voyageur de commerce).
Tony Elkharrat. N’hésitez pas à partager votre avis sur les réseaux sociaux ou autour de vous pour faire connaître la chaîne. À la semaine prochaine pour Kruskal.
Bonjour Monsieur, super explications, je voudrais savoir est ce que cette algorithme permets de faire toujours un seul arbre couvrant avec un seul poids minimal et cela peut importe le sommet de départ, ou pour chaque sommet on aura un arbre donné avec un score donné
Cet algorithme peut donner des arbres différents suivant l’ordre de traitement des éléments lorsque plusieurs poids sont égaux. Le cas extrême est lorsque tous les poids sont égaux. Dans ce cas n’importe quel arbre peut potentiellement être construit avec cet algorithme.
Bonjour, j'aurais aimé avoir une petite validation pour être sûr de bien avoir compris la différence entre Prism et Dijkstra. - Si on veut relier le sommet O à chacun des autres sommets par une chaîne de telle sorte qu’on minimise la distance du sous ensemble composé de toutes les chaînes reliant O à chacun des autres sommets: Est ce qu'on parle bien de l'algo de Dijkstra dans ce cas ci ? - Et si on veut relier le sommet O à chacun des autres sommets par une chaîne de telle sorte que, pour chaque sommet j, on minimise la distance du sous-ensemble composé de la chaîne reliant O à j: Est ce que ici on parle bien de l'ago de Prism ? Merci d'avance pour votre aide!
Dijkstra : calculer les plus courts chemins (plus précisement les chemins pondérés de poids minimaux) depuis un sommet de départ donné r, vers tous les autres sommets accessibles à partir de r dans un graphe orienté (ou pas) pondéré. Prim : construire, dans un graphe pondéré non orienté connexe un arbre couvrant de poids minimal. Il ne s'agit pas, dans un cas comme dans l'autre de construire une seule chaine mais bel et bien un arbre (ou une arborescence dans le cas pondéré).
Bonjour. Il y a trop de variantes de problèmes de tournées de véhicules pour répondre simplement à votre question. Par contre, l'algorithme de Prim est utilisé comme sous-partie d'un algorithme qui permet de construire des solutions approchées pour le problème du "voyageur de commerce" (par exemple l'algorithme de Christofides).
Bonjour, Je me demandais si l'algo de prim garantie que l'arbre couvrant sera de poids minimal ou l'arbre trouvé serait en quelque sorte une moyenne de tous les arbres couvrants tendent vers 0 ou un minimum? Au lieu de faire le chemin D-G-C qui a poids total de 8, si nous aurions fait D-G et D-C qui reviendrait à un poids total de 7, cela ne créerait pas un arbre de poids plus petit?
Bonjour, une chose que je ne comprend pas , pourquoi on cherche le poids min? Si ce poids représente une somme d'argent par exemple vaut mieux qu'il soit max non ?
Bonjour. Ici on se place plutôt du côté de la personne qui doit payer. Elle veut par exemple ‘louer’ des lignes à un opérateur pour assurer la connectivité entre ses sites géographiquement éloignés mais elle veut obtenir ce service en dépensant le moins d’argent possible. À elle de bien les choisir pour minimiser son coût total.
Pour trouver un arbre de poids maximal, il suffit de pondérer le graphe avec l'opposé des poids, d'appliquer Kruskal et de prendre l'opposé du résultat obtenu.
Bonjour prof, sauriez-vous comment prouver qu'un arbre couvrant de poids minimal est unique dans un cas où le coût des arêtes du graphe ne sont pas tous distincts ?
Si les arêtes ne sont pas de poids distincts (comme vous les dites dans votre question) alors l'arbre de poids min. n'est PAS forcement unique (par exemple si tous les poids sont à 1 n'importe quel arbre couvrant est de poids min.). Le bon résultat est : si les arêtes ont des poids deux à deux distincts (si les poids sont distincts) alors l'arbre couvrant de poids minimal est unique. On peut le montrer en raffinant la preuve de l'algorithme de Prim par exemple (trop compliqué pour vous l'expliquer ici).
Ah je vois plus clair merci pour l'explication. J'ai pensé également à un graphe connexe à 3 sommets et 2 arêtes de poids 1. Les poids ne sont pas 2 à 2 distincts mais l'arbre couvrant de poids min est unique. Ce qui me portait à confusion c'est que je pensais qu'un arbre couvrant de poids minimum était unique si et seulement si les poids étaient 2 à 2 distincts
Bonsoir! svp j'ai un devoir à remettre le 27 Octobre et je ne comprends pas du tout svp aidez moi, voici l'énoncé: soit G=(A,E) un digraphe pondéré Ecrire un algorithme qui cherche et affiche l'arc (U,V) appartenant à E ayant le plus petit poids oule plus faible poids. (U, V) tel que µ(U, V)=minv(a, n) ou (a, n) appartenant à E a) En utilisant la matrice d'adjacence b) En utilisant la liste d'adjacence c) En utilisant la récursivité sur la matrice d'adjacence d) Analyser la complexité de ces 3 algorithmes
![Examen de Métaheuristiques 2023/2024 [Corrigé de l'exercice 2]](/img/n.gif)
Votre voix est parfaite pour y faire comprendre
Super video, le rythme est bon ce qui rend le contenu intéressant et très utile !
Un cours bien animé, des explications claires et précises à la fois... Bon sang qu'il en faudrait plus des chaines comme ça!
Merci beaucoup !
N'hésitez pas à parler de ma chaine autour de vous...
Merci beaucoup pour cette super vidéo ! Grace à vous tout est compris très rapidement !
Votre rythme et vos explications sont super! Merci beaucoup
Merci pour votre commentaire ! Une autre vidéo de la chaine est consacrée au même problème.
Merci beaucoup pour votre effort et vos supers videos.
Merci infiniment monsieur pour votre chaine ! Vous avez le don pour expliquer ce que mon professeur ne parvient pas à faire.
Merci mon giga reuf pour cette très bonne vidéo explicative, mon prof à côté vaut tchi ! f🔥❤🔥
tu as une méthode plus que fantastique. merci bcp !
Bonsoir, je vous remercie pour cette petite vidéo bien sympathique et expliquée :)
merci wlh t'es le meilleur rapide efficace et net ,merci professer
Toujours aussi bien expliqué
Trés clair même aprés 3 ans ! Merci beaucoup
C'est très simple.merci monsieur.
Clair, concis et compréhensible! Merci beaucoup!
Merci à vous pour votre avis. Je vous laisse découvrir les autres vidéos...
Merci pour ce cours clair et précis
Un cours bien détaillé très claire vraiment merci
Très clair, votre explication. Rien à dire j'ai tout compris 😁
bien expliquer et ça m a aider enormement
Gémial, merci pour cette vidéo !
Super video, Merci beaucoup !
Super clair et j'adore la voix !
Très pédagogue, merci !
Très sympathique pour aborder les graphes. Merci :)
PS: encore mieux en vitesse x2
Merci beaucoup. Très clair en un temps record.
Merci pour votre commentaire.
super vidéo très instructive. merci
Merci pour votre commentaire !
Si le sujet des arbres de poids min. vous intéresse, je vous invite à regarder aussi celle sur l'algorithme de Kruskal (un autre algorithme. pour en construire un). Du même coup, je vous invite à regarder toutes les autres de vidéos de la chaine... si vous avez du temps...
t'es le sang
Merci beaucoup !
Merci beaucoup cette vidéo m'a bien aidé ! :)
Tant mieux si ça vous a été utile. Jetez un œil aux titres des autres, on ne sait jamais.
Si le sujet vous intéresse abonnez-vous...
C'est cool, cette vidéo
merci j'ai pu assimiler aisément la notion
Merci ❤️🙏♥️
Très clair merci !
Merci beaucoup♥️ TOP
merci beaucoup monsieur
Tres bonne video ! Merci
Merci monsieur 😭😭✊✊
Parfait♥️♥️♥️♥️
MERCI BEAUCOUP !!!!
Natacha 231. De rien. Regardez aussi les autres vidéos.
le meilleur ♥
merci mon reuf
trés clair bravo
excellent !!!!
Merci beaucoup
Cette vidéo me sauve pour mes exams ! Merci beaucoup, très bon contenu :)
Tant mieux si ça vous a été utile. Il y a une autre vidéo sur le même sujet mais traité avec un algorithme. différent. Bon courage pour vos examens !
@@a_la_decouverte_des_graphes La vidéo sur Kruskal est de la même qualité ! Merci à vous.
2 ans plus tard, cette vidéo (et celle sur Kruskal me sauve aussi pour mes examens) :)
Merci ❤
perfect video
Thank you Sir.
merci beaucoup
Merci😃
merci💓
Mrc bcp 💚
merci
merci !
Merci
Très bon cheminement
Super
Très bonne explication ; Bravo !
Merci ! Une autre vidéo sur le même thème est disponible sur ma chaine.
Rien que pour les effets de flammes cette vidéo mérite un pouce bleu x)
Rien que pour ça le pouce bleu ? :-) Merci !
Regardez l'autre vidéo sur le même sujet qui présente un autre algorithme. Mais je ne sais pas s'il y a des flammes...
@@a_la_decouverte_des_graphesJe l'ai regardée aussi, super utile pour mon exam, alors merci à vous plutôt !
MD. Tant mieux si ça vous a été utile pour vos cours.
Mrc
merci beaucoup pour cette vidéo, svp je veux savoir avec quelle application tu as fais l'animation et les transitions des graphes
Il y a une vidéo sur ma chaîne qui explique cela, comment je fais mes vidéos.
top ! Une video sur L'algorithme de Kruskal serait la bienvenue
Tony Elkharrat. Oui pourquoi pas. Mais Prim est plus simple à expliquer et à comprendre.
En fin de compte, je vais en faire une sur Kruskal. Les slides sont faits mais il faut que je l'enregistre. Elle devrait sortir dans une semaine environ. La prochaine est sur le TSP (voyageur de commerce).
Super Merci ! vos videos sont excellentes , simple et comprehensible rien a dire Bravo !
Tony Elkharrat. N’hésitez pas à partager votre avis sur les réseaux sociaux ou autour de vous pour faire connaître la chaîne. À la semaine prochaine pour Kruskal.
Bonjour Monsieur, super explications, je voudrais savoir est ce que cette algorithme permets de faire toujours un seul arbre couvrant avec un seul poids minimal et cela peut importe le sommet de départ, ou pour chaque sommet on aura un arbre donné avec un score donné
Cet algorithme peut donner des arbres différents suivant l’ordre de traitement des éléments lorsque plusieurs poids sont égaux. Le cas extrême est lorsque tous les poids sont égaux. Dans ce cas n’importe quel arbre peut potentiellement être construit avec cet algorithme.
Bonjour, j'aurais aimé avoir une petite validation pour être sûr de bien avoir compris la différence entre Prism et Dijkstra.
- Si on veut relier le sommet O à chacun des autres sommets par une
chaîne de telle sorte qu’on minimise la distance du sous ensemble composé de toutes les chaînes reliant O à chacun des autres sommets: Est ce qu'on parle bien de l'algo de Dijkstra dans ce cas ci ?
- Et si on veut relier le sommet O à chacun des autres sommets par une
chaîne de telle sorte que, pour chaque sommet j, on minimise la distance du sous-ensemble composé de la chaîne reliant O à j: Est ce que ici on parle bien de l'ago de Prism ?
Merci d'avance pour votre aide!
Dijkstra : calculer les plus courts chemins (plus précisement les chemins pondérés de poids minimaux) depuis un sommet de départ donné r, vers tous les autres sommets accessibles à partir de r dans un graphe orienté (ou pas) pondéré.
Prim : construire, dans un graphe pondéré non orienté connexe un arbre couvrant de poids minimal.
Il ne s'agit pas, dans un cas comme dans l'autre de construire une seule chaine mais bel et bien un arbre (ou une arborescence dans le cas pondéré).
bonjour , je vais savoir si l algorithme de prim peut résoudre le problème de tournée de véhicules ?si oui,comment ?
Bonjour.
Il y a trop de variantes de problèmes de tournées de véhicules pour répondre simplement à votre question. Par contre, l'algorithme de Prim est utilisé comme sous-partie d'un algorithme qui permet de construire des solutions approchées pour le problème du "voyageur de commerce" (par exemple l'algorithme de Christofides).
Bonjour,
Je me demandais si l'algo de prim garantie que l'arbre couvrant sera de poids minimal ou l'arbre trouvé serait en quelque sorte une moyenne de tous les arbres couvrants tendent vers 0 ou un minimum? Au lieu de faire le chemin D-G-C qui a poids total de 8, si nous aurions fait D-G et D-C qui reviendrait à un poids total de 7, cela ne créerait pas un arbre de poids plus petit?
alexandre moreau. Bonjour. Faire DG et Dc conduit à un total de 7*3=10 c’est à dire plus grand que l’autre option.
À la découverte des graphes oups petit problème d’inattention merci.
monsieur Si on commence avec le sommet, on aura un problème et je ne comprends pas comment le résoudre.
Avec un autre sommet de départ de
Je dois trouver le même poids ??
Oui. Pas forcement le même arbre mais un arbre avec un même poids.
Bonjour, une chose que je ne comprend pas , pourquoi on cherche le poids min?
Si ce poids représente une somme d'argent par exemple vaut mieux qu'il soit max non ?
Bonjour.
Ici on se place plutôt du côté de la personne qui doit payer. Elle veut par exemple ‘louer’ des lignes à un opérateur pour assurer la connectivité entre ses sites géographiquement éloignés mais elle veut obtenir ce service en dépensant le moins d’argent possible. À elle de bien les choisir pour minimiser son coût total.
Pour trouver un arbre de poids maximal, il suffit de pondérer le graphe avec l'opposé des poids, d'appliquer Kruskal et de prendre l'opposé du résultat obtenu.
Cm vs choisiz le sommet de depart ???
Ça n’a pas d’importance, vous pouvez partir de n’importe lequel.
bjr cher public .je cherche les different types d'algorothme de poids maximal.
Est ce que le poid min est 25 pour l activité ?
Oui, c'est dit dans la vidéo.
Badice vien par la
Bonjour prof, sauriez-vous comment prouver qu'un arbre couvrant de poids minimal est unique dans un cas où le coût des arêtes du graphe ne sont pas tous distincts ?
Si les arêtes ne sont pas de poids distincts (comme vous les dites dans votre question) alors l'arbre de poids min. n'est PAS forcement unique (par exemple si tous les poids sont à 1 n'importe quel arbre couvrant est de poids min.).
Le bon résultat est : si les arêtes ont des poids deux à deux distincts (si les poids sont distincts) alors l'arbre couvrant de poids minimal est unique. On peut le montrer en raffinant la preuve de l'algorithme de Prim par exemple (trop compliqué pour vous l'expliquer ici).
Ah je vois plus clair merci pour l'explication. J'ai pensé également à un graphe connexe à 3 sommets et 2 arêtes de poids 1. Les poids ne sont pas 2 à 2 distincts mais l'arbre couvrant de poids min est unique. Ce qui me portait à confusion c'est que je pensais qu'un arbre couvrant de poids minimum était unique si et seulement si les poids étaient 2 à 2 distincts
Bonsoir! svp j'ai un devoir à remettre le 27 Octobre et je ne comprends pas du tout svp aidez moi, voici l'énoncé:
soit G=(A,E) un digraphe pondéré
Ecrire un algorithme qui cherche et affiche l'arc (U,V) appartenant à E ayant le plus petit poids oule plus faible poids.
(U, V) tel que µ(U, V)=minv(a, n) ou (a, n) appartenant à E
a) En utilisant la matrice d'adjacence
b) En utilisant la liste d'adjacence
c) En utilisant la récursivité sur la matrice d'adjacence
d) Analyser la complexité de ces 3 algorithmes
Désolé mais je ne réponds pas à ce type de sollicitations.
d'accord.
stp j'ai besoin l'algorithme détail de ce graphe
Regardez dans un livre pour ça.
mrc ! je voudrais l'algorithme de sollin svp
Ca graphe non oriente et si le graphe oriente cmmnt faire!!
Dans le cas d’un graphe orienté il faut définir le problème car qu’est-ce qu’un arbre couvrant ?
Menehssjshhdshavusbsidbsusbwjqbisbdjsvsudvshdvgaggwjsbowboqbydbuebusbsjskaloqbudbtviytewbdiwbgzacdfvcvfvhgbgcfvgvfcfvgvfcfvgbgbhhghghyhytytrrtrdededsdswswwerdefewwqwqwqaqaqwdwswsasaswaqdwaqsbebebeicicicbdjdhdjejakakaksisisidjjjejeidididcttfcegejekekekekekkekekdidididiididveevvavavaxaxzazazazazazsbdnxncncmclnlnlnlbobovovovicuxytx
tu as une methode plus que fantastique. merci bcp !
Merci
Merci