Párování a perfektní párování
Prerekvizity: [L0.1] Co je graf. V této lekci jde jen o pojem — algoritmy na výpočet přijdou až v kapitole K4 (toky).
Definice
Ze slidů (04_Flows, slide 38): „Matching is the set of arcs $P \subseteq E(G)$ in undirected graph $G$, such that the endpoints are all different (no arcs from $P$ are incident with the same node).“ Česky: párování je podmnožina hran, ve které se žádné dvě hrany nedotýkají stejného vrcholu — každý vrchol je „spárovaný“ nejvýš jednou.
Zkus sám: kolik vrcholů pokrývá párování o $k$ hranách? Kolik hran může mít párování v grafu s $n$ vrcholy nejvýš?
Každá hrana párování pokrývá 2 vrcholy a žádný vrchol se neopakuje — párování o $k$ hranách pokrývá přesně $2k$ vrcholů. Proto párování nemůže mít víc než $\lfloor n/2 \rfloor$ hran.
Perfektní párování
Slide 38 pokračuje: „When all nodes of $G$ are incident with some arc in $P$, we call $P$ a perfect matching.“ Perfektní párování tedy pokrývá každý vrchol právě jednou hranou — nikdo nezbyl.
Zkus sám: může mít perfektní párování graf s lichým počtem vrcholů? A stačí sudý počet vrcholů k tomu, aby perfektní párování existovalo?
Lichý počet vrcholů: ne — perfektní párování pokrývá $2k$ vrcholů, takže $n$ musí být sudé. Sudý počet ale nestačí: třeba hvězda se 4 vrcholy (střed + 3 listy) má sudý počet vrcholů, ale jakákoli hrana pokryje střed a jeden list — dva zbylé listy už spárovat nejde (nevede mezi nimi hrana). Existence perfektního párování závisí na struktuře grafu, ne jen na počtu vrcholů.
Čtyři problémy nad párováním (zatím jen názvy)
Slide 38 vyjmenovává čtyři úlohy — teď je ber jako slovníček, počítat je budeme později:
- a) Maximum Cardinality Matching — párování s největším počtem hran (v obecném grafu).
- b) Maximum Cardinality Matching in Bipartite Graphs — totéž v bipartitním grafu (vrcholy ve dvou skupinách, hrany jen mezi skupinami); speciální případ a). Spočteme přes max-flow v [L4.9] Bipartitní matching přes max flow.
- c) Minimum Weight Matching — nejlevnější z párování maximální kardinality ve váženém grafu.
- d) Minimum Weight Perfect Matching v úplném bipartitním grafu se stejně velkými stranami — tzv. Assignment Problem (přiřazovací problém); speciální případ c) a zároveň speciální případ min-cost flow. Spočteme v [L4.12].
Důležité (a u zkoušky uklidňující): „These problems can be solved in polynomial time.“ Párování jsou — na rozdíl od ILP — efektivně řešitelná. Pro důkazy (např. Christofides v K3) navíc stačí existence a vlastnosti min-weight perfect matchingu; výpočet znát nemusíš.
Zkus sám: v bipartitním grafu nahoře je zeleně párování o 2 hranách. Je největší možné (jde rozšířit na 3)?
Zelené párování $\{x_2y_1, x_3y_2\}$ rozšířit přímo nejde — nepokryté zůstaly jen $x_1$ a $y_3$ a každá jejich hrana ($x_1y_1$, $x_3y_3$) se dotýká už pokrytého vrcholu. Ale největší to není: párování $\{x_1y_1, x_2y_2, x_3y_3\}$ má 3 hrany a je dokonce perfektní. Pozor tedy na rozdíl „nejde přidat hranu“ vs. „největší možné“ — k vylepšení je někdy potřeba hrany přepárovat (to dělá tzv. augmenting path, potkáš ji v K4).
Key takeaways — L0.6- Párování (matching) $M \subseteq E(G)$: žádné dvě hrany nesdílí vrchol; $k$ hran pokrývá přesně $2k$ vrcholů.
- Perfektní párování: každý vrchol pokrytý právě jednou hranou — vyžaduje sudé $n$, ale sudé $n$ samo nestačí.
- Min-weight perfect matching v úplném bipartitním grafu = assignment problem; tady jen pojem — výpočet přes toky až v [L4.9] (cardinality) / [L4.12] (min-weight perfect).
- Úlohy o párování jsou řešitelné polynomiálně; pro důkazy (Christofides) stačí existence a vlastnosti matchingu.
“Matching is the set of arcs $P \subseteq E(G)$ in undirected graph $G$, such that the endpoints are all different (no arcs from $P$ are incident with the same node). When all nodes of $G$ are incident with some arc in $P$, we call $P$ a perfect matching.” For the graph in the first figure of this lesson (nodes $u_1,\dots,u_6$), find a maximum cardinality matching and decide whether the graph has a perfect matching.
a) Co je v zadání?
Na prvním obrázku lekce najdi co největší párování a rozhodni, jestli existuje perfektní (tj. párování pokrývající všech 6 vrcholů).
b) Co k tomu budeme potřebovat?
- Tato lekce — definice párování a perfektního párování.
- [L0.1] Co je graf — hrana, incidence s vrcholem.
c) Jak nad úlohou uvažovat?
6 vrcholů → perfektní párování by mělo 3 hrany pokrývající každý vrchol právě jednou. Zkus vrcholy rozdělit do tří disjunktních dvojic spojených hranou. Pomáhá začít od vrcholů s nejmenším stupněm (mají nejmíň možností).
d) Úplné řešení
Hrany grafu: $u_1u_2$, $u_1u_4$, $u_2u_3$, $u_2u_5$, $u_3u_6$, $u_4u_5$, $u_5u_6$. Vrchol $u_1$ má jen sousedy $u_2, u_4$. Zkusím $u_1u_4$: zbývá spárovat $u_2, u_3, u_5, u_6$ — vezmu $u_2u_5$? Pak zbyde $u_3, u_6$ a hrana $u_3u_6$ existuje ✓. Tedy $$M = \{u_1u_4,\; u_2u_5,\; u_3u_6\}$$ je párování o 3 hranách pokrývající všech 6 vrcholů — perfektní párování existuje a $M$ je zároveň maximum (víc než $6/2 = 3$ hran párování mít nemůže).
A bus company has $m$ morning runs and $n$ afternoon runs that it needs to assign them to its $n$ drivers. The runs are of different duration. If the total duration of the morning and afternoon runs assigned to a driver is more than a specified $D$, the driver receives a premium payment for each hour of overtime. The company would like to assign the runs to the drivers to minimize the total number of overtime hours.
(a) Formulate this problem as an appropriate matching problem. Formally specify input parameters of the problem.
(b) Suppose that we arrange the morning runs in the non-decreasing order of their duration and the afternoon runs in the non-increasing order of their duration. If we assign each driver $i$ to the $i$th morning run and the $i$th afternoon run, do we obtain the optimal assignment? Outline the proof or find a counterexample.
a) Co je v zadání?
Ranní a odpolední jízdy se mají rozdělit řidičům po dvojicích (každý řidič jedna ranní + jedna odpolední); přesčas řidiče je čas nad limit $D$. Cíl: minimalizovat celkové přesčasy. Část (a): pojmenuj to jako úlohu o párování. Část (b): rozhodni, zda „nejkratší ranní s nejdelší odpolední“ je optimum.
b) Co k tomu budeme potřebovat?
- Tato lekce — min-weight perfect matching v úplném bipartitním grafu (assignment problem).
- Tato lekce — bipartitní graf (zaveden u problému b výše) a jeho úplná varianta $K_{n,n}$; z [L0.1] Co je graf stačí hrana a incidence.
c) Jak nad úlohou uvažovat?
(a) Co jsou dvě strany bipartitního grafu? Co znamená hrana $(i,j)$ a jakou má cenu (kolik přesčasu vznikne, když ranní $i$ a odpolední $j$ dostane tentýž řidič)? Které párování odpovídá přípustnému přiřazení — stačí libovolné, nebo perfektní? (b) Vezmi dvě dvojice „prohozené“ proti seřazenému pravidlu a porovnej přesčas obou variant (výměnný argument). Pomůže funkce $o(x) = \max\{0, x - D\}$ a její konvexita.
d) Úplné řešení
(a) Vstup: doby ranních jízd $m_i$, doby odpoledních jízd $a_j$, limit $D$ (a $m = n$, aby vyšlo přiřazení každému řidiči). Přesčas dvojice: $c_{ij} = o(m_i + a_j) = \max\{0,\, m_i + a_j - D\}$. Sestroj úplný bipartitní graf $K_{n,n} = (M \cup A, E)$, kde $M$ = ranní jízdy, $A$ = odpolední; hrana $(i,j)$ = „jeden řidič dostane ranní $i$ a odpolední $j$“ s váhou $c_{ij}$. Přípustné přiřazení = perfektní párování (každá jízda právě jednou), takže úloha je minimum-weight perfect matching v $K_{n,n}$ — assignment problem. Ekvivalentně: $\min \sum_{i}\sum_{j} c_{ij} x_{ij}$ za podmínek $\sum_j x_{ij} = 1\ \forall i$, $\sum_i x_{ij} = 1\ \forall j$, $x_{ij} \in \{0,1\}$.
(b) Ano, seřazené protichůdné párování je optimální. Výměnný důkaz: vezmi $m_i \le m_j$ a $a_p \le a_q$. „Souhlasné“ spárování $(m_i,a_p), (m_j,a_q)$ vs. „protichůdné“ $(m_i,a_q), (m_j,a_p)$. Označ $A = m_i + a_p$, $\Delta = m_j - m_i \ge 0$, $\Gamma = a_q - a_p \ge 0$; součty jsou $A,\ A{+}\Delta{+}\Gamma$ vs. $A{+}\Gamma,\ A{+}\Delta$ (stejný celkový čas, protichůdné je vyrovnanější). Stačí ukázat $$o(A+\Gamma) + o(A+\Delta) \;\le\; o(A) + o(A+\Delta+\Gamma).$$ S $\alpha = A - D$ rozbor tří případů: (1) $\alpha \ge 0$ — obě strany rovny $2\alpha + \Delta + \Gamma$; (2) $\alpha + \Delta + \Gamma \le 0$ — všechny členy nulové; (3) $\alpha < 0 < \alpha + \Delta + \Gamma$ — pravá strana je $\alpha + \Delta + \Gamma$, levá nejvýš $2\alpha + \Delta + \Gamma \le \alpha + \Delta + \Gamma$ (protože $\alpha \le 0$), případně menší. Výměna tedy nikdy nezhorší cíl; opakovaným odstraňováním „inverzí“ dojdeš až k seřazenému protichůdnému párování — to je optimální. $\blacksquare$