Hello everyone.
This is magic frequently we're going to be talking about the forward.
So an algorithm with me talking about networks.
So here we come.
OK.
So there are many different types of networks in this class.
We're discussing some of them but obviously there's many many applications.
Firstly let's just consider some those applications.
Why do we care.
Well for instance if you want to get from one place to another you have to find the optimal way to get
there.
One way from point A to Point B.
That could be people traveling on a train.
It could be a water system needing to go through the sewers to get to everybody.
It could be electrical circuits.
It could be lovesickness.
So some basic background so we can be talking about the same thing and understanding what's going on.
We have something called a network which is just a series of different nodes like one two three four
five six.
And then they have weights on them.
Sometimes those nodes could go in one direction.
Sometimes those nodes could have weights which can go in either direction.
So we have also something called a source and a sink source is where it starts.
A sink is where it has to get to.
So if you're going from here to Miami from New York to Miami you start in New York that's your source
and your sink is where you're going to.
That's Miami.
There are many different plane routes that you could take and you would like to investigate which is
the quickest exception.
Now how do you rate those weights.
It depends.
It might be the quickest.
It might be at least expensive.
There are many different factors that one could expect to find.
We could make a cut in the graph and we'll be discussing what it is it would be a partition of the graph
to cut it in half kind of.
And then we also have the capacity related to the graphs.
So for instance if you have this graph you have a source and you have a sink.
Now we just took a different graph a different set up.
There may not have straight lines and we're just pictorially mentioning it here.
So the source s the capacity is how much can go through it.
So for instance you have five 10 and 15 on the left side.
Now five 10 and 15 on the left side.
That's going to be as much as you can start with.
And you have the real true capacity at the end which is how much you can go through at the end.
So even though we have well in and beginning we actually do have 30 but it could be with even a half
more or something like that depending on what the story is.
But our sink can only accept 30.
And of course we could have multiple sinks like you might have and with the Internet this is a cut where
this is a possible hash and we're cutting the diagram in half.
And what that means is that we're chopping out one side from the other and we can stop the flow entirely.
The flow over network is the path that you take to get from one part to the next part.
So if you're going from party to party that's the flow over the network.
So the one possible path might be here shear here.
There will be a cost to that.
Another possible path would be here here here there would be a cost to that as well.
And we're going to follow the arrows and you can see that maybe you'll get into a loop like this.
Maybe you'll get out of the loop but there's many many different paths that would be examples of flow.
There is a theorem that we'll be discussing called the max flow Mencap theorem that says for any network
the value of the maximum flow the flow being how the water is getting from the source to this and getting
from point A to Point B.
That's all the different ways to get to the max flow is how much can we get through.
It's going to be equal to the capacity of the minimum cut and we'll explain what we mean by minimum
cost but let's first explain what we mean by Max flow.
So Max flow is the most that we can get through this network.
The best path to take is in other words if I have packet's that I'm sending and routing trillion over
the internet I need to find a path to do it.
And I would like to get the maximum amount through.
I'd like to find the easiest way to do it.
Now there's many different types of problems that we can have in something like this in a network.
One problem that we discussed for instance with regard to routing is the maximum flow.
But another problem of course is not just the maximum flow but the shortest path.
What's the best way for information to get from point A to Point B.
In other words the shortest route not just the maximum amount that we could push through but the shortest
route.
That's another problem.
OK.
Another problem that we might be discussing in here is another problem that we could be discussing is
something like this which is can we cover every node.
For instance if I want to send you information then I might want the shortest path if I have a network
that needs to have cars going through it or have water going through the network I might want the maximum
flow and to know the maximum flow there or I might have something like something then distributing to
everybody I would need to get something which is the minimum spanning tree is the records m s the minimum
spanning tree that tree will be the spot that hits every note so you can imagine such a scenario in
the Internet as well where perhaps I want to hit every note for whatever reason it is right or I want
to get the shortest path to somewhere or I want to make sure that I can get the maximum flow bandwidth
wise except
OK.
So let's talk about our example of routing which is we determine the path.
We have nodes ABC the fear of course and we have this is our grass.
And we have many many different paths What's the best way to get from one to the other.
Well what would you say.
One way to do it is just pick pick the cheapest route or the most expensive route depending on what
your goal has.
And then you continue to pick the cheapest from there and from there et cetera.
And there are a couple algorithms in fact that do something similar to this.
Another thing to think about within these algorithms is that you can have many different approaches.
One is to have a rule that everybody needs to take time.
Another is that you have different nodes that they could go visit and distribute in different ways.
In other words we could have something that has a centralized rule that we have together or we could
have something which is de-centralized the router knows physically connected vaporise links cost to
neighbors and that's all I need to know.
And perhaps that is enough information to do that.
Where a router just needs to know who is nearby send it in the general direction of where it's supposed
to go.
And then if it gets to that direction the closest thing in that direction the shortest distance and
direction will be the best.
That's a possibility.
Another thing is that routers changed slowly over routes change over time so we have to be aware of
that and that routes change more quickly based on updates and other stuff like that.
There's an algorithm that we're not going to discuss right now but just that you should be aware of
contextual algorithm which is the shortest path from point A to Point B if you need to link to somebody
you need to get that information.
That's how you go about it.
One of those algorithms are Dexters.
There's others not important right now but the idea is that you pick the best possibility right now
and you map out that path then you go to the next note you pick the best basically is are there you
map that out and you update everything continually doing
important right.
But you could see it's quite effective.
Come now a graph abstraction just means that we are showing the picture of it in a graph with these
weights that are assigned to it.
So don't worry about any of the fancy stuff here.
Just make sure that you understand that the picture is just a way for us to interpret what's really
happening whether it be peer to peer file sharing etc. which we'll be discussing also
some considerations that we've mentioned are that there are costs involved.
What are those costs.
Bandwidth speed physical and monetary cost policy configurations can so when deciding the route not
on the initial set up you need to consider these things.
What is your cost and what is meaningful to you.
Speed might be more meaningful than monetary cost as such might go a different route.
And as we said before you could have every run or having a global typology knowing every route or you
could have it being an iterative process where they slowly figure out whats going on etc..
Ok so here is our example of a path that we want to get from a source to really sink.
We have nodes A B C D E F G and we have a weights on them.
Now you'll notice that there are weights 5 and zero.
There are two ways that there are two types of grass that we can have one type of graph would be one
that has directions it says you can go this way you can go this way you can go this way you can go this
way you can go this way you can go this way you can go this way you cannot go back here.
It tells us we can go back and here we can go both directions in our graph.
We might just as well assume that you could only go in one direction but typically you would need to
be told that in this you might assume two.
Now there are possible paths ABC etc..
Lets track check one.
We could start at 8.
We could pick a 5 to get through.
And again we want maximum to go through a four or an eight.
I'm just going to start with this because that's the biggest so I can get 8 through this direction.
So that's 8 to the last me to get 8 through.
And there's nothing stopping me so I can get all through.
OK.
Now let's assume that I can pick any of these over here to go I'm not going to go backwards that's going
to be up at 7.
I can't go this direction because that's the zero.
I can't go this direction because it's a three.
I mean like could it doesn't seem to be that great an option six seems to be better option 4 doesn't
seem to be as great an option so if I did 8 here I could send six here.
Now I have two left so I could maybe send a different way.
But as far as getting the most through I have 8 going through.
And then I have six going through.
So there would be eight and then ignore the two for now.
And we have six and then we have six.
Now that we could do that now we can't do anything here this could except one but it's a great 0 OK.
But this can except six.
However there's one on this side.
So we're going to be seeing that the most that we could do is actually going to be well let's say that
it's
6 0.
OK.
And we are back recording's recordings.
Sorry bet.
So we're still here in the picture over here.
Which now you can see a picture with him and we have different paths that we can take.
We were saying that we have a the F G A C F G.
So if we do have 8 and we do 6 we could do six more over a year.
Now the one we're going to assume is just what's there even though that might be a little bit strange
that our source has seen as something really but look.
We have a D F G.
And that means that we could do eight 8 six would be this way and that and there's only six I went through
from the eight anyway so we have six men we have six more so that all together would get me six here
we could take different paths.
And so let's examine some of those paths.
This is a possible path that we have over here.
This was 8 and now we update it to be four what that means is
this beat.
I'm going to go this way and I'm going to go this way since the minimum is the bottleneck here.
Eight and four then 10.
The minimum is the bottleneck.
What that means is the most I can get through this whole thing is four so eight is it going to be updated.
I'm going to make that a fork because there's four left.
I'm going to put a 4 here because there's four that went through.
There's four that goes over here.
So I'm going to make this a zero.
And this a for and then there's four that's going to go to that.
So this is going to become a 10 minus four which is six.
And this is going to become a four.
So you can see at four and four because the eight became eight minus four minutes for that went through
this four went all the way through.
So this is 0 4.
Now the words for my score 0 1 and 4 1 here and 10 minus 4 6 in there.
That's one possible path which gets us to have four or weaker that is in theory one pass.
That's one possible pass.
That gives us a five total at this.
However in theory we should be able to find a way to get all of this or at least more of it going through.
So there's 13 plus four.
There are going to be in here so we have 17 that needs to get through and we need to find a way to get
it through.
Now we found a way to get some of it through.
So let's see if we could develop more.
That's one path and we'll keep this graph there.
OK.
Let's check a different another path might be this let's say the minimum 5 3 and 6 is going to be our
3.
So that means the minimum that we can get through history.
So let's send three through over here.
So that five that's right here gets updated to become five minus three is two three here.
This three we send all the way.
So we subtract that and we update this.
So it's fun.
And then we have E to G which is going to send three as well.
So it's 3 6 9 3 7.
So we are better off after the second pair.
We have the the half first and now we have the AB e.g. -- over here which gets us to 8.
Let's see if we could go any further.
Here's another possible path with its update.
The four five six path has a minimum of four.
So that path is going to have a bottleneck.
Up until 4:00.
So we can update this.
This will be one and this will be two
04.
There's one left over because there's only four being sent and there's two left over because there's
only four being sent in again.
We've updated a new path over here.
OK.
So we have nothing more to send through here.
We have nothing more to send through here.
We have one more to send through here and in theory we might be able to do it.
Let's check a different path for them.
This path that a the F G.
Let's see what that would be.
That's 4 6 2 The minimum is 2.
So we can update this by the minimum of this thing.
How are my picking pans.
In theory I should always just pick the path that has the biggest number so I have four out of two four
and zero I'm going to pick a 4.
Now I'm going to pick a 6.
Now going to pick the two.
So I update this at zero and that's going to now be.
So it's going to be 4 minus 4.
One sorry for minus two because I wanted something to group.
This is going to be too greater because I'm saying two is the minimum six minus two.
That's two now.
And two is going to give us zero.
So we see that we have 14 all together.
Now that looks pretty good because in fact we only actually had 14 so we had 17 to begin with so perhaps
we could do something more.
Let's see perhaps there's another path.
The only thing is this will give us nothing.
This will give us nothing.
This will give us one.
But as soon as we do that that one will be there.
So let's see if we could go on.
We could do this has the minimum being a one like this over here which means that we're just going to
get one more.
And now we have 15.
So patterns of flow of flow is yielding the maximum flow of various is what we have at the end.
Let's examine what this means.
Just you can see that there's a sentiment at the end here so we put a 7 in the middle.
You can see that there's a three at the end here.
So we put a 3 in a 0.
So it's interesting.
We have a zero and a 4 0 on a form for can we have any
two and three we're going to go for the three.
So let's see the pattern of flows in their directions which give the maximum simultaneous flow of vehicles
per minute is shown in figure nine point seven The arc labels and.
This is after everything is done after everything is said and done.
This is what we have.
They show the amount of note that the principle of conservation of note is respected.
A note is respected for example the Flo's entering note.
Total seven vehicles years world.
Total seven flows entering and F total seven.
With those We're going to add to the flows leaving no F which is 6 and 7.
So this is what we have where we're entering these and we're leaving this way.
We went this way exceptional.
We didn't have anything that was both directions.
So we had this.
Now this we don't end up actually reading this we don't actually need it.
So we're OK with that.
Let's see what else we have.
So this was something that was useful to us a pap.
This was a useful path.
And these are the totals of those pass so it's not just this diagram.
So it's a good start but it's not just this diagram.
What we won is after everything is said and done and you have all your pads make sure that you can write
down because you should write it down as you go.
Everything that's happening all of the different paths that these things can take.
And then you get your total that's going through here.
Now how much is our total.
Well thankfully there's three seven and four is 14 and there's eight and six which is 14 which means
that yes we are missing some because originally we had 17 but this would be a reasonable path to go
through everything.
OK.
And that's not how much we're actually sending through.
Now there was an extra in here because it started there like we said a little bit strange but that's
how it was.
But that's how much we're actually sending it.
So that is the maximum flow if we sense with these weights three three or seven three or four through
here four through here three through there.
You're there.
As time went again because it's that immediate things would have to beat up.
But this would be our maximum so of the diagram.
Now we said that there's this idea of a minimum cut we send
then you can cut this diagram and chop off all access to the end.
So for instance you could cut right here and if you chop this half the know and get to the end.
If you cut right here now and you get to the end.
In other words if you put a blocker in this network it's going to stop the flow of the network.
Now what we want to know is where is the minimum cost.
In other words Where's the stuff that we could cut the least out of that would allow us to start the
whole network.
Now this one is 16 over here 16 is a relatively big.
And that crazing this cut is 80.
That's how much the weights were all together that were sending through.
And this cut is 22.
That's also quite big.
Now what we might want to realize is that perhaps if we how much is the capacity of this how much goes
through the whole thing.
We said there's four teams going through the whole thing.
So we want to find that cut really.
That is the maximum flow the minimum cost.
The point that we could block and if we can find a way to back up just 14 and we'd get the minimum cut
and we get the easiest way to block out this network and we have to figure out what that is.
Now again you have this is our original diagram but you can see that.
Why is this 16.
You have for an 8 is 12 13 16.
In other words that's what we're chopping off cutting.
Just to be clear.
And then if we did this cut we cut the cut the cut the F and we cut c. half this cut right here which
is eight in that's three four six and five.
And if we cut this one it will have 10
11:22 as well so that's another possible cut.
Since we have these bottlenecks and we've been talking about what's the minimum cuts what's the minimum
cost.
Well it should be 40.
Why is it 14.
Well because if the maximum flow the most I can get through this whole network is 14.
Even though I originally had more but the most I can get through in any reasonable way is 40 the minimum
cut if I want to block off this that work.
Where are the spots that I could cut a minimum off of.
Exactly where it's 14.
Now how do we possibly find it.
If we check every possibility that we say let's go check every possibility got our original grant us.
Did you check every possibility of this and say wow this is the one that 5:31
10.
13:14 So this would be 14.
This right here.
Well how do you know that.
Maybe you should go to this or this or this or this or this.
Right.
Quite difficult to understand.
But let's see what happens in our final final grass.
This one over here.
You'll notice that we ended up getting stuff through here three for one in six which is our 14.
But how do we know that that's going to be that random set up.
Well if you were to come over here and you were to finish up this is a 0 0 0 0.
This cut is the cut that it gives.
It has all the zeros over there that gives everything over it so you can get that cut that gives everything
over it because you update your diagram as you go.
If you get that cut it gives everything over.
Then you'll actually get the minimum cut OK.
So let's see if we could try and do one of these ourselves.
So we're going to go to a new picture one that I very poorly Drew and see if we could solve this.
So let's see we have a b c we have a c we have a D.
Those are all kinds of paths.
In theory we could do a C B or A C D etc.
There are a lot of different possible paths of reading in my beautiful drawing I apologize.
There are a lot of different possible paths.
Let's see if we can figure out what is the miller.
Well our total capacity in and starting is seven eight nine sets to four and three.
OK.
Let's just pick the biggest ones.
And we could write that our paths as we go.
So I'm going to pick this up for and let's see.
Let's just pick the biggest paths so that's for three fives.
OK.
So I'm going to go this way because it gets the biggest thrill.
And I'm going to do that search for three fives.
OK.
So that means I have to update these the out of the four 3:5 the minimum is three points I can I can
get three three.
So if I erase this how much is going to now be going in.
Well we said that the minimum that's going to go here
is my tool and approach.
And the minimum is going to be three so I mean I can have one left over over there this is going to
be outdated.
The three is now going to be updated by three.
So it's going to be bigger.
So it's going to be six now.
Hopefully we can read this.
Now I'm going to go down to label.
This is a one OK.
I'm sorry.
That was a mistake.
Look if angst this is a one zero and I'm going to assume that that's actually a zero.
Which means I'll put a 3 over here because that's how much it's accepted.
Assume that that was that that was a that this accepted only that it had zero in place of that original
like that.
OK.
Now let's go take this three because that's the path we're going.
And we'll erase that and we'll put a zero in that's up open to zero over here.
That means we have to update this down here because that is this accepted theory except in threes.
I'm going to update this.
And now I'm going to get the five updated as well.
I'm going to update this five
so that now it's two because there's two left after three goes through.
And now this over here is going to be three grader.
So I have three up here OK.
So that's one possible path and that's right down that path that path is a C D A C D D.
And overall we were actually able to get three through.
OK.
Now let's see what other possible paths we could take if we did this the three which is the next biggest
STARTING POINT we could do this.
And then we could get a real thrill and then we can get a sex song and I started going to do a greedy
algorithm and pick my biggest ones are three six.
OK.
That means I have to update these as well.
So those three that's going to be a 0 and a 3.
So now there's nothing left over here.
Whoops call in.
There's nothing left over here and there's three already here.
I can't bring anything down but I could take three and get it over here.
That means that this is going to be three less
and this is going to be three greater
come now.
Whoops.
You should actually be a because there was one there already.
My fault.
So it's going to be three degrader.
So that was one and we'll get to four here.
OK.
So now there's nothing left that can get through here and this can go anywhere.
So we're OK now.
Let's write down that path.
That was a B A B C and that was three as well.
So now there's seven but really this was because there's one there already so that's like to actually
add anything.
What we do.
But OK let's get it started.
And let's pick the greatest number over here as well and we'll get that to them.
We could send you this way or we could send too this way but it's not going to matter because I'm going
to get stuck on one over there.
So I'm going to send you this way too this way.
And that's what happens.
So let's take this I'm going to send you this way.
I'm going to send too this way.
So let's update that.
So this is now zero.
And this is true.
Now I'm going to go this way.
I'm going to send two.
Which means that this is going to end up being a zero.
This is going to end up being a five
just zero.
And this is fine.
OK.
So that's nine.
Now this is a zero which means no more can get through.
So we know that we can't get this direction anymore.
If I were to fail and this is a serious I can't get this direction if I were to have a way to fill in
if I were to have a way to fill in this one somehow that would get me there.
This zero can do that zero can't do it the only thing left I have is a one.
So let's say I have one over here I can get it that way.
And that would be perfectly fine.
Now I could do it this way as well but that's equivalent in other words I could do a CD or I could do
a c but those two things are equivalent.
So we did Adey already Aidy
80.
We did two.
And now we're going to do a c
and we're going to do one.
So let's fix this up.
It's going to be.
Whoops.
That's Let's double check.
K.
That's my entire race.
So we have one that's going through.
So this is a zero.
Now this is a form this is going to be one going through.
So this is going to be a zero.
And this is going to be a 4.
I'm sorry at 1 0 and 1 and we see 3 6 7 8 9.
My total at this point is 9.
Like I expected I got everybody through.
Now where's the minimum cut.
This is the maximum flow in other words this path.
What were the paths.
Well if we go through it AC The gave three maybe gave three the gave two.
He gave one and altogether we have nine.
Now that is the maximum flow.
Each of these things.
So this is giving three this would giving three etc. just like we have in the other direction.
What now is our minimum cost.
Well anywhere that has a zero in front like right here for instance would be a minimum.
So this is perfectly fine because we have nine and this is three four five six seven eight nine.
So this would be our minimum cut as well because that would be where they're zeroes.
Now.
There might be other minimum cost.
We're not saying that the minimum cut can be any different.
There might be more than one option.
For instance you might want to do something like this where you cut through here and again that would
be three four or five.
Now that won't work.
OK.
But there might be other options.
Let's see.
It's OK.
That looks like a good option.
But you might possibly be able to find in options.
So that's your minimum cut that's your maximum flow.
And we were able to in fact solve the problems.
Now let's go back to our screen over here and we have like we said you draw that if you look at the
diagram you are the source of the sink.
You check the different possible paths.
Updating them as we go.
And then you get how much each is contributing to it.
So it might be worthwhile when you're doing this not only to keep a updated version and the paths but
in fact you could also write down somewhere in the middle or we hear how much each one is being is giving
out.
And then you have that as a reminder for all of these just wanting to do that which is quite helpful
to another.
So to go further now there is a homework on vailable to you that's on the drive never use and do that
FFA h w homework.
OK.
In other words there's.
Let me open it up in fact.
But is another problem I'm giving you that's the first thing
to say here it is.
Here are the numbers.
I think everything is filled in.
And the second but there are the numbers.
Solve that problem.
A is your source D is your sink and you want to get from A to D.
In the math find the maximum flow and the minimum cost of that.
Second problem design a problem yourself with at least six notes that can go in both directions.
And you should use it just have a solution that actually requires you to in fact go in both directions
and figure out and recorded the solution to your problem and the max flow men cut.
So that is a Ford Focus algorithm.
That's one of the problems that we have.
Again there's three things that we discussed.
The first is Max phloem and the second is shortest path to get from point A to Point B.
And the third is to find the minimum spanning tree.
This being the minimum spanning tree which is something that touches on three very important algorithms
three very important problems in our networks in many different algorithms in order to crunch these
for us is finding the max flow is very meaningful when talking about sending packets over the Internet
access.
OK.
Thank you very much.