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.