algorithm - 3 max flow prove or disprove small questions -

-

the questions :

enter image description here

for (a) seems not true, can fin example of flow growing without e being saturated.

for (b) seems true, yet not sure how prove it. maybe because of min cut max flow theorm, on min cut had grew.

for (c) seems false. flow grew because e changed e might have not grew 5.

(1) seems true me - if managed increase maximum flow, means found new path source sink (that did not exist before increasing edge e). e must in new path, if e not saturated before, path have existed in original graph.

(2) false. take graph this:

s --20-- n --20-- t

where s source , t sink, there 2 min-cuts ({(s, n)} , {(n, t)}), increasing either (s, n) or (n, t) won't change maximum flow.

(3) false. take graph this:

s --20-- n --25-- t

if increase capacit of e = (s, n) 10, new maximum flow 25, did not increase value of e 5.


Comments

Post a Comment

Popular posts from this blog

ruby - Trying to change last to "x"s to 23 -

-
i have been playing around irb , have string looks this: irb(main):072:0> puts ["[\"4354 5432 5432 xxxxx\", \"6547 6547 8543 xxxxx\", \"2344 6543 6674 xxxxx\", \"2346 6236 7543 xxxxx\", \"1273 5585 5587 xxxxx\"]"] => nil irb(main):073:0> what want gsub last 2 "x" s of each 17 digit combination, 23 . what i've tried far (i've been using rubular): a.gsub(/\d[x]/,"23") <= grabs "x" s i'm close a.gsub(/\w[x{2}]/,"23") <= grabs "x" s grabs two digits each combination. is there easier way i'm not understanding? a.gsub(/\d{4} \d{4} \d{4} xxx\kxx/, '23') \d{4} = 4 digits what \k drop matched far. can use don't replace entire number, still able validate have in desired format.
Read more

jquery - Clone last and append item to closest class -

-
this bare-bones code on page: <div class="list-container"> <div class="single-list-item"> <button>remove</button> </div> <div class="single-list-item"> <button>remove</button> </div> <div class="single-list-item"> <button>remove</button> </div> </div> <p><button class="add-list-item">add</button></p> <div class="list-container"> <div class="single-list-item"> <button>remove</button> </div> <div class="single-list-item"> <button>remove</button> </div> <div class="single-list-item"> <button>remove</button> </div> </div> <p><button class="add-list-item">add</button></p> <di...
Read more

css - Can I use the :after pseudo-element on an input field? -

-
i trying use :after css pseudo-element on input field, not work. if use span , works ok. <style type="text/css"> .mystyle:after {content:url(smiley.gif);} .mystyle {color:red;} </style> this works (puts smiley after "buu!" , before "some more") <span class="mystyle">buuu!</span>a more this not work - colors somevalue in red, there no smiley. <input class="mystyle" type="text" value="somevalue"> what doing wrong? should use pseudo-selector? note: cannot add span around input , because being generated third-party control. :after , :before not supported in internet explorer 7 , under, on elements. it's not meant used on replaced elements such form elements (inputs) , image elements . in other words it's impossible pure css. however if using jquery can use $(".mystyle").after("add smiley here"); api docs on .after to ...
Read more