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

c - Unrecognised emulation mode: elf_i386 on MinGW32 -

-
i'm trying make kernel, , cannot link c output assembly. ld . i'm getting error: unrecognized emulation mode: elf_i386 i'm using windows 10 professional mingw32 , msys. code using: link.ld /* * link.ld */ output_format(elf32-i386) entry(start) sections { . = 0x100000; .text : { *(.text) } .data : { *(.data) } .bss : { *(.bss) } } kernel.c /* * kernel.c */ void kmain(void) { const char *str = "my first kernel"; char *vidptr = (char*)0xb8000; //video mem begins here. unsigned int = 0; unsigned int j = 0; /* loops clears screen * there 25 lines each of 80 columns; each element takes 2 bytes */ while(j < 80 * 25 * 2) { /* blank character */ vidptr[j] = ' '; /* attribute-byte - light grey on black screen */ vidptr[j+1] = 0x07; j = j + 2; } j = 0; /* loop writes string video memory */ while(str[j] != '\0') { /
Read more