Modelování přiřazení jako tok (vrstvená síť) [FOTO]
V [L4.1]–[L4.4] jsi síť vždycky dostal nakreslenou v zadání a počítal jsi na ní. Na zkoušce 1. 6. 2026 ale padla úloha „Residents & council“ — a v ní žádná síť není. Jen text o klubech, radě města a kvótách. Tvoje práce je síť vyrobit: zvolit vrcholy, hrany a hlavně kapacity tak, aby tok přesně odpovídal hledanému přiřazení. To je dnešní (a jediná) nová věc — a rovnou FOTO checkpoint.
Úloha, ve které žádná síť není (slide 19)
Assignment problem with an additional constraint.
Let us have $n$ residents of a town, each of them is a member of at least one club $k_1, \ldots, k_l$ and belongs to exactly one age group $p_1, \ldots, p_r$. Each club must nominate one of its members to the town's governing council so that the number of council members belonging to the age group is constrained by its minimum and maximum. One resident represents at most one club. Find a feasible assignment of the representatives or prove that it does not exist. Formulate as the Maximum Flow Problem.
Zkus sám: než začneš kreslit — co bude v téhle úloze „jednotka toku“? Co poteče sítí?
Jedna nominace (jedno křeslo v radě). Klubů je $q$, každý nominuje právě jednoho člena — sítí má tedy protéct přesně $q$ jednotek, každá po trase „klub → jeho člen → členova věková skupina“. Jakmile víš, co teče, vrstvy se nabídnou samy: zdroj, kluby, rezidenti, věkové skupiny, stok.
Tři omezení → tři kapacity
Celé kouzlo modelování je v tom, že každé slovní omezení přeložíš na kapacitu jedné hrany. Projdi si je po jednom (v jednodušší variantě z 1. 6. 2026 jsou místo věkových skupin politické strany $P_k$ a kvóta je jen horní: nejvýš $u_k$ radních ze strany $P_k$):
Zkus sám: „each club must nominate one of its members“ — jak tokem říct, že klub $C_j$ nominuje právě jednoho?
Hrana $s \to C_j$ s kapacitou $u = 1$. Tím říkáš „nejvýš jedna nominace na klub“ — a „právě jedna“ z toho uděláš až na konci požadavkem, aby všechny hrany ze zdroje byly nasycené ($f = u = 1$ na každé). Samotná síť umí vynutit jen „nejvýš“; „přesně“ je otázka na hodnotu maximálního toku.
Zkus sám: „one resident represents at most one club“ — to je omezení na vrchol $R_i$, ne na hranu. Jak ho vynutíš kapacitami hran?
Stačí si všimnout, že všechno, co do $R_i$ přiteče, musí odtéct jeho výstupními hranami (Kirchhoff [L4.1]). Rezident patří do právě jedné strany, takže z $R_i$ vede jediná hrana $R_i \to P_k$ — dáš jí kapacitu $1$ a průtok vrcholem $R_i$ je omezen jedničkou. Obecný trik: omezení „přes vrchol nejvýš $c$“ se modeluje kapacitou $c$ na hraně, kterou všechen tok vrcholem musí projít (kdyby výstupních hran bylo víc, vrchol rozdělíš na $R_i^{in} \to R_i^{out}$ a kapacitu dáš spojovací hraně).
Zkus sám: „nejvýš $u_k$ radních ze strany $P_k$“ — kam s kvótou?
Na hranu $P_k \to t$ s kapacitou $u_k$. Každá nominace člena strany $P_k$ musí do stoku projít právě touhle hranou, takže jich projde nejvýš $u_k$. (A ve variantě slidu 19 s minimem i maximem dostane táž hrana navíc dolní mez $l(e) = $ minimum — k tomu se vrátíme v úloze T01.)
Dohromady: čtyři vrstvy $s \to C_j \to R_i \to P_k \to t$. Hrany $C_j \to R_i$ existují přesně pro členství „$R_i$ je v klubu $C_j$“ (kapacita 1), hrana $R_i \to P_k$ vede do rezidentovy strany. Tady je konkrétní mini-instance, na které budeme celou lekci pracovat:
Vzor: vrstvená (třívrstvá bipartitní) síť
Stejný půdorys potkáš pořád dokola, jen se přejmenují vrstvy: $s$ → kategorie s požadavky → lidé/jednotky → kategorie s kvótami → $t$. Hrany ze zdroje říkají, kolik čeho se musí stát (jedna nominace na klub); prostřední hrany říkají, co je dovoleno (členství, kompatibilita); hrany do stoku říkají, kolik se kam vejde (kvóty $u_k$, kapacity stolů). Tímhle vzorem se modeluje i večeře rodin u stolů (úloha T02 dole), bipartitní párování ([L4.9] Bipartitní matching přes max flow) a preemptivní rozvrhování přes intervaly (slide 5–6; na to dojde v kapitole K5, lekce [L5.0] Rozvrhování přes toky).
Odpověď ANO/NE čteš z nasycení hran ze zdroje
Zkus sám: jakou největší hodnotu může mít tok v naší síti? (Vzpomeň na řezy z [L4.4].)
Řez $A = \{s\}$ má kapacitu $C(A) = \sum_j u(s \to C_j) = q$ (počet klubů; v mini-instanci $3$). Slabá dualita [L4.4] dává $|f| \le q$ pro každý tok. Maximální tok tedy buď $q$ dosáhne (všechny hrany ze zdroje nasycené), nebo zůstane pod ním.
A přesně to je kritérium, které u zkoušky musíš napsat:
Recept: přiřazení jako max flow (co odevzdat u zkoušky)- Vrcholy: $s$, vrstva požadavků (kluby), vrstva lidí (rezidenti), vrstva kvót (strany/skupiny), $t$.
- Hrany + kapacity: $s \to C_j$ s $u=1$ (každý klub jedna nominace); $C_j \to R_i$ s $u=1$ pro členy; $R_i \to P_k$ s $u=1$ do rezidentovy strany; $P_k \to t$ s $u = u_k$. Dolní meze $l \equiv 0$.
- Kritérium: přípustné přiřazení existuje $\iff$ hodnota maximálního toku $= q$, tj. maximální tok nasytí všechny hrany ze zdroje.
- Zdůvodnění čtení výsledku: kapacity jsou celočíselné → existuje celočíselný maximální tok (viz níže), hrany $C_j \to R_i$ s $f = 1$ jsou přímo nominace.
Zkus sám: v mini-instanci zmenši kvóty na $u_1 = u_2 = 1$. Existuje rada? Najdi odpověď bez spouštění algoritmu — jedním řezem.
Neexistuje. Vezmi $A = V \setminus \{t\}$: jeho kapacita je $C(A) = u_1 + u_2 = 2 < 3 = q$, takže $|f| \le 2$ pro každý tok a hrany ze zdroje nasytit nejdou — tři nominace se nevejdou do dvou stranických křesel. Tohle je přesně role minimálního řezu z [L4.4]: když odpověď zní NE, min řez je certifikát, kudy vede úzké hrdlo.
Proč si tok smíš přečíst jako přiřazení (slide 17)
Jedna věc by tě měla hryzat: tok je obecně reálné číslo. Co kdyby maximální tok poslal klubem $C_1$ půlku nominace přes $R_1$ a půlku přes $R_2$? Tady zachraňuje celočíselnost:
If the capacities of the network are integers, and there exists a feasible flow, then there exists an integer-valued maximum flow.
This follows from total unimodularity of the incidence matrix of a digraph $G$, which is matrix $\mathbf{A}$ in LP formulation $\mathbf{A} \cdot x \le b$. Alternatively we can prove it as follows: If all capacities are integers, $\gamma$ in 3) of the Ford-Fulkerson algorithm is always an integer. Since there is a maximum flow of finite value, the algorithm terminates after a finite number of steps.
Druhý argument znáš z vlastní zkušenosti: Ford-Fulkerson [L4.3] startuje z nulového toku a každá augmentace přičítá celočíselné $\gamma$ — celočíselnost se nemá kde pokazit. (První argument přes totální unimodularitu je tentýž, který jsi viděl u [L3.12] TUM.) V naší síti jsou všechny kapacity $1$ nebo $u_k$, takže existuje maximální tok s $f(e) \in \{0, 1\}$ na hranách vrstev — a hrany $C_j \to R_i$ s $f = 1$ jsou hledané nominace.
Naživo: nominace Ford-Fulkersonem
Postavená síť je obyčejná síť — žádný nový algoritmus nepotřebuješ. Proklikej si běh Ford-Fulkersona [L4.3] na mini-instanci (popisek hrany $= l, f, u$). Sleduj hlavně třetí iteraci: jde přes zpětné hrany a v řeči úlohy to znamená, že algoritmus přehodí dřívější nominaci, aby uvolnil místo v kvótě.
Nebezpečné polopravdy při modelování1) „Stačí nakreslit vrstvy a hrany.“ Nestačí — bez kapacity $1$ přes prostřední vrstvu (tady na jediné hraně $R_i \to P_k$) by jeden rezident mohl zastupovat dva kluby a model lže. Každé slovní omezení musí mít svou kapacitu; u omezení na vrchol si vždy ověř, kudy všechen tok vrcholem protéká. 2) „Síť = odpověď.“ Maximální tok existuje vždy — odpověď NE poznáš jen podle $|f| < q$. Bez věty „přiřazení existuje $\iff$ max tok nasytí hrany ze zdroje“ je formulace u zkoušky neúplná.
Key takeaways — L4.5- Vrstvený vzor: $s$ → kategorie s požadavky → lidé → kategorie s kvótami → $t$; hrany prostřední vrstvy = co je dovoleno (členství/kompatibilita).
- Kapacity kódují omezení: „právě jedna nominace na klub“ = $u(s \to C_j) = 1$ + nasycení; „jeden člověk nejvýš jednou“ = kapacita $1$ na hraně, kterou všechen tok vrcholem musí projít; kvóty = kapacity hran do $t$.
- Feasibilita: přiřazení existuje $\iff$ max tok nasytí všechny hrany ze zdroje ($|f| = q$); víc než $q$ to být nemůže (řez $A = \{s\}$, [L4.4]). Když NE, min řez je certifikát úzkého hrdla.
- Celočíselnost (Dantzig-Fulkerson, slide 17): celočíselné kapacity → existuje celočíselný max tok (F-F ho rovnou najde) → hrany s $f = 1$ čteš přímo jako přiřazení.
- U zkoušky odevzdej čtyři věci: vrcholy, hrany s kapacitami, kritérium nasycení, čtení výsledku z celočíselného toku.
FOTO checkpoint
zdroj: zkouška KO 1. 6. 2026 (doložena svědectvím, přesný přepis se nedochoval) ≈ AMO93 Application 6.2 dle ko_souhrn (EN 1:1) + varianta slide 19 (EN 1:1) ≈ test2_2015; řešení dle této lekce
A town has $r$ residents $R_1, R_2, \ldots, R_r$; $q$ clubs $C_1, C_2, \ldots, C_q$; and $p$ political parties $P_1, P_2, \ldots, P_p$. Each resident is a member of at least one club and can belong to exactly one political party. Each club must nominate one of its members to represent it on the town's governing council so that the number of council members belonging to the political party $P_k$ is at most $u_k$. Is it possible to find a council that satisfies this "balancing" property? (Formulate as a maximum flow problem; illustrate on an example with $r = 7$, $q = 4$, $p = 3$.)
b) Variant (slide 19, 1:1): …each of them is a member of at least one club $k_1, \ldots, k_l$ and belongs to exactly one age group $p_1, \ldots, p_r$. Each club must nominate one of its members to the town's governing council so that the number of council members belonging to the age group is constrained by its minimum and maximum. One resident represents at most one club. Find a feasible assignment of the representatives or prove that it does not exist. Formulate as the Maximum Flow Problem.
a) Co je v zadání?
Modelovací úloha slotu 4 z 1. 6. 2026: žádná síť, jen text. Kluby nominují po jednom členovi do rady, každý rezident má právě jednu stranu (resp. věkovou skupinu) a strany mají kvóty — v základní verzi jen horní ($\le u_k$), ve variantě b) navíc dolní (minimum). Máš formulovat max-flow problém a říct, kdy rada existuje.
b) Co k tomu budeme potřebovat?
- Tato lekce — vrstvený vzor, kapacity, kritérium nasycení, celočíselnost (takeaways).
- [L4.4] — řez jako strop ($|f| \le q$) a certifikát odpovědi NE.
- [L4.1] — síť $(G, l, u, s, t)$, role dolních mezí $l(e)$ (pro variantu b).
- [L4.3] — čím max tok spočítáš a proč vyjde celočíselný.
c) Jak nad úlohou uvažovat?
Polož si tři otázky z lekce: (i) co je jednotka toku? (nominace — sítí má protéct $q$ jednotek); (ii) které slovní omezení patří na kterou hranu? („právě jeden za klub“ → hrany ze zdroje; „rezident nejvýš jednou“ → jediná hrana z $R_i$; kvóty → hrany do stoku); (iii) jak z čísla $|f|$ přečteš odpověď ANO/NE? U varianty b) navíc: kam v síti patří minimum — a co dolní meze udělají s tvrzením „nulový tok je vždy přípustný start“?
d) Úplné řešení
Konstrukce sítě. Vrcholy: $s$, $C_1, \ldots, C_q$, $R_1, \ldots, R_r$, $P_1, \ldots, P_p$, $t$. Hrany (všude $l = 0$):
- $s \to C_j$, $u = 1$, pro každý klub — každý klub nejvýš jedna nominace;
- $C_j \to R_i$, $u = 1$, právě když $R_i$ je členem $C_j$ — nominovat lze jen vlastního člena;
- $R_i \to P_k$, $u = 1$, kde $P_k$ je (jediná) strana rezidenta $R_i$ — jediná výstupní hrana s kapacitou 1 vynucuje „one resident represents at most one club“;
- $P_k \to t$, $u = u_k$ — nejvýš $u_k$ radních ze strany $P_k$.
(Pořadí vrstev volíme $s \to C \to R \to P \to t$: rezidenti musí být uprostřed, protože jen oni mají vztah ke klubům i ke stranám. Ruční náčrt v souhrnu uvádí vrstvy v pořadí $R \to C \to P$ — tam ale členství ve straně nejde vyjádřit hranou z klubového vrcholu; zrcadlově obrácená síť $s \to P \to R \to C \to t$ by naopak fungovala taky. Volba pořadí je naše — přiznáno.)
Kritérium. Pro každý tok platí $|f| \le q$ (řez $A = \{s\}$ má kapacitu $q$, [L4.4]). Rada existuje $\iff$ hodnota maximálního toku je rovna $q$, tj. max tok nasytí všechny hrany $s \to C_j$. Kapacity jsou celočíselné, takže existuje celočíselný maximální tok (Integral Flow Theorem, slide 17) — F-F ho rovnou vydá — a nominace přečteš z hran $C_j \to R_i$ s $f = 1$: klub $C_j$ nominuje $R_i$. Kvóty jsou dodrženy, protože do $t$ ze strany $P_k$ proteče nejvýš $u_k$. Pokud max tok $< q$, rada neexistuje a minimální řez (z posledního značkování, [L4.4]) je certifikát: ukazuje skupinu klubů, jejichž členové se „mačkají“ v příliš malých kvótách. Na příkladu $r = 7$, $q = 4$, $p = 3$: tatáž síť se $4$ klubovými a $3$ stranickými vrcholy; rada existuje $\iff |f_{\max}| = 4$.
b) Varianta s minimem i maximem (slide 19). Jediná změna: hrana $P_k \to t$ dostane dolní mez $l_k$ (minimum pro skupinu $k$) a horní mez $u_k$ (maximum). Tím ale síť přestane mít $l \equiv 0$, takže nulový tok už není přípustný a samotné „pusť F-F od nuly“ nestačí: nejdřív je potřeba najít počáteční přípustný tok při nenulových dolních mezích — to je přesně rozhodovací úloha „feasible flow“, kterou řeší následující lekce [L4.6] a [L4.7] (transformace na max flow s nulovými $l$). Odpověď pak zní: přípustné přiřazení existuje $\iff$ existuje přípustný tok v této síti nasycující všechny hrany $s \to C_j$; jinak neexistuje (certifikátem je opět řez).
FOTO checkpointVyřeš úlohu NA PAPÍR bez koukání do řešení — přesně tahle formulace padla 1. 6. 2026. Nakresli síť (klidně pro malý příklad $r = 7$, $q = 4$, $p = 3$), ke každé hraně napiš kapacitu a nezapomeň na čtyři povinné věci z receptu: vrcholy, hrany+kapacity, kritérium nasycení hran ze zdroje, čtení výsledku z celočíselného toku. Přidej dvě věty k variantě b) (kam patří minimum a proč pak nejde startovat z nulového toku). Pošli mi fotku — zkontroluju ti to.
Several families go out to dinner together. There are $p$ families, the $i$-th family has $a(i)$ members; there are $q$ tables, the $i$-th table has capacity $b(i)$. To increase their social interaction, no two members of the same family may sit at the same table. Formulate the problem of finding a seating assignment as a maximum flow problem and determine when the seating is feasible.
a) Co je v zadání?
Stejný vzor jako rezidenti, jen o vrstvu kratší: rozesadit členy rodin ke stolům tak, aby u žádného stolu neseděli dva členové téže rodiny. „Jednotka toku“ = jeden usazený člověk; protéct musí $\sum_i a(i)$ jednotek.
b) Co k tomu budeme potřebovat?
- Tato lekce — kapacity kódují omezení, kritérium nasycení, celočíselnost (takeaways).
- [L4.4] — řezový strop pro rychlou kontrolu feasibility.
c) Jak nad úlohou uvažovat?
(i) Které omezení je „požadavek“ (hrany ze zdroje) a které „kvóta“ (hrany do stoku)? (ii) Jak jedinou kapacitou říct „nejvýš jeden člen rodiny $i$ u stolu $j$“ — potřebuješ na to vůbec vrchol pro každého člena? (iii) Kdy je rozesazení přípustné — co musí nasytit maximální tok?
d) Úplné řešení (vlastní — přepis obsahuje jen náčrt)
Síť (všude $l = 0$): $s \to F_i$ s kapacitou $a(i)$ (celá rodina se musí usadit); $F_i \to S_j$ s kapacitou $1$ pro každou dvojici rodina–stůl (nejvýš jeden člen rodiny $i$ u stolu $j$ — tady je celé „párty pravidlo“, žádné vrcholy pro jednotlivé členy nejsou potřeba, členové jedné rodiny jsou zaměnitelní); $S_j \to t$ s kapacitou $b(j)$ (kapacita stolu).
Kritérium. Rozesazení existuje $\iff$ maximální tok má hodnotu $\sum_i a(i)$, tj. nasytí všechny hrany $s \to F_i$. Celočíselný max tok (slide 17, kapacity celé) pak čteš po hranách: $f(F_i \to S_j) = 1$ znamená „jeden člen rodiny $i$ sedí u stolu $j$“; Kirchhoff zaručí, že rodina $i$ obsadí přesně $a(i)$ různých stolů a stůl $j$ nejvýš $b(j)$ lidí. Rychlé řezové kontroly nutnosti: $a(i) \le q$ pro každou rodinu (členové potřebují různé stoly) a $\sum_i a(i) \le \sum_j b(j)$ — když některá neplatí, příslušný řez má kapacitu $< \sum_i a(i)$ a odpověď je NE.
Poznámka: ruční náčrt v souhrnu kreslí navíc vrcholy pro jednotlivé členy s kapacitou 1; to funguje taky, ale je to zbytečně velká síť — kapacita $a(i)$ na hraně $s \to F_i$ udělá tutéž práci.