The pdf says the test is due at 5pm Friday Oct 27. I think the test is due on Monday the 27th, but I want to verify that it is not Friday the 24th. Can you clarify this?
What are we to measure in?
The number of queries?
or
the number or point-line tests?
or
what?
If it is the number of point-line tests, do we assume when the data structure is built that the recursion goes until there is only one point left (or four? or what?) ?
I suppose I don’t see how the data structure is set up (designed), nor how the query would be done, are either of these relevant to the problem?
To clarify,
we are to measure the upper bound, no?
What I’m asking for is the running time (yes, an upper bound) for a query. The data structure construction is described briefly, and so is the query. It’s your job to fill in the blanks and work out the analysis.
Now a query L can be processed as follows:
1. L intersects at most three of the four children of the root. Let these three children be
v1; v2; v3.
2. Suppose one of the vi (say v1) is completely contained on one side of L. Merely add the
count of points represented by v1 to the overall count, and discard it.
I don’t understand how L can intersect a node and have it completely contained on one side.
Say L intersects v1, v2 and v4, is it really possible to have v1 completely contained to one side?
or
is it stating, of the nodes that are not intersected, check for ‘completely contained’ …
also,
The described data structure partitions the space nicely, but it only contains information associated with the number of points within that space.
Are we to build on top of this data structure so it provides operations that can return whether L intersects it and whether it is ‘completely contained’ on one side of L?
or
are we to assume the data structure has these operations and can do them in constant time (which I can’t see how it can)?
Yes, I have office hours today. as for the questions:
each node corresponds to a region of space. That’s what L intersects.
The four pieces are defined by two lines and their intersection. Checking whether a point is on one side of a line is sufficient to determine the location of L with respect to the four regions.
So yes, you can assume a constant time operation to do this.
For problem 1.1 and 1.2, are we supposed to derive a bounding function in the explicit form of f(n)? Obviously A(n) and B(n) are non-converging series, but the problem shouldn’t be so simple, right?
I’m not sure what you mean by ‘non-converging series’. As a function of n, each of the two functions has a definite upper bound in terms of n. And the tighter the bound you give, the better.
What I mean is that A(n) and B(n) are unbounded, both go to infinity as n->infinity. But it makes sense if we are to find some approximating functions to bound the series.
In the first paragraph, you present an algorithm that has nothing to do with flows, correct?
for my own clarification, the algorithm is:
create an empty “bag” (merely a set of edges)
Pick an edge e that is
-an element of E
-and not an element of the “bag”
-and neither of the two vertices associated with e is associated with any edge in the “bag”
Add e to the “bag”
repeat until no edge e exists
This is the algorithm that you present that is claimed to produce a maximal match, correct?
last thing:
Since G is a bipartite graph, there is no edge in E that goes from a vertex in L to another vertex in L (and the same for R), right?
In the first paragraph, you present an algorithm that has nothing to do with flows, correct?
…
This is the algorithm that you present that is claimed to produce a maximal match, correct?
…
last thing:
Since G is a bipartite graph, there is no edge in E that goes from a vertex in L to another vertex in L (and the same for R), right?
on part 2,
looking at the symmetric difference of two matchings,
we are to prove that the resulting graph “consists of cycles and paths”.
I have an example of two matchings of a bipartite graph where their symmetric difference does not produce a graph with a cycle. This makes me think I’m doing something wrong,
allow me to ’show’ my example.
G = ( {(a, c)} union {(b, d)} , { (a-b) , (b-c) , (c-d) } )
M = { (b-c) }
M’ = { (a-b) , (c-d) }
The symmetric difference of M and M’ is = { (b-c) , (a-b), (c-d) }
There is no cycle!!!
Actually the defined graph can never have a cycle.
If we are to prove the resulting graph from the symmetric difference consists of cycles, then I’m doing something wrong, are you able (willing) to tell me what?
Hmm. I asked to show that the resulting graph is a collection of cycles and paths. In other words, no *other* kind of graph structure appears. take a closer look at what you wrote down.
am not sure what that means: if you mean, dividing a set of points into the regions, then no: it takes linear time to do that. If you mean computing a description of the region, then yes, that can be done in constant time (find the point of intersection, and then each region is described by two halflines emanating from that point)
I think I was asking about the first case you mentioned.
So it takes O(n) times to divide a set of n points into four subregions.
And it takes constant time to judge which of the four regions are intersected by the line, and which are entirely contained on one side. Is that correct?
But if the first statement is true, the first divide step will take O(n) time. In contrast, the brute force way is also in linear time O(n). The divide-conquer procedure should get sublinear time. Is there any inconsistencies?
I think you’re confusing the procedure that builds the tree (and needs to examine the points) with the query procedure (that does the line intersection checking). I’m asking about the analysis of the latter.
For 5.2 where we prove that the graph has only cycles and paths, what kind of paths are we talking about? Any path from one node to another, or a path that starts at a vertice in L and ends at a vertice in R?
The instructions say “You MAY NOT use answers found on the web.”
Listening to you talk in class on Wednesday, it sounds like you are telling us not to find solutions to these specific problems on the web, whereas using, say, the links you have on the course webpage (the CS theory cheat sheet, etc.) as well as, say, other textbooks that we have is fine, right?
Wikipedia?
Can you clarify the definition of a bottleneck edge? Problem 4c defines it as an edge where if the capacity were increased, the max flow of the network would increase. Does this mean “If the edge capacity were to be increased in isolation (changing no other edges)” exclusively?
Would you please explain more fully this undefined “maximal bag” algorithm you refer to in part one of question 5? I saw a clarification above, but that does not quite make sense to me either, though it’s better. When you say “we just throw edges into our matching bag”, I’m picturing lines randomly being attached to dots with no mention of how many lines (edges) there are compared to the dots (vertices). I realize that one end of an edge must be in L and the other in R, since it is a bipartite graph. But I don’t understand what you mean by being “stuck.” It sounds like we “aren’t stuck” as long as there are vertices between the two groups that have not been connected. Is that what you are saying? So we are at “maximal” when have connected all the vertices between the two groups with edges in some random fashion?
I think the random “maximal bag” is similar to what you said. Someone correct me if I am wrong, but basically you randomly throw edges into the bag until there are no more edges that if added would result in a greater matching. Not all the vertices will be connected and this matching is not necessarily a maximum matching.
For example, if we had V={a,b,c,d} and E={{a,b},{c,b},{c,d}}. A valid result of this algorithm would be to grab the edge {c,b}. At which point you can’t add any more edges since all other edges would make an invalid matching. Clearly this isn’t a maximum matching, but it is maximal in that we can’t do any further without taking something out of the bag.
I believe that in the case of a network with no bottlenecks our algorithm should return an empty set of edges. If there are bottlenecks, the algorithm should return a set of all the bottleneck edges.
Returning an empty set in that case makes sense, but how to determine that there are no bottleneck edges by using the residual graph after a max flow (as the problem suggests) is not clear. I don’t want to say too much about this particular case because that would be the answer to 4d, but this one has me confused…
Regarding bottleneck edges, Mike answered correctly: if there are no bottleneck edges, you report that fact. More I can’t say without revealing crucial information :). It might help if you can clarify what you’re confused about in 4e.
Regarding maximal matchings, again Mike’s clarification is correct. I would hesitate to use the term “random”: I prefer “arbitrary”, because in later lectures the term “random” will have a definite meaning :), but the intent is correct.
Given a graph G = V, E, and a subset of edges E’, the graph induced by E’ is what we get if we delete all edges that are in E - E’, and then remove all vertices that are now isolated.
The delta operator is defined in 5.1 It operates on 2 sets of edges and produces another set of edges. Take the set of edges produced by doing M delta M’ and make a graph out of those edges. That graph is the one you are proving things about.
For example, let M={{b,c}} and M’={{a,b},{c,d}} be subsets of the edges in the graph G=(V,E). M delta M’ gives us {{b,c},{a,b},{c,d}} (well call this resulting set E’). We then create a graph G’ = (V,E’) and prove stuff about that new graph. Hopefully I’m not causing more confusion
I guess I was a little slow and a little wrong on that last one (2 for 3 though, not too bad). So the V in the new graph G’ should have isolated vertices removed.
One thing I am not sure on the 5 more matchings problem. In the 5.2 proving cycles and paths question, this will not be true when |M| and |M’| are both optimal, right? Coz, I can give a conflict example when M and M’ are {a, b, c, d, e, f, {ae}, {cf}} and {a,b,c, {ad},{bf}} (a, b,c on one side, the rest are on the other side), in this example the graph of M\delta M’ contains no cycles and paths. Please tell me where did I go wrong, if it is not right.
T(n) = T(4n/5) + C
M(n) = 4M(n/5) + C
P(n) = P(2n/5) + P(2n/5) + C
S(n) = 2S(n/5) + S(2n/5) + C
-the same under certain situations (depending on T(n)’s base case I guess),
-always the same,
-never the same,
-or nothing may be said about them together.
Need a little clarification for question 5.2 .. which one of the two following statements does it say ?
— there exists an augmenting path which has the given property (k+1 edges from current Matching and k from the rest) and pick this augmenting path for extending the current matching.
— every augmenting path has this property, so pick any one of them to extend the current matching.
I guess its the first one, but I want to make sure I am on the right track.
Yes I realized that I flipped the property. Thanks … but that leads me to another question.
If the graph is G=({a,b,c}U{d,e,f}, {ad, ae, af, be, bf, cf}) and let the current maximal matching be M = {ae, bf}. Now the augmenting path c-f-a-d doesn’t seem to be following this property. Am I missing something very obvious ?
um no. It’s the process of creating flow that defines the directions, remember. If you have a flow path that traverses ae, and another that traverses bf, then in the residual graph, what does the edge af look like ? Remember that all edges start with zero backwards capacity
Entries
October 20th, 2008 at 6:15 pm
The pdf says the test is due at 5pm Friday Oct 27. I think the test is due on Monday the 27th, but I want to verify that it is not Friday the 24th. Can you clarify this?
October 20th, 2008 at 7:48 pm
Apologies: it’s indeed Monday. I’ll fix it.
October 20th, 2008 at 9:23 pm
On problem 2 Range Searching:
You ask: How long does this procedure take ?
What are we to measure in?
The number of queries?
or
the number or point-line tests?
or
what?
If it is the number of point-line tests, do we assume when the data structure is built that the recursion goes until there is only one point left (or four? or what?) ?
I suppose I don’t see how the data structure is set up (designed), nor how the query would be done, are either of these relevant to the problem?
To clarify,
we are to measure the upper bound, no?
thank you
October 20th, 2008 at 11:35 pm
What I’m asking for is the running time (yes, an upper bound) for a query. The data structure construction is described briefly, and so is the query. It’s your job to fill in the blanks and work out the analysis.
October 21st, 2008 at 10:43 am
Will you be holding your normal office hours today?
October 21st, 2008 at 10:56 am
On problem 2 Range Searching:
it states:
Now a query L can be processed as follows:
1. L intersects at most three of the four children of the root. Let these three children be
v1; v2; v3.
2. Suppose one of the vi (say v1) is completely contained on one side of L. Merely add the
count of points represented by v1 to the overall count, and discard it.
I don’t understand how L can intersect a node and have it completely contained on one side.
Say L intersects v1, v2 and v4, is it really possible to have v1 completely contained to one side?
or
is it stating, of the nodes that are not intersected, check for ‘completely contained’ …
also,
The described data structure partitions the space nicely, but it only contains information associated with the number of points within that space.
Are we to build on top of this data structure so it provides operations that can return whether L intersects it and whether it is ‘completely contained’ on one side of L?
or
are we to assume the data structure has these operations and can do them in constant time (which I can’t see how it can)?
thanks
October 21st, 2008 at 11:21 am
again on problem 2 Range Searching:
to clarify,
for a query L it only recurses on intersected nodes, no?
October 21st, 2008 at 12:31 pm
Yes, I have office hours today. as for the questions:
each node corresponds to a region of space. That’s what L intersects.
The four pieces are defined by two lines and their intersection. Checking whether a point is on one side of a line is sufficient to determine the location of L with respect to the four regions.
So yes, you can assume a constant time operation to do this.
October 21st, 2008 at 6:20 pm
For recurrence 1.4, we are given H(1) = c, but it seems to me like we would also need H(2). Is that right?
October 21st, 2008 at 7:08 pm
That’s correct. assume whatever you need. The ideal case is to assume things to be arbitrary constants (rather than specific ones like 1 or 0)
October 21st, 2008 at 8:40 pm
For problem 1.1 and 1.2, are we supposed to derive a bounding function in the explicit form of f(n)? Obviously A(n) and B(n) are non-converging series, but the problem shouldn’t be so simple, right?
October 21st, 2008 at 8:46 pm
I’m not sure what you mean by ‘non-converging series’. As a function of n, each of the two functions has a definite upper bound in terms of n. And the tighter the bound you give, the better.
October 21st, 2008 at 9:10 pm
What I mean is that A(n) and B(n) are unbounded, both go to infinity as n->infinity. But it makes sense if we are to find some approximating functions to bound the series.
October 21st, 2008 at 9:51 pm
What I mean is that A(n) and B(n) are unbounded, both go to infinity as n->infinity.
But how is that different to any recurrence we’ve analyzed in class: After all, the recurrence
T(n) = 2T(n/2) + n
yields T(n) = Theta(n log n) which goes to infinity as n goes to infinity.
October 22nd, 2008 at 2:43 pm
For the constraint in question 3, shouldn’t the less-than-or-equal-to be an equal-to?
October 22nd, 2008 at 4:22 pm
No, this is correct. You are not adding extra spaces, so you may not be able to fit L exactly (there might be slack)
October 23rd, 2008 at 2:50 pm
On problem 5 More Matchings:
In the first paragraph, you present an algorithm that has nothing to do with flows, correct?
for my own clarification, the algorithm is:
create an empty “bag” (merely a set of edges)
Pick an edge e that is
-an element of E
-and not an element of the “bag”
-and neither of the two vertices associated with e is associated with any edge in the “bag”
Add e to the “bag”
repeat until no edge e exists
This is the algorithm that you present that is claimed to produce a maximal match, correct?
last thing:
Since G is a bipartite graph, there is no edge in E that goes from a vertex in L to another vertex in L (and the same for R), right?
thank you
October 23rd, 2008 at 2:56 pm
In the first paragraph, you present an algorithm that has nothing to do with flows, correct?
…
This is the algorithm that you present that is claimed to produce a maximal match, correct?
…
last thing:
Since G is a bipartite graph, there is no edge in E that goes from a vertex in L to another vertex in L (and the same for R), right?
Yes, on all three questions.
October 23rd, 2008 at 4:25 pm
in that case (same problem, 5 more matching)
on part 2,
looking at the symmetric difference of two matchings,
we are to prove that the resulting graph “consists of cycles and paths”.
I have an example of two matchings of a bipartite graph where their symmetric difference does not produce a graph with a cycle. This makes me think I’m doing something wrong,
allow me to ’show’ my example.
G = ( {(a, c)} union {(b, d)} , { (a-b) , (b-c) , (c-d) } )
M = { (b-c) }
M’ = { (a-b) , (c-d) }
The symmetric difference of M and M’ is = { (b-c) , (a-b), (c-d) }
There is no cycle!!!
Actually the defined graph can never have a cycle.
If we are to prove the resulting graph from the symmetric difference consists of cycles, then I’m doing something wrong, are you able (willing) to tell me what?
thank you
October 23rd, 2008 at 4:50 pm
(associated with previous post)
sorry, this was implied, but I’ll state it explicitly:
M’ is formed from P = { (a,b) , (b,c) , (c,d) }
October 23rd, 2008 at 7:57 pm
Hmm. I asked to show that the resulting graph is a collection of cycles and paths. In other words, no *other* kind of graph structure appears. take a closer look at what you wrote down.
October 23rd, 2008 at 10:30 pm
For problem 2, can we assume that it takes constant time to divide a region equally by four with two intersection lines?
October 23rd, 2008 at 10:32 pm
am not sure what that means: if you mean, dividing a set of points into the regions, then no: it takes linear time to do that. If you mean computing a description of the region, then yes, that can be done in constant time (find the point of intersection, and then each region is described by two halflines emanating from that point)
October 23rd, 2008 at 10:45 pm
I think I was asking about the first case you mentioned.
So it takes O(n) times to divide a set of n points into four subregions.
And it takes constant time to judge which of the four regions are intersected by the line, and which are entirely contained on one side. Is that correct?
October 23rd, 2008 at 10:47 pm
Correct on both statements.
October 23rd, 2008 at 10:53 pm
But if the first statement is true, the first divide step will take O(n) time. In contrast, the brute force way is also in linear time O(n). The divide-conquer procedure should get sublinear time. Is there any inconsistencies?
October 23rd, 2008 at 10:55 pm
I think you’re confusing the procedure that builds the tree (and needs to examine the points) with the query procedure (that does the line intersection checking). I’m asking about the analysis of the latter.
October 24th, 2008 at 11:50 am
For 5.2 where we prove that the graph has only cycles and paths, what kind of paths are we talking about? Any path from one node to another, or a path that starts at a vertice in L and ends at a vertice in R?
October 24th, 2008 at 11:52 am
Well since the graph is undirected and bipartite, *any* path has to be a path that starts in L and ends in R
October 24th, 2008 at 2:32 pm
You said in regards to the more matching problem 5:
Hmm. I asked to show that the resulting graph is a collection of cycles and paths. …
should this be, cycles OR paths?
thanks
October 24th, 2008 at 2:47 pm
Sure, if you want to think of it that way. More precisely, each component of the graph is a member of the set CYCLES U PATHS
October 24th, 2008 at 2:54 pm
The instructions say “You MAY NOT use answers found on the web.”
Listening to you talk in class on Wednesday, it sounds like you are telling us not to find solutions to these specific problems on the web, whereas using, say, the links you have on the course webpage (the CS theory cheat sheet, etc.) as well as, say, other textbooks that we have is fine, right?
Wikipedia?
October 24th, 2008 at 2:57 pm
correct. Wikipedia, no. any definitions you need should be available in the textbooks.
October 25th, 2008 at 4:08 pm
Can you clarify the definition of a bottleneck edge? Problem 4c defines it as an edge where if the capacity were increased, the max flow of the network would increase. Does this mean “If the edge capacity were to be increased in isolation (changing no other edges)” exclusively?
October 25th, 2008 at 4:14 pm
That is correct.
October 25th, 2008 at 4:20 pm
If that is the case, then what should our algorithm for 4e return in the case of a graph like 4d?
October 25th, 2008 at 5:38 pm
Would you please explain more fully this undefined “maximal bag” algorithm you refer to in part one of question 5? I saw a clarification above, but that does not quite make sense to me either, though it’s better. When you say “we just throw edges into our matching bag”, I’m picturing lines randomly being attached to dots with no mention of how many lines (edges) there are compared to the dots (vertices). I realize that one end of an edge must be in L and the other in R, since it is a bipartite graph. But I don’t understand what you mean by being “stuck.” It sounds like we “aren’t stuck” as long as there are vertices between the two groups that have not been connected. Is that what you are saying? So we are at “maximal” when have connected all the vertices between the two groups with edges in some random fashion?
October 25th, 2008 at 7:15 pm
I think the random “maximal bag” is similar to what you said. Someone correct me if I am wrong, but basically you randomly throw edges into the bag until there are no more edges that if added would result in a greater matching. Not all the vertices will be connected and this matching is not necessarily a maximum matching.
For example, if we had V={a,b,c,d} and E={{a,b},{c,b},{c,d}}. A valid result of this algorithm would be to grab the edge {c,b}. At which point you can’t add any more edges since all other edges would make an invalid matching. Clearly this isn’t a maximum matching, but it is maximal in that we can’t do any further without taking something out of the bag.
October 25th, 2008 at 7:22 pm
@John M
I believe that in the case of a network with no bottlenecks our algorithm should return an empty set of edges. If there are bottlenecks, the algorithm should return a set of all the bottleneck edges.
October 25th, 2008 at 7:30 pm
Returning an empty set in that case makes sense, but how to determine that there are no bottleneck edges by using the residual graph after a max flow (as the problem suggests) is not clear. I don’t want to say too much about this particular case because that would be the answer to 4d, but this one has me confused…
October 25th, 2008 at 8:05 pm
Terminology issue: Can anyone explain what is meant in problem 5-2 by, “the graph induced by the edges of M^M’ “?
October 25th, 2008 at 8:13 pm
Regarding bottleneck edges, Mike answered correctly: if there are no bottleneck edges, you report that fact. More I can’t say without revealing crucial information :). It might help if you can clarify what you’re confused about in 4e.
Regarding maximal matchings, again Mike’s clarification is correct. I would hesitate to use the term “random”: I prefer “arbitrary”, because in later lectures the term “random” will have a definite meaning :), but the intent is correct.
Given a graph G = V, E, and a subset of edges E’, the graph induced by E’ is what we get if we delete all edges that are in E - E’, and then remove all vertices that are now isolated.
October 25th, 2008 at 8:14 pm
The delta operator is defined in 5.1 It operates on 2 sets of edges and produces another set of edges. Take the set of edges produced by doing M delta M’ and make a graph out of those edges. That graph is the one you are proving things about.
For example, let M={{b,c}} and M’={{a,b},{c,d}} be subsets of the edges in the graph G=(V,E). M delta M’ gives us {{b,c},{a,b},{c,d}} (well call this resulting set E’). We then create a graph G’ = (V,E’) and prove stuff about that new graph. Hopefully I’m not causing more confusion
October 25th, 2008 at 8:16 pm
I guess I was a little slow and a little wrong on that last one (2 for 3 though, not too bad). So the V in the new graph G’ should have isolated vertices removed.
October 25th, 2008 at 8:22 pm
well actually removing isolated vertices is not essential. in any case these vertices don’t participate in the action, so to speak
October 25th, 2008 at 11:21 pm
One thing I am not sure on the 5 more matchings problem. In the 5.2 proving cycles and paths question, this will not be true when |M| and |M’| are both optimal, right? Coz, I can give a conflict example when M and M’ are {a, b, c, d, e, f, {ae}, {cf}} and {a,b,c, {ad},{bf}} (a, b,c on one side, the rest are on the other side), in this example the graph of M\delta M’ contains no cycles and paths. Please tell me where did I go wrong, if it is not right.
October 25th, 2008 at 11:29 pm
an empty graph is indeed one that contains only cycles and paths. A cycle of length zero and a path of length zero.
October 26th, 2008 at 1:57 pm
Are all of these:
T(n) = T(4n/5) + C
M(n) = 4M(n/5) + C
P(n) = P(2n/5) + P(2n/5) + C
S(n) = 2S(n/5) + S(2n/5) + C
-the same under certain situations (depending on T(n)’s base case I guess),
-always the same,
-never the same,
-or nothing may be said about them together.
dumb question, I know, sorry
October 26th, 2008 at 2:27 pm
They are different, and yes, it does depend on the base case, and C
October 26th, 2008 at 4:02 pm
Need a little clarification for question 5.2 .. which one of the two following statements does it say ?
— there exists an augmenting path which has the given property (k+1 edges from current Matching and k from the rest) and pick this augmenting path for extending the current matching.
— every augmenting path has this property, so pick any one of them to extend the current matching.
I guess its the first one, but I want to make sure I am on the right track.
October 26th, 2008 at 4:05 pm
the second. *every* augmenting path has this property (and it should be flipped: k from the current, and k+1 that are not)
October 26th, 2008 at 4:16 pm
Yes I realized that I flipped the property. Thanks … but that leads me to another question.
If the graph is G=({a,b,c}U{d,e,f}, {ad, ae, af, be, bf, cf}) and let the current maximal matching be M = {ae, bf}. Now the augmenting path c-f-a-d doesn’t seem to be following this property. Am I missing something very obvious ?
October 26th, 2008 at 4:18 pm
The path c-f-a-d is not augmenting. Draw the residual graph resulting from the flow through ae and bf, and you’ll see what i mean
October 26th, 2008 at 4:29 pm
So, all the edges in the original graph have direction from L -> R ?? Otherwise the directional edge from f->a will make this path an augmenting path.
October 26th, 2008 at 4:32 pm
um no. It’s the process of creating flow that defines the directions, remember. If you have a flow path that traverses ae, and another that traverses bf, then in the residual graph, what does the edge af look like ? Remember that all edges start with zero backwards capacity
October 26th, 2008 at 9:17 pm
Does something like T(n)=n^0.5 a polynomial time or a sublinear time? Thx.
October 26th, 2008 at 11:52 pm
Any time of the form n^c, c > 0 is polynomial. A running time that is o(n) (not O(n)), is sublinear.
October 27th, 2008 at 8:52 am
In question 5.2: …each vertex has degree at most two. Does that include s and t, or are we ignoring them for that part of the question?
October 27th, 2008 at 10:20 am
we ignore s and t for this part. this is a structural fact related to matchings, and thus does not concern itself with the source and sink vertices
October 27th, 2008 at 1:56 pm
> Well since the graph is undirected and bipartite, *any* path has to be a path that starts in L and ends in R
Why can’t an undirected and bipartite graph have a path that starts in R and ends in L?
October 27th, 2008 at 1:58 pm
Well two answers;
* if the graph is undirected, what’s the difference
* if we are thinking about augmenting paths, how can they start in R ?
October 27th, 2008 at 5:49 pm
now that the test is done,
when will you be able to stop this torture
When will the answers be available?
thanks,
JOsh
October 27th, 2008 at 7:41 pm
I’ll try to hand them out wednesday. no promises though