9 views

Skip to first unread message

Dec 3, 2012, 5:09:40 PM12/3/12

to cs561-f12

A hint on problem 3 of the hw.

Note that for all the network flow algorithms we discussed in class (Fat-Pipe, Short-Pipe, Ford-Fulkerson), the following is true:

- If the capacities of all edges are integers, then all flow values returned in the max flow are integers.

This is true since each augmenting path will increase flow by an integral value. This is sometimes called the Integrality Invariant.

Jared

Dec 3, 2012, 5:50:41 PM12/3/12

to cs56...@googlegroups.com

Professor Saia,

Are we required to use the hint in problem 3? I think I found a way to prove it without relying on the Max flow/Min Cut Theorem.

Thanks!

Stephen

Jared--

Dec 3, 2012, 6:37:16 PM12/3/12

to cs561-f12

Stephen,

I'd prefer if you solve this problem using the Max flow/Min Cut theorem. Among other things, if you do it that way, it'll help you on a related problem that may appear on the final.

Jared

p.s. There are certainly other ways to show this result, but I don't think any of them are any easier then using the Max flow/Min Cut theorem.

--

Dec 4, 2012, 11:41:10 AM12/4/12

to cs561-f12

Stephen,

There's a problem in the following:

"(if a then b) is logically equivalent to (if not b then not a)"

- Ok so far

"Thus, it is sufficient (equivalent) to prove that If |N(S)| < |S| then there is not perfect matching in G."

- This is a mistake. You've mismatched the statements a and b. a is the statement "For all S, |N(S)| >= |S|". b is the statement "There is a perfect matching"

Thus, "if not b, then not a" is equivalent to

"If there is no perfect matching, then there is some subset S such that |N(S)| < |S|"

This is a much harder statement to prove. Again the Max-flow/Min-cut Theorem leads to the simplest proof I know for this problem.

Hope this helps!

Jared

--

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu