0:00

. 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.

Â