Matematické Fórum

kamdem · 05. 01. 2016 22:11

Zdravím, potřebuji poradit s jendím příkladem.

Nalezněte a zapište největší tok ze zdroje z do stoku s v sítí.

//forum.matweb.cz/upload3/img/2016-01/27633_20160105_214404_Burst01.jpg

Vyšlo mi že nějvětší tok $||f||=8$ ale nevím jak mám udělat řez abych si to ověřil.

Tady je postup:

Podle definice ze skript:

Sestavíme množinu $U$ , zařadíme do ní všechny vrcholy, které jsou dosažitelné ze zdroje po nenasycených
cestách. Odcházející hrany tvoří řez

Takže v množině U budou vrcholy $U = \{z, v_{2},v_{5}.v_{4}\}$ ?

A které teďka mám vzít ty odcházející hrany?

petrkovar · 06. 01. 2016 02:37

Ty, které mají počáteční vrchol v U a koncový mimo U: $v_3v_6, v_5s, v_4s$ . pro kontrolu vidíme, že hrana "přicházející do U" $v_6v_5$ od stoku má nulový tok.

kamdem · 06. 01. 2016 13:14 — Editoval kamdem (06. 01. 2016 13:15)

↑ petrkovar:

Děkuji za odpověď. Chtěl bych se ještě zeptat na jednu nejasnost.

//forum.matweb.cz/upload3/img/2016-01/82188_20160105_215611_1.jpg

Pokusil jsem se vyznačit na obrázku množinu U a hrany které budou řez. Doufám že jsem to vyznačil správně.

Když jste psal že vezmu hrany, které mají počáteční vrchol v U a koncový mimo U, tak mi není jasné proč tam bude patřit i hrana $v_{3}v_{6}$ když má počátční i koncový vrchol mimo U? Proč tam nebude patřit hrana $z,v_{3}$ ?

petrkovar · 07. 01. 2016 12:07

Máte pravdu, měla tam být hrana $z,v_{3}$ a ne $v_{3}v_{6}$ . Špatně jsem přečetl množinu U.
Teď se dívám ,že do U patří i vrchol i $v_1$ , neboť z vrcholu $v_4$ tam vede nenasycená cesta.

kamdem · 07. 01. 2016 13:51

↑ petrkovar:

Dobře, ještě pro koreknost doplním obrázek správně.

//forum.matweb.cz/upload3/img/2016-01/70837_20160105_215611_1.jpg

Teď se dívám ,že do U patří i vrchol i $v_1$ , neboť z vrcholu $v_4$ tam vede nenasycená cesta.

Nějak mi není jasné proč tam bude patřit i $v_{1}$ . Když cesta z $v_4$ do $v_1$ je naopak orientovaná a podle mého obrázku je nasycená 2/2. ? Mohl byste mi prosím ještě toto vysvětlil?

petrkovar · 09. 01. 2016 04:53

Podle definice nenasycené cesty je právě proto hrana, která vede opačně a má nenulový tok nenasycená. Tok do v_1 je možno zvýšit o 2 jednotky, které nyní odtékají.

Matematické Fórum

#1 05. 01. 2016 22:11

Toky v sítích

#2 06. 01. 2016 02:37

Re: Toky v sítích

#3 06. 01. 2016 13:14 — Editoval kamdem (06. 01. 2016 13:15)

Re: Toky v sítích

#4 07. 01. 2016 12:07

Re: Toky v sítích

#5 07. 01. 2016 13:51

Re: Toky v sítích

#6 09. 01. 2016 04:53

Re: Toky v sítích

Zápatí