Vrcholové pokrytí

Úloha číslo: 3765

Vrcholovým pokrytím grafu \(G=(V,E)\) nazveme množinu \(U\subseteq V\), která má s každou hranou grafu alespoň jeden společný vrchol. Dokažte, že v každém bipartitním grafu platí, že velikost nejmenšího vrcholového pokrytí je rovna velikosti největšího párování.

  • Nápověda

    Použijte dualitu mezi toky a řezy ve vhodné síti.

  • Řešení

    Bipartitní graf s částmi \(A,B\) doplníme na síť s jednotkovými kapacitami tak, že zdroj \(z\) připojime hranami ke všem vrcholům z množiny \(A\), podobně \(B\) ke stoku \(s\), a všechny hrany vedeme z \(A\) do \(B\).

    Nalezneme maximální tok, a protože kapacity hran jsou celočíselné, lze zvolit celočíselný maximální tok. Použité hrany toku mezi částmi \(A\) a \(B\) jsou párování, protože z žádného vrcholu \(A\) nemohou vést dvě hrany (kapacita hran do \(A\) je jednotková); podobně pro vrcholy \(B\). Jde o maximální párování, protože každé párování lze převést na tok.

    Máme-li hranový řez \(F\), lze bez újmy na obecnosti předpokládat, že každá hrana řezu je incidentní se \(z\) nebo se \(s\) (Jinak hranu řezu mezi \(A\) a \(B\) zaměníme za jejího následníka vedoucího do \(s\).) Za \(U\) zvolme ty vrcholy z množiny \(A\cup B\), které náleží hranám řezu \(F\). Zřejmě \(|U|=|F|\). Množina \(U\) je navíc i vrcholové pokrytí původního bipartitního grafu – nepokrytá hrana by odpovídala cestě mezi \(z\) a \(s\), a tedy by \(F\) nebyla řezem.

    Obdobně, z každého vrcholového pokrytí \(U\) lze vytvořit řez stejné kapacity.

    Odtud je velikost minimálního vrcholového pokrytí rovna kapacitě minimálního řezu, a ta je rovna velikostem maximálního toku i maximálního párování.

Obtížnost: Středně těžká úloha
Úloha na dokazování, ověřování
En translation
	Zaslat komentář k úloze