Königova věta (kombinatorika)

V teorii grafů Königova věta (König-Egerváryho věta, maďarská věta [1] ) , dokázaná Denesem Königem v roce 1931 [2] , prosazuje rovnocennost problémů hledání největší shody a nejmenšího pokrytí vrcholů v bipartitu . grafy . Nezávisle na tom byl ve stejném roce 1931 [3] objeven Jeno Egervari v poněkud obecnější podobě pro případ vážených grafů .

Definice

Graf se nazývá bipartitní, pokud lze jeho vrcholy rozdělit na dvě množiny tak, že každá hrana má své koncové vrcholy v různých množinách.

Vrcholový kryt grafu je množina vrcholů taková, že každá hrana grafu má alespoň jeden koncový vrchol z této množiny. Vrcholový kryt se nazývá nejmenší , pokud žádný jiný vrcholový kryt nemá méně vrcholů.

Shoda v grafu je množina hran, které nemají společné koncové vrcholy. Shoda se nazývá největší , pokud žádná jiná shoda nemá více hran.

Prohlášení věty

V každém bipartitním grafu je počet hran v největší shodě roven počtu vrcholů v nejmenším pokrytí vrcholů.

Příklad

Bipartitní graf na obrázku výše má 7 vrcholů v každé z částí. Shoda se 6 hranami je zvýrazněna modře a kryt vrcholu je zvýrazněn červeně. Tento kryt má nejmenší velikost, protože jakýkoli vrchol krytu musí obsahovat alespoň jeden koncový vrchol odpovídající hrany. Stejně tak nedochází k většímu párování, protože jakákoli odpovídající hrana musí obsahovat alespoň jeden koncový vrchol z krytu vertexu, takže toto párování je největší. Koenigův teorém pouze tvrdí rovnost velikostí párování a krytí (v tomto příkladu jsou obě čísla rovna šesti). ${\displaystyle \{x_{2},x_{4},x_{5},y_{2},y_{4},y_{6}\))$

Důkaz

Nechť je dán bipartitní graf a je největší shoda v . $G=(X,Y,E)$ $M$ $G$

Nejprve zvažte případ, kdy shoda saturuje všechny vrcholy zlomku , to znamená, že velikost shody je rovna . Je zřejmé, že celý podíl je pokrytím vrcholů v grafu , proto je to také nejmenší pokrytí vrcholu a v tomto případě je tvrzení věty pravdivé. $M$ $X$ $M$ $|X|$ $X$ $G$

V opačném případě vezmeme všechny vrcholy části , které nejsou nasyceny párováním , a spustíme z nich přechod na šířku podle následujícího pravidla: $X$ $M$

Zleva doprava procházíme pouze po okrajích, které nejsou zahrnuty ( nazveme je černé). $M$
Zprava doleva procházíme pouze po okrajích zahrnutých v (budeme jim říkat modré). $M$

Nechť a jsou podmnožiny vrcholů levé a pravé části navštívené během průchodu a jsou podmnožiny nenavštívených vrcholů (viz obrázek vpravo). ${\displaystyle X^{+))$ ${\displaystyle Y^{+))$ $X^{-}$ $Y^{-}$

Mezi množinami nejsou žádné černé okraje a , protože jinak bychom při procházení navštívili vrcholy z množiny . Z podobného důvodu nejsou modré okraje mezi sadami a . ${\displaystyle X^{+))$ $Y^{-}$ $Y^{-}$ $X^{-}$ ${\displaystyle Y^{+))$

Dokažme, že mezi množinami a ani jedním nejsou žádné modré okraje . Naopak budiž taková hrana . Vrchol nemůže být výchozím bodem pro procházku nejprve na šířku, protože je nasycen odpovídajícími . Proto první procházka na šířku přišla z nějakého vrcholu podél modrého okraje, což znamená, že dva modré okraje a jsou incidentní s vrcholem . Ale to je nemožné, protože modré okraje tvoří shodu. ${\displaystyle X^{+))$ $Y^{-}$ $\{x^{+},y^{-}\}$ ${\displaystyle x^{+))$ $M$ ${\displaystyle x^{+))$ ${\displaystyle y^{+))$ ${\displaystyle x^{+))$ $\{x^{+},y^{-}\}$ $\{x^{+},y^{+}\}$

Proto je jakákoli hrana grafu G incidentní buď s vrcholem z nebo s vrcholem z , to znamená, že je to kryt vrcholu. Ukažme, že všechny vrcholy v jsou nasyceny párováním . Pro vrcholy z , je to zřejmé, protože konstrukcí všechny nenasycené vrcholy levé části leží v . Pokud je v , nenasycený vrchol, pak na něm končí -alternující cesta, což je v rozporu s tím, že shoda je největší. Nyní zbývá připomenout, že mezi množinami a nejsou žádné hrany z , to znamená, že každá hrana shody je incidentní právě s jedním vrcholem z krytu vrcholu . Proto je , a vertexové pokrytí nejmenší [4] . $X^{-}$ ${\displaystyle Y^{+))$ ${\displaystyle X^{-}\cup Y^{+))$ ${\displaystyle X^{-}\cup Y^{+))$ $M$ $X^{-}$ ${\displaystyle X^{+))$ ${\displaystyle Y^{+))$ $M$ $M$ $X^{-}$ ${\displaystyle Y^{+))$ $M$ ${\displaystyle X^{-}\cup Y^{+))$ $|M|=|X^{-}\cup Y^{+}|$ ${\displaystyle X^{-}\cup Y^{+))$

Důkaz pomocí Ford-Fulkersonovy věty

Úkol najít největší shodu v grafu lze redukovat na nalezení největšího toku v dopravní síti tak , že od zdroje k prvnímu podílu a od druhého podílu k odtoku existují okraje kapacity a pro jakoukoli hranu původního grafu, od do je hrana kapacity . $G=(A,B,E)$ ${\displaystyle G'_{\infty ))$ $s$ $A$ $B$ $t$ $jeden$ $(a,b)\in E$ $A$ $b$ $+\infty$

Podle Fordova-Fulkersonova teorému je hodnota takového toku rovna hodnotě minimálního zářezu v . Nechť je takový řez dán množinami vrcholů a . Vrcholy původního grafu lze rozdělit do čtyř skupin jako a , while a . S takovou klasifikací nemůže mít původní graf hrany od do , protože takové hrany by velikost řezu učinily nekonečnou. ${\displaystyle G'_{\infty ))$ $S$ $T$ ${\displaystyle A_{S},A_{T},B_{S},B_{T))$ $A=A_{S}\cup A_{T}$ ${\displaystyle B=B_{S}\cup B_{T))$ $A_{S},B_{S}\subset S$ $A_{T},B_{T}\subset T$ $A_{S}$ $B_{T}$

To zase znamená, že jakákoli hrana grafu je incidentní s vrcholem z , nebo s vrcholem z . Samotný řez je přitom tvořen hranami od do a od do . Na jedné straně je tedy vrcholové krytí původního grafu, na druhé straně je hodnota minimálního řezu v grafu , což znamená, že množina je minimální vertexové krytí grafu [5] . $A_{T}$ $B_{S}$ $s$ $A_{T}$ $B_{S}$ $t$ $A_{T}\cup B_{S}$ $|A_{T}|+|B_{S}|$ $A_{T}\cup B_{S}$ $G$

Důsledek Königovy věty

Nechť a být největší odpovídající a nejmenší vrcholový kryt v bipartitním grafu . Potom jakákoli hrana od je incidentní přesně s jedním vrcholem od . Naopak do libovolného vrcholu v přesně jedné hraně od je incident . Jinými slovy, relace incidence definuje bijekci mezi množinami a . $M$ $C$ $G$ $M$ $C$ $C$ $M$ $M$ $C$

Všimněte si, že pokud by graf nebyl bipartitní, pak dva vrcholy z , a některé vrcholy z , nemusí mít dopadající hrany z . $G$ $M$ $C$ $C$ $M$

Algoritmus pro konstrukci nejmenšího vertexového pokrytí v bipartitním grafu

Výše popsaná procházka do šířky z důkazu věty zkonstruuje nejmenší vrcholové pokrytí dané největší shodou. [4] Tento algoritmus je složitý . Největší shodu v bipartitním grafu lze nalézt pomocí Hopcroft-Karpova algoritmu v čase . $O(|E|)$ ${\textstyle O(|E|{\sqrt {|V|)))}$

Spojení s dokonalými grafy

O grafu se říká, že je dokonalý , pokud se pro jakýkoli vygenerovaný podgraf jeho chromatické číslo rovná velikosti maximální kliky . Jakýkoli bipartitní graf je dokonalý, protože kterýkoli z jeho podgrafů je buď bipartitní, nebo nezávislý. V bipartitním grafu, který není nezávislý, jsou chromatické číslo a velikost maximální kliky dvě, zatímco pro nezávislou množinu jsou obě tato čísla rovna jedné.

Graf je dokonalý právě tehdy, když je jeho doplněk dokonalý [6] , přičemž Königovu větu lze považovat za ekvivalentní tvrzení, že doplněk bipartitního grafu je dokonalý. Jakékoli doplňkové obarvení bipartitního grafu má velikost nejvýše 2 a třídy velikosti 2 tvoří shody. Kliky v doplňku grafu G jsou nezávislou množinou v G , a jak jsme psali výše, nezávislá množina v bipartitním grafu G je doplňkem pokrytí vrcholu G . Jakákoli shoda M v bipartitním grafu G s n vrcholy tedy odpovídá zabarvení doplňku G s n -| M | barev, což s ohledem na dokonalost doplňku bipartitních grafů odpovídá nezávislé množině v G s n -| M | vrcholy, což odpovídá vrcholovému krytu G | M | vrcholy. Koenigův teorém proto dokazuje dokonalost doplňků bipartitních grafů, tedy výsledek vyjádřený v explicitnější podobě Gallai [7] .

Königovu větu o barvení čar lze také vztáhnout k jiné třídě dokonalých grafů, liniovým grafům bipartitních grafů. Pro graf G má spojnicový graf L ( G ) vrcholy odpovídající hranám G a hranu pro každý pár sousedních hran v G . Takže chromatické číslo L ( G ) se rovná chromatickému indexu G. Pokud je G bipartitní, kliky v L ( G ) jsou přesně množiny hran v G , které mají společný koncový vrchol. Nyní Königův teorém o zbarvení čar, který říká, že chromatický index se rovná maximálnímu stupni vrcholů v bipartitním grafu, lze interpretovat tak, že spojnicový graf bipartitního grafu je dokonalý.

Protože spojnicové grafy bipartitních grafů jsou dokonalé, jsou dokonalé i doplňky spojnicových grafů bipartitních grafů. Klika v doplňku spojnicového grafu pro G je jednoduše shoda G . A obarvení doplňku spojnicového grafu pro G , je-li G bipartitní, je rozdělením hran grafu G na podmnožiny hran, které mají společné vrcholy. Koncové vrcholy, které jsou společné v těchto podmnožinách, tvoří vrcholový kryt grafu G . Samotnou Königovu větu lze tedy také interpretovat jako tvrzení, že doplnění spojnicových grafů bipartitních grafů je dokonalé.

Dodatky

U grafů, které nejsou bipartitní, je situace s problémy největší shody a nejmenšího pokrytí vrcholů zcela odlišná – největší shodu lze nalézt v polynomiálním čase pro jakýkoli graf, zatímco nalezení nejmenšího pokrytí vrcholů je NP-úplný problém . Dokončení pokrytí vrcholů pro jakýkoli graf je nezávislá množina a nalezení největší nezávislé množiny je dalším NP-úplným problémem.
Königův teorém je ekvivalentní řadě dalších teorémů o minimaxu v teorii grafů a kombinatorice , jako je Hallův svatební teorém a Dilworthův teorém . Protože párování v bipartitních grafech je speciální případ toku sítě, Königova věta také vyplývá z Ford-Fulkersonovy věty . [osm]
V ruském internetu a vědecké literatuře je běžná následující formulace věty: pokud je obdélníková matice složena z nul a jedniček, pak se minimální počet řádků obsahujících všechny jedničky rovná maximálnímu počtu jedniček, které mohou být vybrány tak, aby žádné dva z nich neležely na jedné a téže přímce (pojem "čára" znamená buď řádek nebo sloupec v matici). [9]

Navzdory ekvivalenci těchto dvou problémů z hlediska přesného řešení nejsou pro aproximační algoritmy vůbec ekvivalentní . Největší problém shody pro bipartitní grafy lze aproximovat na libovolnou přesnost v konstantním čase pomocí distribuovaných algoritmů , na rozdíl od problému nejmenšího pokrytí vrcholů, který vyžaduje alespoň logaritmický čas. [deset]

Poznámky

↑ Evnin, 2005 .
↑ Kőnig, 1931 .
↑ Egerváry, 1931 .
↑ 12 Bondy , 1976 , s. 74-75.
↑ Cesa-Bianchi, Nicolò Matchings a věta o max-flow min-cut (11. dubna 2020). Archivováno z originálu 9. května 2021. (neurčitý)
↑ Lovas, Plummer, 1998 , str. 567.
↑ Gallai, 1958 .
↑ Lovas, Plummer, 1998 , str. 89.
↑ Rybnikov, 1972 , s. 100.
↑ Göös, 2012 .

Odkazy

Lovas L., Plummer M. Aplikované problémy teorie grafů. Teorie párování v matematice, fyzice, chemii. — M.: Mir, 1998. — 653 s. — ISBN 5-03-002517-0 .
Rybnikov K.A. Úvod do kombinatorické analýzy. - Moskevská státní univerzita, 1972.

Evnin A. Yu. Kolem Hallova teorému // Matematika. arr .. - 2005. - T. 3 (34) . - S. 2-23 . (Ruština)

Bondy, JA, Murty, USR Teorie grafů s aplikacemi. - Severní Holandsko, 1976. - ISBN 0-444-19451-7 .

Egervary, Jenő. Matrixok kombinatorius tulajdonságairól [O kombinatorických vlastnostech matric] (maď.) // Matematikai és Fizikai Lapok. - 1931. - Sv. 38. - S. 16-28.

Gallai, Tibore. Maximum-minimum Sätze über Graphen // Acta Math. Akad. sci. Maďarsko.. - 1958. - Sv. 9. - Vydání. 3-4 . - S. 395-434. - doi : 10.1007/BF02020271 .

Goos, Mika. Jukka Suomela. 26. mezinárodní symposium o distribuovaných počítačích (DISC), Salvador, Brazílie, říjen 2012. - 2012.

Kőnig, Denes. Gráfok és mátrixok (maďarština) // Matematikai és Fizikai Lapok. - 1931. - Sv. 38. - S. 116-119.