$\begingroup$
$\endgroup$
2
Let $N = (V, E)$ be a network in which the capacity of each edge is either 12ドル$ or 18ドル$.
Prove or disprove: The value of a maximum flow for $N$ can’t be 56ドル$.
I'm trying to figure out how to definitely prove this. I think that this is not possible because of no combination of 12ドルX + 18Y$ (where $X$ and $Y$ are integers) will ever $= 56$. Is there a better way of saying this? Am I right to say that an integer solution to 12ドルX + 18Y = 56$ is what the Fold-Fulkerson algorithm implies?
-
$\begingroup$ Hint: can the minimum cut have a total capacity of 56? en.wikipedia.org/wiki/Max-flow_min-cut_theorem $\endgroup$Angela Pretorius– Angela Pretorius2019年06月18日 19:39:51 +00:00Commented Jun 18, 2019 at 19:39
-
$\begingroup$ It looks like you have got the major ideas. I would encourage you to write an answer yourself. $\endgroup$喜欢算法和数学– 喜欢算法和数学2019年06月18日 19:45:12 +00:00Commented Jun 18, 2019 at 19:45
1 Answer 1
$\begingroup$
$\endgroup$
By the max flow min cut theorem, the maximum value of a flow equals the minimum capacity of a cut. The capacity of a cut is of the form 12x+18y, which can’t equal 56 because 56 is not a multiple of 6.