Tip:
Highlight text to annotate it
X
Welcome to the thirty-third lecture of graph theory. So, in the last class, so we were
studying circulations; what are circulations? It was a value is given to each arc in such
a way that for each vertex, the sum of values on the incoming arcs is equal to the sum of
values on the outgoing arcs; this should be true for every vertex in the graph, in the
network. While in the case of flow, we have two exceptions namely the source and the sink,
here we do not allow any exceptions. So, now the so we were so yesterday we did one theorems
stating that if you consider the this function defined on the set of arcs is a vector defined
on see a vector in the r raise in r raise to m and where m is the number of arcs. And
then each position corresponds to an arc, and the value on the arc corresponds to the
value of the function for that position.
So, we can we can see it as a vector and that way, we also show that so we can write this
inequality M f equal to 0, where m is the incidence matrix of the graph, digraph. So,
what was M f? The the rows are the vertices and the arcs correspond to the columns, and
for instance if x y is an arc that is x to y arc, the position corresponding to the row
x in that column will get the value one and the position corresponding to the row y in
that column will get minus 1, all other columns will other positions will be 0 right. So,
this this is easy to see, this is the way we can model that.
And the support of this vector this the the arcs on which f becomes non-zero that is what
we were studying last in the last class in the end. So we show that the support should
always contain a cycle and more over, we so that the if it was non-negative, so that means
no value was no flow was function was not taking any negative values. Then the support
should contain a directed cycle itself and of case, right so then this was this this
was where we stopped. So, the another thing we consider was a kind
of circulation associated with the cycle. So the suppose you have a cycle, this also
I thing explained in the last class. So the suppose this is a cycle, we can associate
say suppose this is a direction associated with the edges of the cycle, so like this.
Then we can associate a sense of traversal for this say, we traversal like this suppose;
and then because this arc is in the correct with respect to the sense of traversal it
is in the correct direction, so it is in the forward direction, so then we can put one
for this value; one is the value for this. And then this is also in the it is in consistent
with is consistent with the direction of traversal therefore, will put one here. But this arc
is in the round direction is the reverse direction with respect to the sense of traversal; we
will put minus 1 for that, here again 1, here minus 1, because it is in the reverse direction
say this is 1. Together this is a valid circulation, if you
put zeros for all other arcs right you know all other arcs if you put zeros. See you can
see that the incoming here is equal to the outgoing here; here also incoming here is
equal to the outgoing. And in cases like this, so both are incoming, so 1 is minus 1 and
the other is plus 1, they add up to 0 again, here both are outgoing; and one is 1 and the
other is minus 1 and we add up to 0. So therefore, this is circulation. This is
called a circulation associated with a cycle. Now that we have told that given any flow,
any circulation it support the arcs corresponding to its support means, the arcs corresponding
to the non-zero values will contain a cycle. So what we can immediately infer is that see
we can represent the entire circulation as a linear combination of the circulations associated
with the cycles.
So, what is the statement, we want to proof? So, we want to so this is the about the cycle.
So then, every circulation on a digraph is a linear combination of the circulations associated
with its cycle. How do we say this thing? So, it is a not very difficult to see.
Now that you have given a circulation f, then you know you consider the support, we will
do an induction on the number of the cardinality of the support that means, the number of arcs
with non-zero values with with respect to f right. Now, we will we know that support
contains a cycle, we will pick up that cycle suppose this is the cycle right. So with see
we can this is the cycle, and then the arcs may be something like this say, whatever is
the arc. And now we will see some arc right so it is the direction here is this or may
be this arc, let us say for a change this arc, so direction is like this. Now, we will
select a sense of traversal such that this arc get positive 1 plus 1 right, so in that
case will have to select the traversal this way right, because then this will get 1, this
will get minus 1 and so on, so that that will be the circulation associated with that cycle
this cycle with respect to this sense of traversal. Now what we can do is, there is a value of
the flow here on this arc f takes a value here, f takes a value here and so on right.
Now we can take the circulation, so that means that will correspond to a vector, where all
other places will have 0, corresponding to these arcs will have 1, minus 1 and so on.
So we have to know the arc numbers, then that will correspond to 0, minus 1 and so on. And
then we can multiply this by the the value of the function here right, and this what
what happens if i minus this for instance, if this arc is a than if i minus f of a in
to the circulation associated with this circle cycle f c we can say right f a into f c if
i. So, what I what I want to do is I find a new
new flow, new circulation by minus in f a times f c, f c being the circulation associated
with this circle with this sense of traversal, and f a being the values with respect to this
this current circulation on for this arc right. This will be is it see that this is again
a circulation, it is definitely a circulation, because as for as every vertex is concerned,
we are only reducing 0, because it is together the circulation will amount to 0 only for
that. And then therefore, the vertices will satisfy
again the conservation condition, so all the vertices, because suppose this cycle was not
involved in a certain vertex, then it want to be changed; if it is involved, the values
on the arcs will change, but together it will again satisfy the conservation condition that
means incoming arcs values on the incoming arcs will sum up to the same as sum up to
the same as the values on the some some other values on the outgoing arcs.
So then, this is the new circulation f dash equal to f minus f a times f c, this is the
value of the new circulation. Now, the good thing about this new circulation is that the
support of this f dash is at least 1 less than, the cardinality of the support of this
f dash is 1 less than the cardinality of the support of this f, why is it so? Because we
have only changed the flow the values of the circulation, the f dash change is different
from f only these edges right, and these edges, where part of the support of f therefore the
all had non-zero values before. Now one of these things where made 0, because
when you f a in to f c, when a minus from f and this arc we will get 0 right f with
respect to f dash this arc will have 0. So the support has reduced this all other arcs
may remain same or this may change but then even if this all remain non-zero, so at least
one case we have changed the value from non-zero to zero. And from now case we have change
the value from zero to a non-zero value, because we never touched any edge with non-zero value
on it right, we only manipulated the edges, where change the values on the edges, where
the value is already non-zero. So therefore, we have decreased the cardinality of the support.
So and now we can see that this is by induction, this this flow right, so that is we we see
that f equal to f dash new flow plus f a in to f c right. Now, this is a can be represented
as a linear combination or the circulations associated with cycles. And then this is also
f a times f c some some some value times a circulation associated with cycle. So therefore,
this talk together this is represented as the linear combination of circulations associated
with the cycles of the network.
So, you can also see that if the values for all non-negative, if the values for all non-negative,
then we could have done this being a little careful maybe you could have the non-negative
among the non negative numbers; so of case when the values are non-negative, we will
not only get a cycle, we will get a directed cycle in the support right.
So then we could have looked at the edges of the support, and selected the edge with
the smallest value of case it is non-negative value. And then the smallest and then that
could have been the edge a, this edge a could have been selected that way, and then the
f a and f c we will give the sense of traversal such that this becomes positive, and f a and
f c will just make the zero and all others will become non-negative again or yeah some
of them others if with the equal values some of others some other edges also may ask may
also become 0, but none of them will become negative, because if they if we are picking
up the smallest value as f f a right f of a.
So now, we can see that it was the directed cycle, and then we have reduced the cardinality
of the support by 1, and again the flow became non-negative. Therefore, we will get again
a directed cycle in the support of the new flow, and then we can pick up that or may
be by induction we know we can say that this new flow can be represented as the linear
combination of the the circulations associated with its directed cycles. And therefore, together
we can say that this new flow also the the our original flow also can be represented
as the linear combination of the circulations associated with the directed cycles.
Not only that, we because if these are all non-negative integer values, then we see that
this f a is an integer value, and then it would also mean that we could represent f
as a linear combination of the circulations associated with the the directed cycles of
the network, such that the coefficients in the linear combinations combination are positive
non-negative integers, because this f a we have selected is an non-negative integer and
here we if assume that all of them non-negative integers, then together there going all of
them are going to be non-negative integers that is also easy to see. So these are some
interesting observations regarding the circulations right.
So to summaries, what we have done, so here is we will summaries in this statement. So
every circulation on a digraph is a linear combination of the circulations associated
cycles. Not only that, every non negative circulation in a digraph is a non negative
linear combination of the circulations associated with its directed cycles. More over if the
circulation is integer valued valued, then the coefficients of the linear combination
may be chosen to be non negative integers. So that is the point.
So, now the next statement, we will we will be started this the study of the circulations
with one question namely the directed directed paths x y paths in a network; in the network
in x y, we were interested in the question, how many directed paths are there in a it
is not in network, in a directed graph? Given a directed graph with x and y has to special
vertices, we can says source and sink, how many directed paths are there between x and
y? This is what we talked about the communication networks, and we were interested to see, how
reliable this network; in the sense are not reliable, and what was how right…
So in fact, if a if somebody some enemy is trying to the the network, so for instance
if some arc is broken, then will the communication between x and y be destroyed that was the
question we raised. So, we were we were we were saying that if we had several edge, disjoint
edge, disjoint paths between x and y, then the enemy has to break at least so many edges
right. So if there are k edge disjoint paths between x and y, it is clear that the enemy
has to at least break k edges, so that the communication between x and y is broken.
So that is why we were interested in the question, how many edge disjoint paths are there between
x and paths x and y? Now, we see that we can answer this question by the max flow min cut
theorem in the following way. So, this questions you see, you can easily see that if there
are so many edge disjoint paths, suppose k edge disjoint paths between x and y, and we
can we can construct network from this digraph by putting a value of 1 on each of the arcs
right each of the arcs. So then now we see that, so see this value
of one is the capacity of each arc, we can think that the capacity of each arc is this
one one just unit unit capacity arcs. Now the question is how many arcs are there? So
we can ask the same question, so how how big a flow can we have in the in this network
in this network. See, one easy thing to see is that if there a k arc disjoint paths a
k units of flow can go from x to y, because a flow of value k is possible, because through
each directed path, you can push one flow right that is very clear. So, if you add plus
1 1 1 along each of the directed paths and puts 0 0 everywhere else it is definitely
a flow with value k. But the question is, is it the maximum possible?
So can it be more than that right. So the we see that now we will say that in fact it
will be equal to the maximum flowing this network, because of the maximum or in other
words, if the maximum flow in this network the value of maximum flow in this network
will actually give us the number of arc disjoint paths between x and y.
So one while one direction is direct that means, if there are so many arc disjoint path,
the value of the flow has to be at least as much as this is clear we want to show the
other side. That means if there is a flow of value k, then there are k arc disjoint
paths in the network, how will you do that? So, it is so suppose there is a flow of value
k here right.
Now, what will happen, if I introduce this edge, an x y edge like we were telling in
the beginning this was the network. So, now we add this new edge, this edge, say this
edge right, this is the y to x edge, backward edge; and we have a flow here. So, we will
give the value of that flow as the flow as a the the function value should be defined;
for instance if f is the flow here let f of this arc be defined as f of this arc say,
let it is a is defined as the value of the flow in the in this network right from x y
flow. In that case what will happen, we have already
discuss this thing, then this is the way to convert the flow to the circulation, this
becomes a circulation, because every intermediate node was satisfying the conservation condition
before except x and y. Now if you put like this, then this and this also will satisfy
the conservation condition. Now this is become a circulation.
Now the question is converted to the circulation; now we know that so if the value here it is
value of f some positive integer value, and then these are all 1 1 1 the capacities right.
And now we can see that, because this is an integer positive integer valued function,
and so we can we can represent this circulation is a linear combination of directed cycles,
linear combination of directed cycles with non-negative coefficients, in the linear combination
the coefficients can be selected as non- negative integers also.
So in that case, what will happens for instance, if in that vector look at the position corresponding
to this arc, there we have value of f; and all other arcs are ones right now they should
be part of some cycle, but that cycle may be like this right, so you have this directed
cycle, so it should go like this and then come like this. So, see the coefficient cannot
be more than one for that cycle, because this cycle cannot get a coefficient more than 1,
because if you get more than 1, then these arcs will get value more than 1 here, but
there is only one here right, because that is non-negative every where its non negative
coefficient that we are taking once we take it something more than one, and how will you
balance this right? So for this edge, we can only have one right
therefore, we see that the this is coefficient for this cycle will be 1 and then but then
how will you get value of f, we will have we will you have to get several such cycles
to add up to this to make value of f for this, so we should the situation will be like this,
it will be one directed path here and making this cycle right, and there will be another
directed path here, another directed path here and making this cycle, and then there
will be another directed path, how many? Each of them will be contribute one each and finally,
we make value of f we will will have to get value of f such directed paths here; so forming,
the completing the cycle with this edge right. So they should be to form this value of f,
they should be value of f number of directed paths between x and y. So if the value of
f, the flow value of the flow is k, then we should have k directed paths between this
and this, so that is vertex. So, what we have showed is essentially the number of directed
paths between x and y will be equal to the value of the flow. So the first we showed
there if there are so many directed path, then we can easily could construct a flow
with value equal to k, where k is the number of directed paths. We just have to put ones
along each at the directed path, the edges on each of the directed paths; see this will
and all every other edge get 0. So it is very easy to verify that this is the flow, and
then the value of this is just k. Now, we cannot get more than this, because
if suppose there is a flow with value k, then like you have seen here we should be able
to represent the corresponding circulation, which I have created like this by putting
this x y edge as a non-linear combination of directed cycles and using non negative
integer coefficients, using non negative integer coefficients.
So therefore, it means that we should have to get this edge represented right, we need
so many directed cycles, because k directed cycles are required. And then each of them
have to be coming from different directed paths, so they have to be they have to be
at least k directed paths, this is what it says. So this we if the value of the flow
was k, then they will get k directed paths. So therefore, the it says that the number
of directed paths in this network in this directed graph is equal to the value of the
flow in the corresponding network if you put the capacity is to 1. And we also know that
by the max flow min cut theorem that this value of the flow is equal to the capacity
of the minimum cut, minimum cut. And which means that, the number of directed path between
arc disjoint directed path between x and y will be equal to the number of minimum cuts
number of edges, forward edges in the min cut, the capacity of the min cut right number
of forward edges, because the capacities of one here number of edges in the min cut. So
that that max flow min cut theorem becomes the Menger’s theorem for the directed case
by considering it that way right. So, by this thing, we conclude that.
And then now our intention in the because the the about flow was there are several things
to study, we will we do not have several hours to spend on that. So, in this class and possible
in next class, we will we will consider some of the important topics associated with the
flows, what at least to get familiar with it, we we want to able to and get in to it
in any reasonable depth, so we will quickly mention some of the terminology and some of
the associated with this thing, and may be some of the questions associated with the
flows.
The as in now see we go back to this equality m times f equal to 0, so this f correspond
to the flow sorry circulation that is the vector corresponding to the circulation, where
the vector means, if you consider as a vector each component correspond to an arc, there
the value of the circulation on that arc will be the component value. So m being the incidence
metrics m into f equal to 0, 0 being the zero vector right. This is an n by m metrics, m
being the number of arcs, n being the number of vertices; and this is m by 1 vector, and
then this is and n by one vector right. So, the essentially, this was representing
the conservation condition at each vertex that means, the incoming arcs, the sum of
the values of the circulation on the incoming arcs will be equal to the some of the values
on the outgoing arcs, for each vertex that is what it was say right. But then you see
that this this is the set of if you consider all the flows, all the set of all circulations,
then that set is a vector space, because the this these are the set of vectors, which when
multiplied with m m f makes it 0, takes it to 0 right.
So and not only that, so the you can see that it is the orthogonal complement to the rows
of row space of this m; for instance if you if you consider the rows of m, essentially
it is the orthogonal component complement right. So that is the next statement circulation
space c of a digraph d is the orthogonal complement of the row space of this incidence matrix
right.
So then incidence now, let study so we know we know enough about the circulations now,
let see what is what about its orthogonal complement, the row space of the incidence
matrix m, what is it? So, suppose you consider any member of this space, this orthogonal
complement of this circulation space, the space of the circulations sorry orthogonal
complement of this circulations, circulation space. Then let say let us consider a vector
g right.
So if this is a in the orthogonal complement of the circulations space that means in the
row space of the incidence metric, then we should be able to write this as p times m
right, where p belongs to some r raise to v right, where where see is like corresponding
to the vertices of the corresponding to the vertices of the graph, we have a vector here
p. And then for each vertex, we have a position in the vector, we have the component position
in the vector, and there we have certain values. And so that is how this is multiplying, it
should see the it will it will pick up the the the value p of x, the corresponding to
the vertex x will multiply the row corresponding to x, and then they will it will then those
after multiplying the row corresponding to x with p of x, we will sum up that is what
g is.
So essentially, that is the definition of in the m, when g is a member of the the row
space of this thing. So we can always write it like this, where p is a vector. So, but
what is thus mean? So this means that for instance here, we call that m is a matrix,
where these are all rows, and these are all arcs a 1, a 2 some a m right arcs. Now, when
I multiply with p say p 1, p 2, p n, so what will happen in the what what will you get,
so we will get a vector corresponding to so right… So the each arc, there will be some
entry here right, so this is a 1, a 2, a m, so what will be there, what will be the entry
in the a i, the correspond the entry corresponding to the i th arc, this is a i.
So you see that, here there are most of the entries are 0s, there is a one entry, there
is a minus one entry, what is what will this one entry correspond? Suppose this is x and
this is y, then the arc a i is x y; if arc a i is x y x to y arc, then at in this row,
we will have one, and in this row we will have minus 1, all other places were 0. When
we multiply this, then you can see that this will not contribute, and this and this will
contribute.
So therefore, the value here will be this is x, so we have to pick up p x from here
and this y we have to pick up p y from the corresponding position. So we will get p x
minus so p x minus p y or maybe you can say p of x minus p of y, if you consider this
p as a function right p of x minus p of y. So if you consider this as a certain some
potential like considering in an analogy with electrical networks, if I consider this as
potential associated with each vertex, then the value on the arc is the potential difference
right for instance, so for instance we see that the network each has a potential value
this is p of 1, this is p of 2 and this is p of n. And whenever this edge is there, we
will see what we see here has the value g, g of a is equal to say for instance this is
p of x and this is p of y, then we see p of x minus p of y, where this is arc from x to
y right this what we see. So, we can interpret as the members of the
rows space of the incidence matrix as this, so like representing the potential differences,
where p is the p represents the potential the vector corresponding to the the function
corresponding to the potentials right.
Now, so this tensions space also they they also be have analogous to the circulation
space, circulation space and for instance many other theorems that we have studied for
circulations can be imitated for that tensions also. For instance, we can see that see an
equivalent thing like like there are cycles in the case of circulations, we can consider
a bond in the case of tensions right.
What is the bond? Bond means ah so when we consider a cut, edge cut, and if it is minimal,
then it is called a minimal edge cut is a bond; for instance you can consider a collection
of vertices x and then these are the this is the edge cut corresponding to it right.
Now you can look at the edge cut, the minimal edge cut corresponding for instance no smaller
collection of edges, no proper subset of this edges form an edge cut, then it is got a it
is called a bond; you can easily see with some thought you can easily understand that
if it is a bond, then both side of the bond has to be connected; is it not? Because for
instance if it was disconnected for instance, if it is an edge cut, then you see this is
also an edge cut, this is also an edge cut, you do not need all of this thing, because
this will be one edge cut between this and this.
But on the other hand, if it was if both the sides are connected, so if you take any proper
subset of this edges was if I take this, then this edge can still connect this side with
this side, so they would not become an edge cut; this along cannot become an edge cut
at all. This is very different from this situation, where suppose this is two parts right if these
two parts, then you you need only this much to define a cut with because this portion
will be separated from this portion by this set of edges.
So the it is the minimal edge cuts, bonds are minimal edge cuts. Now the bonds will
play the equivalent role in that case of tensions, what there all equivalent to the role, the
cycles play in the case of circulations. Let see for instance some another analogous theorems.
So we can for instance the way we associated a circulation with a cycle, we can associate
with the associated tension with the bond like this. We can we can suppose a bond B
is given, then we can define a tension by assigning one, if a is a forward arc of the
bond that means if it is an outgoing arc with respect to bond, you can always consider a
sense of direction for instance, if this is the bond then so for each forward some other
forward some of the arcs are forward arcs some arc some reverse arcs right.
Now for the forward arcs let us put 1, and for the reverse arcs let us put minus 1 right.
So this will be a this will be a tension associated with the the bond. Why is it a tension, one
may for in the case of circulation, it was very easy to check, we will just made sure
that the conservation condition is valid everywhere. Here how do we check it? We just have to come
up with the potential function, which will which will tell us that this is indeed a indeed
a tension, so the potential we can gave us for instance we can assign once to each of
the vertices here so 1s and 0s to each other vertices on this side. Now you see if you
take any edge here that is 1 minus 1, the potential difference, so g will be 0 on all
these things right. Here also g will be 0 on all the arcs inside this; across we will
see 1 here and 0 here, so 1 minus 0 is 1, and here we see 0 minus 1 it is minus 1; therefore,
this is indeed a tension. See the way we are verifying how it is a tension, we are just
trying to identify a potential function on the set of vertices that p function, such
that p m is equal to g right. So so g is the function which I have designed
an arc set I have to just show a function on the set of vertices at the p m is equal
to g. We have already seen that to see this thing it is enough to make sure that for each
arc I can represent g of a is equal to p of x minus p of y, where a equal to the arc x
x y x to y arc right so that is what we have done. We if we assign values one to all the
vertices here and assigns 0s to all the vertices here, then p of x minus p of y happens to
be this function that means, on the arcs inside within this we get 0 and arcs within this
we get 0, across we get one if it is a forward arc, minus 1 if it is a reverse arc.
Therefore it is indeed a tension, so a tension associated with the bond. So in comparison
with our earlier theorems, we can say that every tension in a digraph is a linear combination
of the tensions associated with its bonds. But for that, we need an analogous statement.
Just before that we need this statement, let g be a non zero tension in a digraph, then
the support of g contains a bond; more over if g is an if g is an non negative, then the
support of g contains a directed bond. So this is analogous to the statement that
suppose we are given a circulation, then the support of the circulation contains a cycle.
So here analogous if you are given a tension, non zero tension of case non zero circulations
there, here non zero tension here. Then in this support of this tension that means, in
the if you collect the arcs, if you consider this sub graph corresponding to the arcs,
where the values of the tension is non zero, then it should contain a bond, it should contain
a bond like in the circulation case, when we collect a arcs which have non zero values,
that arcs sets in the sub graph corresponding to that arc set, we should have a cycle right.
So why is this bond required here, it is a easy to see, because you see there is a it
is a non zero, it has a non zero, it is a non zero tension therefore, at least there
is a one arc say a equal to let us say a a equal to x y sorry have at least one arc a
is equal to x y, such that p of x minus p of y right, so p being the if you if you assume
that g equal to p m right some p is there such that we can be represented as p m so
this is g of a right. So this arc using the support right, because
its non-zero p x is here p x is different from here, p x is not equal to p of y right.
Now what would you do is, we we can collect all the vertices u element of v, such that
p of u is equal to p of x right. So we can collect this set x such that the potential
value is equal to p of x for all these things. Now you know it is not the entire vertex set,
because p of y is at least is different from p of x.
So now this x will be this, so y should be at least outside, and you know this edge,
this out going edge x to y right x to y is in the cut between x and y. Now you see that
if we consider all the arcs, which are out going right, so and then some arcs will be
incoming right, now this is indeed a cut right this is indeed a cut, they it can be just
y here, but at least one vertex is there namely y then this because this is a cut, edge cut
there is a minimal edge cut inside this we can… So we need to show that this all these
things are non negative, because this is in the support we are saying that with inside
this support, we have a cut right. We are but these are all non zero, because
we have collected all the vertices, which have potential values equal to x, so these
values are different from x, so the values on this thing is p of x minus something here.
So because this is different here and here it will be different values, then definitely
the value on the g of g value on the arc, the tension value on the arc will be definitely
non-zero. So therefore, this is as a subset of… This is indeed a subset of the support,
this is indeed a sub this this is indeed a subset of this support and within this edge
cut we will be able to get a minimal edge cut. So therefore, there is a bond in the
minimal edge cut, which is a subset of support of the tension.
Now, you can easily see that suppose we have suppose our tension given tension g was non
negative right suppose our given tension was non negative, and not only non negative suppose
it was sorry if it was non negative, then what is I had taken this among all these values
potential values I took the biggest potential value say p of x was such that it is the biggest
potential value, they cannot be all equal, because there is at least one arc which is
non-zero therefore, they should be some values which is smaller than p of x, p of x is the
biggest among the values p p values right p of x being is the biggest among the p values.
In that case, we see that so these are all smaller values than p of x, because p of x
being the biggest and there is at least one value outside this also; so therefore, there
is a cut and all these cuts have non negative values. But can the question is so if this
is an outgoing arc, its fine, because p of x minus this thing is a non positive value
here. But but suppose there was an inward arc, so that there is an arc like going from
here to here, then what will happen? The value of the g value here will be this minus this,
but this is the higher value and this is the smaller value, so we will get a negative value
here, which is a contradiction. So therefore, they cannot be any arc which
is going inward, so all the arcs should be going outward here, and then if you take the
minimal edge cut from this edge cut, this so this is an edge cut, such that all arcs
are going outward from x. So there will be a minimal edge cut in it; that will be a directed
bond. So, what we have now proved is if the tension values are all non negative, we can
not only say that non negative, non zero g with non negative values right, then we can
indeed say that there there exist as a bond within the set of arcs, which form the support
of g the tension right.
It is now the next statement that we can make is analogous to the previous statement, so
of case this both this statement are analogous to the previous statement, so of case both
the statements are analogous to the previous one that means in the circulation, in the
case of circulation in this support, we had a cycle; I mean if the circulation had non
negative values and then we had we could say that it was a directed cycle. Here we could
say that in the tension, in the support of the tension we have a bond, and if it is the
tension was non negative, and then it was it contained contained a directed bond, it
contained a directed bond. So, this is equivalent statement.
And then now the next statement is about representing a tension as a linear combination of the tensions
associated with its bonds very similar situation. What we do is we takes suppose we are given
a tension g, so if a given a tension g, so we will do it again with induction using induction
on the cardinality or the support of the given tension. So we will consider the support of
the given tension, and we know that there is a bond in it right.
So this bond will have we can fix a sense of direction, so for instance we can set one
side and consider. And then we can as usual we can we can pick up a tension associated
with bond namely for the outgoing edge this is one, and then for this incoming edges we
have minus 1, all others are 0 0 0, and then we can see the value of g here and multiply
this particular tension with g of say, if this is a we can multiplied with g of a. So
that when I minus it from original g g minus so g of a into the tension associated with
I can say tension associated with this bond if this is b g b right, so then we will get
g dash right. Now using g can be represented as g dash plus
g a g of a into g b; now g dash is a linear combination can be represented as a by induction
hypothesis g dash can be represented as the linear combination of the tension associated
with bonds, and now this is one more such term g b in to g a therefore, g this is represented
as linear combination of the tensions associated with the bonds. See, why because we can use
induction is because by minus in this thing we have made this 0; and so that way is decrease
the cardinality of the support of g g dash the cardinality therefore, the g dash the
cardinality the support of support is strictly less than the cardinality of the support of
g. Therefore, we can apply the induction assumption.
So the similar statements called a true for other statements also like if the tension
is so what we have shown now is if any tension can be represented as a linear combination
of the tensions associated with the bonds. Now suppose the tension was non negative and
then it can be represented as a linear combination of the tensions associated with the directed
bonds, why is it possible? The same argument what we do now is because it is be its non
negative, we will have a directed bond in the support, and then we will pick up that
and then we have to as usual we have to pick up the give it a direction and give a right.
So the smallest pick up the smallest arc in it smallest valued arc in it like we did not
the case of circulation. And then based on that we have to construct g dash; g dash is
equal to g minus g of a in to g b, where g b is the the tension associated with the bond
right. So this will keep the values non negative again, so that we can apply the induction,
and then we will be able to infer that if it is non-negative, the tension is non-negative
then it can be represented as the linear combination of the tensions associated with its bonds.
More over its very easy to see that if they were all integer valued, then the coefficients
can be can can also be selected as into linear combin[ation] coefficients also can be selected
as non negative integers. So that is equivalent; so it so it is it is similar kind of proof
in fact, there is no big difference here, and these are all corresponding statements
for circulations and bonds. Now the next thing we want to do, so is to
consider a notion called a feasible circulation and feasible tension, see we have studied
two concepts now. So to summarize the material in this class so after so the main thing is
we introduce a new concept called tension, it was by looking at the circulation, because
the circulation is a vector space, because m f equal to 0 if f is a circulation, m being
a incidence matrix, and then this space is called a circulation space and its orthogonal
complement is the row space of m, m being the incidence matrix. This is called the tension
space; this is the tension space. Now then we understood how to view this tensions
has the difference of potentials, because it is a vector in the row space, any tension
is a vector in the row space, we can write it as p times m, m being the incidence matrix
and p being a vector defined on its vertices right, a function defined on the vertices
ah the. Now the the the p of x can be seen as a potential associated with the vertex
x p of x minus p of y will be the tension g associated with the arc from x to y. So
that is that is how we understand tension. And then now we show that this several theorems
that we proved for circulations as a corresponding theorem in the case of tensions also.
For example we like we proved that any circulation can be represented as the linear combination
of circulations associated with its cycles, cycles of the network; we can also show that
any tension is associated with the tensions associated linear combination can be represented
as the linear combination of the tensions associated with its bonds. And in the case
of directed sorry in the case of non negative circulations, we had we could say that it
is a linear combination tension with directed cycles, we can say in the case of tensions
that it is a linear combination of the the the the tensions associated with the directed
bonds. And if they are integer valued circulations, we could say that the coefficients of the
linear combination can be selected as integer non-negative integers, the same could be told
in the case of tension. If the tension is non-negative an integer
value, then we can take the coefficients as non negative integers. This is this is the
summary of the theme. In the next class, we will look at what of feasible flows and feasible
tensions, and we will see how a feasible flow can be achieved. Essentially it is a feasible
sorry feasible circulations and feasible tensions, its very much similar to what is the feasible
flow, we have a lower bound and upper bound for each arc the circulation value for the
tension value has to be in between the lower and the upper bounds, this is the feasibility.
So, we will in the next class, we will see what is the sufficient necessary and sufficient
criteria for having a feasible circulation an equivalent feasible tension, we will see
right. Thank you.