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