. Today, we're gonna talk about minimum spanning trees. This is a terrific topic for this course, because it combines a number of classic algorithms with modern data structures to solve a variety of huge problems that are important in practical applications nowadays. We'll start with a brief introduction. What is a minimal spanning tree? Well it's a defined on a graph Now we generalized the idea of a graph one more time to allow weights on the edges, so these are positive numbers associated with each edge. And let say the graph is connected, so we have a connected graph with weighted edges, Now a spanning tree of a graph. Is a subgraph that is connected and has no cycles. So, out of all the spanning trees, we want to find one that has minimum wait. So, that's not a spanning tree, cause it's not connected. This set of black edges is not a spanning tree cause it's not a cyclic. But here's one that is a spanning tree. And if you add up the weights of all the edges, four+6+8+5+11+9+7 that's 50. And you could see, maybe you could get another spanning tree by removing this edge and adding that edge that'd have slightly higher weight. And so the goal is to find a spanning tree of minimum weight. Now, there is a bird force algorithm that is impractical, impractical and probably would be difficult even to growth up. And that is, let's try all possible spanning trees. Now, certainly, we wanna do better than that. Here are some examples of some huge spanning trees that are being worked on in practice nowadays. This is a bicycle route's in Seattle. And it kind of gives a quick way from downtown out to the suburbs. You can see. This is, the idea of an MST as a model of natural phenomenon. And there are many observed natural phenomenon that, seem to be well modeled by spanning trees. This is a purely random graph. And, a minimal spanning tree of that random graph. And this is, the, a image that came up in cancer research, having to do with the arrangement of nuclei and epithelium. And you can see that this tree that's observed in nature is quite similar in character to the MSD of the random graph, so that's another example. This is an example from image processing. A process known as dithering, to remove fuzziness in medical and other images. In computing the MSD of a huge graph built from such images is yet another application. So it's, bottom line for this introduction is, MST is easily defined. It's the, minimum weight set of edges that now connect the vertices in a way to graph. And its got the verse applications from dithering, and face verification, to road networks and satellite imagery, to ethernet networks into network designs of all kind, and it goes back a long way, to the, even early twentieth century for electrical and hydraulic networks, So that's an introduction to the idea of a minimum spanning tree.