Königs sætning (kombinatorik)

I grafteorien hævder König-sætningen (König-Egerváry-sætningen, den ungarske sætning [1] ) , bevist af Denes König i 1931 [2] , ækvivalensen af problemerne med at finde den største matchende og den mindste toppunktsdækning i todelt grafer . Det blev uafhængigt opdaget, i samme 1931 [3] , af Jeno Egervari i en noget mere generel form for tilfældet med vægtede grafer .

Definitioner

En graf kaldes todelt, hvis dens toppunkter kan opdeles i to sæt, således at hver kant har sine endespidser i forskellige mængder.

Toppunktet på en graf er et sæt af hjørner, således at enhver kant på grafen har mindst et endepunkt fra dette sæt. Et toppunktsdæksel kaldes det mindste , hvis intet andet toppunktsdæksel har færre hjørner.

En matchning i en graf er et sæt kanter, der ikke har fælles endespidser. En matching kaldes den største , hvis ingen anden matching har flere kanter.

Udtalelse af sætningen

I enhver todelt graf er antallet af kanter i den største matchning lig med antallet af toppunkter i det mindste toppunktsdæksel.

Eksempel

Den todelte graf i figuren ovenfor har 7 spidser i hver af delene. En matchning med 6 kanter er fremhævet med blåt, og et toppunktsdæksel er fremhævet med rødt. Dette dæksel er det mindste i størrelse, da ethvert toppunkt i dækslet skal omfatte mindst en endespids af en matchende kant. På samme måde er der ingen større matchning, da enhver matchende kant skal indeholde mindst et endepunkt fra toppunktet, så denne matchning er den største. Koenigs teorem hævder blot ligheden mellem størrelserne af matchningen og omslaget (i dette eksempel er begge tal lig med seks). $\{x_{2},x_{4},x_{5},y_{2},y_{4},y_{6}\}$

Bevis

Lad en todelt graf gives , og vær den største match i . $G=(X,Y,E)$ $M$ $G$

Først overveje tilfældet, når matchningen mætter alle hjørner af brøken , det vil sige størrelsen af matchningen er lig med . Det er klart, at hele andelen er et toppunktsdæksel i grafen , derfor er det også det mindste toppunktsdæksel, og i dette tilfælde er påstanden om sætningen sand. $M$ $x$ $M$ $|X|$ $x$ $G$

Ellers tager vi alle hjørnerne af delen , der ikke er mættet med matching , og kører en bredde-først gennemløb fra dem i henhold til følgende regel: $x$ $M$

Fra venstre mod højre passerer vi kun langs de kanter, der ikke er inkluderet i (vi vil kalde dem sorte). $M$
Fra højre til venstre passerer vi kun langs kanterne inkluderet i (vi vil kalde dem blå). $M$

Lad og være delmængderne af toppunkterne i venstre og højre del besøgt under gennemkørslen, og og være delmængderne af henholdsvis de ubesøgte toppunkter (se figuren til højre). ${\displaystyle X^{+))$ ${\displaystyle Y^{+))$ $X^{-}$ $Y^{-}$

Der er ingen sorte kanter mellem sættene og , for ellers ville vi under gennemgangen besøge hjørner fra sættet . Af en lignende grund er der ingen blå kanter mellem sættene og . ${\displaystyle X^{+))$ $Y^{-}$ $Y^{-}$ $X^{-}$ ${\displaystyle Y^{+))$

Lad os bevise, at der ikke er blå kanter mellem sættene og enten. Tværtimod , lad der være sådan en kant . Toppunktet kunne ikke være udgangspunktet for en bredde-første gang, da det er mættet med matchende . Derfor kom den bredde-første gang til fra nogle toppunkter langs den blå kant, hvilket betyder, at to blå kanter og er indfaldende til toppunktet . Men dette er umuligt, da de blå kanter danner en match. ${\displaystyle X^{+))$ $Y^{-}$ $\{x^{+},y^{-}\}$ ${\displaystyle x^{+))$ $M$ ${\displaystyle x^{+))$ ${\displaystyle y^{+))$ ${\displaystyle x^{+))$ $\{x^{+},y^{-}\}$ $\{x^{+},y^{+}\}$

Derfor falder enhver kant af grafen G ind på enten et toppunkt fra eller et toppunkt fra , det vil sige, at det er et toppunktsdæksel. Lad os vise, at alle hjørner i er mættede med matchning . For toppunkter fra , er dette indlysende, da alle umættede hjørner af venstre del ved konstruktion ligger i . Hvis der er et umættet toppunkt i , så er der en -vekslende sti, der slutter ved det, hvilket modsiger det faktum, at matchningen er størst. Nu er det tilbage at huske, at mellem sætene og der er ingen kanter fra , Det vil sige, at hver kant af matchningen er indfaldende med nøjagtigt et toppunkt fra toppunktet dækning . Derfor, , og toppunktet dækning er den mindste [4] . $X^{-}$ ${\displaystyle Y^{+))$ ${\displaystyle X^{-}\kop Y^{+))$ ${\displaystyle X^{-}\kop Y^{+))$ $M$ $X^{-}$ ${\displaystyle X^{+))$ ${\displaystyle Y^{+))$ $M$ $M$ $X^{-}$ ${\displaystyle Y^{+))$ $M$ ${\displaystyle X^{-}\kop Y^{+))$ $|M|=|X^{-}\kop Y^{+}|$ ${\displaystyle X^{-}\kop Y^{+))$

Bevis via Ford-Fulkerson-sætningen

Opgaven med at finde den største match i en graf kan reduceres til at finde det største flow i transportnettet , således at der fra kilden til den første andel og fra den anden andel til afløbet er kanter af kapacitet , og for enhver kant af den originale graf, fra til der er en kant af kapaciteten . $G=(A,B,E)$ ${\displaystyle G'_{\infty ))$ $s$ $EN$ $B$ $t$ $en$ $(a,b)\i E$ $-en$ $b$ $+\infty$

Ifølge Ford-Fulkerson-sætningen er værdien af et sådant flow lig med værdien af den minimale cut in . Lad et sådant snit være givet af sæt af hjørner og . Hjørnerne på den originale graf kan opdeles i fire grupper, således at og , mens og . Med en sådan klassificering kan den originale graf ikke have kanter fra til , da sådanne kanter ville gøre størrelsen af snittet uendelig. ${\displaystyle G'_{\infty ))$ $S$ $T$ ${\displaystyle A_{S},A_{T},B_{S},B_{T))$ $A=A_{S}\cup A_{T}$ ${\displaystyle B=B_{S}\kop B_{T))$ $A_{S},B_{S}\subset S$ $A_{T},B_{T}\subset T$ $A_{S}$ $B_{T}$

Dette indebærer igen, at en hvilken som helst kant af grafen falder sammen med et toppunkt fra , eller et toppunkt fra . Samtidig er selve snittet opbygget af kanter fra til og fra til . Således er på den ene side toppunktet for den originale graf, på den anden side er værdien af minimumsskæringen i grafen , hvilket indebærer, at sættet er grafens minimum toppunktsdækning [5] . $A_{T}$ $B_{S}$ $s$ $A_{T}$ $B_{S}$ $t$ $A_{T}\kop B_{S}$ $|A_{T}|+|B_{S}|$ $A_{T}\kop B_{S}$ $G$

En konsekvens af Königs sætning

Lad og være henholdsvis det største matchende og det mindste toppunktsdæksel i en todelt graf . Så er enhver kant fra indfaldende til præcis et toppunkt fra . Omvendt, til enhver toppunkt i nøjagtig en kant fra er indfaldende . Med andre ord definerer incidensrelationen en bijektion mellem mængderne og . $M$ $C$ $G$ $M$ $C$ $C$ $M$ $M$ $C$

Bemærk, at hvis grafen ikke var todelt, så har to spidser fra , og nogle spidser fra , muligvis ikke indfaldende kanter fra . $G$ $M$ $C$ $C$ $M$

En algoritme til at konstruere det mindste toppunktsdæksel i en todelt graf

Den bredde-første gang beskrevet ovenfor fra beviset for sætningen konstruerer det mindste toppunktsdæksel givet den største matchning. [4] Denne algoritme har kompleksitet . Den største overensstemmelse i en todelt graf kan findes af Hopcroft-Karp-algoritmen i tid . $O(|E|)$ ${\textstyle O(|E|{\sqrt {|V|)))}$

Forbindelse med perfekte grafer

En graf siges at være perfekt , hvis dens kromatiske tal for enhver genereret undergraf er lig med størrelsen af den maksimale klike . Enhver todelt graf er perfekt, da enhver af dens undergrafer enten er todelt eller uafhængig. I en todelt graf, der ikke er uafhængig, er det kromatiske antal og størrelsen af den maksimale klike to, mens begge disse tal for et uafhængigt sæt er lig med ét.

En graf er perfekt, hvis og kun hvis dens komplement er perfekt [6] , og Königs sætning kan betragtes som ækvivalent med udsagnet om, at komplementet til en todelt graf er perfekt. Enhver komplementfarvning af en todelt graf har højst størrelse 2, og klasser af størrelse 2 danner matchninger. Kliker i komplementet til en graf G er et uafhængigt sæt i G , og som vi skrev ovenfor, er et uafhængigt sæt i en todelt graf G komplementet til et toppunktsdæksel G . Enhver matchende M i en todelt graf G med n toppunkter svarer således til en farvning af komplementet af G med n -| M | farver, som i betragtning af perfektionen af komplementet af todelte grafer svarer til et selvstændigt sæt i G med n -| M | hjørner, hvilket svarer til toppunktet G | M | toppe. Derfor beviser Koenigs teorem perfektionen af komplementerne af todelte grafer, det vil sige et resultat udtrykt i en mere eksplicit form af Gallai [7] .

Man kan også relatere Königs linjefarvesætning til en anden klasse af perfekte grafer, linjegraferne for todelte grafer. For en graf G har linjegrafen L ( G ) hjørner svarende til kanterne af G og en kant for hvert par af tilstødende kanter i G. Således er det kromatiske tal L ( G ) lig med det kromatiske indeks G. Hvis G er todelt, er kliker i L ( G ) præcis de sæt af kanter i G , der har et fælles endepunkt. Nu kan Königs linjefarvesætning, som siger, at det kromatiske indeks er lig med den maksimale grad af toppunkter i en todelt graf, tolkes som at linjegrafen for en todelt graf er perfekt.

Da linjegraferne for todelte grafer er perfekte, er komplementerne til linjegraferne for todelte grafer også perfekte. En klike i komplementet til en linjegraf for G er simpelthen en matchning af G . Og farvelægningen af komplementet af en linjegraf for G , hvis G er todelt, er en opdeling af kanterne af grafen G i delmængder af kanter, der har fælles hjørner. De endespidser, der er almindelige i disse delmængder, danner et toppunktsdæksel af grafen G . Königs sætning kan således i sig selv også tolkes som om, at komplementet af linjegrafer af todelte grafer er perfekt.

Tilføjelser

For grafer, der ikke er todelte, er situationen med de største matchende og mindste toppunktsdækningsproblemer ganske anderledes - den største matchning kan findes i polynomisk tid for enhver graf, mens det at finde det mindste toppunktdæksel er et NP-komplet problem . At færdiggøre et toppunktsdæksel for enhver graf er et uafhængigt sæt , og at finde det største uafhængige sæt er et andet NP-komplet problem.
Königs sætning svarer til en lang række andre minimakssætninger inden for grafteori og kombinatorik , såsom Halls bryllupssætning og Dilworths sætning . Da matchning i todelte grafer er et særligt tilfælde af netværksflow, følger Königs sætning også af Ford-Fulkerson-sætningen . [otte]
I det russiske internet og videnskabelig litteratur er følgende formulering af teoremet almindelig: hvis en rektangulær matrix er sammensat af nuller og ettaller, så er det mindste antal linjer, der indeholder alle ener lig med det maksimale antal ener, der kan være valgt, så ikke to af dem ligger på en og samme linje (udtrykket "linje" betyder enten en række eller en kolonne i en matrix). [9]

På trods af ækvivalensen af de to problemer med hensyn til nøjagtig løsning, er de slet ikke ækvivalente for tilnærmelsesalgoritmer . Det største matchningsproblem for todelte grafer kan tilnærmes til vilkårlig nøjagtighed i konstant tid ved hjælp af distribuerede algoritmer , i modsætning til det mindste toppunktsdækningsproblem, som kræver mindst logaritmisk tid. [ti]

Noter

↑ Evnin, 2005 .
↑ Kőnig, 1931 .
↑ Egerváry, 1931 .
↑ 12 Bondy , 1976 , s. 74-75.
↑ Cesa-Bianchi, Nicolò Matchings og max-flow min-cut teoremet (11. april 2020). Arkiveret fra originalen den 9. maj 2021. (ubestemt)
↑ Lovas, Plummer, 1998 , s. 567.
↑ Gallai, 1958 .
↑ Lovas, Plummer, 1998 , s. 89.
↑ Rybnikov, 1972 , s. 100.
↑ Göös, 2012 .