Prim's Algorithm for Minimum Spanning Trees (MST) | Graph Theory
ฝัง
- เผยแพร่เมื่อ 12 เม.ย. 2021
- We go over Prim's Algorithm, and how it works to find minimum spanning trees (also called minimum weight spanning trees or minimum cost spanning trees). We'll also see two examples of using Prim's algorithm to find minimum spanning trees in connected weighted graphs.
This algorithm is one way to solve the problem of finding a spanning tree of minimum weight in a connected weighted graph. The weight of a subgraph of a weighted graph is the sum of the weights of the subgraph's edges. So, among all spanning trees of a graph G, if we use Prim's algorithm to find a minimum spanning tree T of G, it will be a spanning tree of minimum weight/minimum cost. Note that neither spanning trees nor minimum spanning trees are necessarily unique.
Spanning Subgraphs: • What is a Spanning Sub...
Proof Every Connected Graph has a Spanning Tree: • Proof: Every Connected...
Kruskal's Algorithm for Minimum Spanning Trees: • Kruskal's Algorithm fo...
#GraphTheory #Math
★DONATE★
◆ Support Wrath of Math on Patreon for early access to new videos and other exclusive benefits: / wrathofmathlessons
◆ Donate on PayPal: www.paypal.me/wrathofmath
Thanks to Robert Rennie, Barbara Sharrock, and Rolf Waefler for their generous support on Patreon!
Thanks to Crayon Angel, my favorite musician in the world, who upon my request gave me permission to use his music in my math lessons: crayonangel.bandcamp.com/
Follow Wrath of Math on...
● Instagram: / wrathofmathedu
● Facebook: / wrathofmath
● Twitter: / wrathofmathedu
My Music Channel: / @emery3050
![[Watch Party] APL 2024 ใครชนะเข้ารอบ Hydra 🆚 Flash Wolves Talon 🆚 GGLive](http://i.ytimg.com/vi/BvuSgyLy4hA/mqdefault.jpg)
I love these graph videos from a mathematical perspective. There are way more computer science/interview prep videos all over youtube that don't explain WHY an algorithm works or graph property exists and not enough videos like these. Definitely looking forward to your future videos with the proofs.
this is the best playlist for graph theory, thank you so much
That was the clearest explanation of the Prim 's algorithm I already had in my life! Thanks!
So glad to hear it! Thanks for watching!
thanks man for making a video on such a short time. Appreciate it
My pleasure, always glad to turn around requests quickly. I don't get to do it as much these days as I used to. A request was just what I needed to get back into some graph theory lessons!
Haha, you always have a knack for covering topics that I just finished learning a month ago. Good video, though. It's also amusing to adapt Prim's to find the maximum spanning tree, and even minimum product spanning tree!
Thanks, David! Ah well, better than a year ago haha! I've been jonesing to do some more graph theory lately. Will definitely have more on spanning trees soon!
Yes CS perspective for all related videos
thank you so much
My pleasure, thanks for your support! If you're looking for more graph theory, check out my playlist: th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Please ... can you make video about the following question?
(What I found at internet is : cardinality of real irrational numbers is equal to cardinality of real numbers
so there must be bijection between them but I can't find it by myself or by internet)
The question is
what is the bijection between real irrational numbers and real numbers?
Anyone else wonder how things would have played out differently if Katniss hadn't volunteered?
I can help with the CS perspective
Thanks, Devansh! I will keep you in mind when the time comes! And anyone watching this video with CS-related questions, I implore you to ask Devansh and not me! 😂
Show that height of the cylinder of greatest volume which can be inscribed in a
right circular cone of height h and semi vertical angle α is one-third that of the
cone and the greatest volume of cylinder is
4πh³tan²α/27.
I just wanna know that how much do you rate this one out of 10 for difficulty?
I'm not sure! I'd have to go through the process of trying to solve it and actually solving it or seeing a solution to have an idea. But scales don't have meaning without context! So a 5 to me might be a 10 to someone with high school level math knowledge/experience, and a 10 to me might be a 5 to someone with more knowledge/skill. Certainly geometry, and 3d geometry, can be deceptively difficult!
Yeah. It is the fision of Geometry and diffrentiation. It is from chapter *Application of derivatives*
Could you tell when the proof of this algorithm would be explained as i am interested to know why does it work?
Thanks for watching and I am glad you're eager to know why it works - I think that's the best part! If you want it soon, I'll try to get it done soon - perhaps this weekend! We'll suppose for sake of contradiction that T, a spanning tree produced by Prim's algorithm, is not a minimum spanning tree - and proceed from there!
@@WrathofMath thanks !! waiting to see the proof video
Let T be a tree and e = (u, v) be an edge in T. Then beta(T.e) = beta(T. e),\\ beta(T)-1,\\ beta(T), otherwise.
if both u and v are stem vertices; if one of u and v is a leaf and other one is minor stem; otherwise.
Can you give me proof of this theorem??