Description de l'algorithme de Prim qui construit (facilement) un arbre couvrant de poids minimal d'un graphe pondéré (connexe).
Пікірлер: 116
@nosseibagacem90145 жыл бұрын
Votre voix est parfaite pour y faire comprendre
@VictorVonYurenmaru6 жыл бұрын
Un cours bien animé, des explications claires et précises à la fois... Bon sang qu'il en faudrait plus des chaines comme ça!
@a_la_decouverte_des_graphes6 жыл бұрын
Merci beaucoup ! N'hésitez pas à parler de ma chaine autour de vous...
@HajarMahmou5 жыл бұрын
Votre rythme et vos explications sont super! Merci beaucoup
@a_la_decouverte_des_graphes5 жыл бұрын
Merci pour votre commentaire ! Une autre vidéo de la chaine est consacrée au même problème.
@wibber146 жыл бұрын
Super video, le rythme est bon ce qui rend le contenu intéressant et très utile !
@nitrogenfr6 ай бұрын
Merci infiniment monsieur pour votre chaine ! Vous avez le don pour expliquer ce que mon professeur ne parvient pas à faire.
@arilstideenfatah5 ай бұрын
Merci beaucoup pour cette super vidéo ! Grace à vous tout est compris très rapidement !
@Thedeaddu65 Жыл бұрын
Merci mon giga reuf pour cette très bonne vidéo explicative, mon prof à côté vaut tchi ! f🔥❤🔥
@samyabdouche41213 жыл бұрын
Bonsoir, je vous remercie pour cette petite vidéo bien sympathique et expliquée :)
@amineboukhris90073 жыл бұрын
merci wlh t'es le meilleur rapide efficace et net ,merci professer
@meriemel50283 жыл бұрын
Trés clair même aprés 3 ans ! Merci beaucoup
@yeosalomon93407 ай бұрын
Un cours bien détaillé très claire vraiment merci
@youbsan0013 жыл бұрын
tu as une méthode plus que fantastique. merci bcp !
@wismtree4 жыл бұрын
Très sympathique pour aborder les graphes. Merci :) PS: encore mieux en vitesse x2
@happylife93974 жыл бұрын
C'est très simple.merci monsieur.
@Skinz34 жыл бұрын
Très pédagogue, merci !
@tarekarar17364 жыл бұрын
Merci beaucoup pour votre effort et vos supers videos.
@MadDream66615 жыл бұрын
Cette vidéo me sauve pour mes exams ! Merci beaucoup, très bon contenu :)
@a_la_decouverte_des_graphes5 жыл бұрын
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 !
@MadDream66615 жыл бұрын
@@a_la_decouverte_des_graphes La vidéo sur Kruskal est de la même qualité ! Merci à vous.
@ohmeohlife30122 жыл бұрын
2 ans plus tard, cette vidéo (et celle sur Kruskal me sauve aussi pour mes examens) :)
@n0ahri6 жыл бұрын
Clair, concis et compréhensible! Merci beaucoup!
@a_la_decouverte_des_graphes6 жыл бұрын
Merci à vous pour votre avis. Je vous laisse découvrir les autres vidéos...
@nicolasbarre32373 жыл бұрын
Toujours aussi bien expliqué
@desirax21223 жыл бұрын
Super clair et j'adore la voix !
@leoslittlebash17052 жыл бұрын
Très clair, votre explication. Rien à dire j'ai tout compris 😁
@kouadiobedejean19282 жыл бұрын
bien expliquer et ça m a aider enormement
@akanicaise83205 жыл бұрын
Merci beaucoup. Très clair en un temps record.
@a_la_decouverte_des_graphes5 жыл бұрын
Merci pour votre commentaire.
@f2flooneygaming2023 жыл бұрын
Merci pour ce cours clair et précis
@franckblaise2115 Жыл бұрын
C'est cool, cette vidéo merci j'ai pu assimiler aisément la notion
@chachacha12892 жыл бұрын
Gémial, merci pour cette vidéo !
@jacerchetoui709 Жыл бұрын
merci beaucoup monsieur
@FrancisETABA-dr3qx8 ай бұрын
Merci monsieur 😭😭✊✊
@lauriot163 жыл бұрын
t'es le sang
@asmaeflory76833 жыл бұрын
Merci beaucoup♥️ TOP
@user-uw1oj4mj7z4 жыл бұрын
Merci ❤️🙏♥️
@islam69165 жыл бұрын
Super video, Merci beaucoup !
@MysteryDash5 жыл бұрын
Rien que pour les effets de flammes cette vidéo mérite un pouce bleu x)
@a_la_decouverte_des_graphes5 жыл бұрын
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...
@MysteryDash5 жыл бұрын
@@a_la_decouverte_des_graphesJe l'ai regardée aussi, super utile pour mon exam, alors merci à vous plutôt !
@a_la_decouverte_des_graphes5 жыл бұрын
MD. Tant mieux si ça vous a été utile pour vos cours.
@picadillyrun215 жыл бұрын
super vidéo très instructive. merci
@a_la_decouverte_des_graphes5 жыл бұрын
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...
@sofienzammel8751 Жыл бұрын
trés clair bravo
@biyongalain466 жыл бұрын
Merci beaucoup !
@samirelmashoubi99852 жыл бұрын
Merci beaucoup
@user-lw4jc5kt4q6 ай бұрын
Très bon cheminement
@Zamkoori-Hunter6 жыл бұрын
Merci beaucoup cette vidéo m'a bien aidé ! :)
@a_la_decouverte_des_graphes6 жыл бұрын
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...
@davidpotvin10832 жыл бұрын
Tres bonne video ! Merci
@user-uw1oj4mj7z4 жыл бұрын
Parfait♥️♥️♥️♥️
@namaku16413 жыл бұрын
merci mon reuf
@enpochetv12115 жыл бұрын
Très bonne explication ; Bravo !
@a_la_decouverte_des_graphes5 жыл бұрын
Merci ! Une autre vidéo sur le même thème est disponible sur ma chaine.
@nihadbella36110 ай бұрын
Merci ❤
@maelitoP3 жыл бұрын
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!
@a_la_decouverte_des_graphes3 жыл бұрын
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é).
@faroukantri44913 жыл бұрын
le meilleur ♥
@lydiabenz1093 Жыл бұрын
Mrc bcp 💚
@tonyelkharrat64966 жыл бұрын
top ! Une video sur L'algorithme de Kruskal serait la bienvenue
@a_la_decouverte_des_graphes6 жыл бұрын
Tony Elkharrat. Oui pourquoi pas. Mais Prim est plus simple à expliquer et à comprendre.
@a_la_decouverte_des_graphes6 жыл бұрын
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).
@tonyelkharrat64966 жыл бұрын
Super Merci ! vos videos sont excellentes , simple et comprehensible rien a dire Bravo !
@a_la_decouverte_des_graphes6 жыл бұрын
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.
@tarikomar73 жыл бұрын
merci
@imeneboudeuf93853 жыл бұрын
Merci😃
@YayA-ml8tq Жыл бұрын
excellent !!!!
@babekeryounes52722 жыл бұрын
Merci
@sob0o3 жыл бұрын
Thank you Sir.
@caso91186 жыл бұрын
MERCI BEAUCOUP !!!!
@a_la_decouverte_des_graphes6 жыл бұрын
Natacha 231. De rien. Regardez aussi les autres vidéos.
@formationfs13154 жыл бұрын
Très clair merci !
@user-hm2dk6ud3x5 жыл бұрын
perfect video
@alexandremoreau33385 жыл бұрын
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?
@a_la_decouverte_des_graphes5 жыл бұрын
alexandre moreau. Bonjour. Faire DG et Dc conduit à un total de 7*3=10 c’est à dire plus grand que l’autre option.
@alexandremoreau33385 жыл бұрын
À la découverte des graphes oups petit problème d’inattention merci.
@yezzarayene3 жыл бұрын
Mrc
@imaddezzaz99884 жыл бұрын
merci beaucoup
@Heisenberg063 жыл бұрын
merci !
@mood48604 жыл бұрын
merci💓
@linalagab3684 ай бұрын
monsieur Si on commence avec le sommet, on aura un problème et je ne comprends pas comment le résoudre.
@Amsebrid Жыл бұрын
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é
@a_la_decouverte_des_graphes Жыл бұрын
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.
@kaboreaugustin69455 жыл бұрын
bjr cher public .je cherche les different types d'algorothme de poids maximal.
@majdaelmarouni48534 жыл бұрын
merci beaucoup pour cette vidéo, svp je veux savoir avec quelle application tu as fais l'animation et les transitions des graphes
@a_la_decouverte_des_graphes4 жыл бұрын
Il y a une vidéo sur ma chaîne qui explique cela, comment je fais mes vidéos.
@aymenourdjini16645 жыл бұрын
Super
@jawadjaa14806 жыл бұрын
bonjour , je vais savoir si l algorithme de prim peut résoudre le problème de tournée de véhicules ?si oui,comment ?
@a_la_decouverte_des_graphes6 жыл бұрын
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).
@happylife93974 жыл бұрын
Avec un autre sommet de départ de Je dois trouver le même poids ??
@a_la_decouverte_des_graphes4 жыл бұрын
Oui. Pas forcement le même arbre mais un arbre avec un même poids.
@mboubasoubeyedenis9475 жыл бұрын
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
@a_la_decouverte_des_graphes5 жыл бұрын
Désolé mais je ne réponds pas à ce type de sollicitations.
@mboubasoubeyedenis9475 жыл бұрын
d'accord.
@kembocapelsii6 жыл бұрын
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 ?
@a_la_decouverte_des_graphes6 жыл бұрын
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.
@pascalortiz5 жыл бұрын
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.
@asmabgd15033 жыл бұрын
Cm vs choisiz le sommet de depart ???
@a_la_decouverte_des_graphes3 жыл бұрын
Ça n’a pas d’importance, vous pouvez partir de n’importe lequel.
@hamzaaimeche48713 жыл бұрын
Badice vien par la
@SAS0206 жыл бұрын
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 ?
@a_la_decouverte_des_graphes6 жыл бұрын
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).
@SAS0206 жыл бұрын
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