Königs teorem (kombinatorik)

I grafteorin hävdar König-satsen (König-Egerváry-satsen, den ungerska satsen [1] ) , bevisad av Denes König 1931 [2] , likvärdigheten mellan problemen med att hitta den största matchningen och det minsta vertextäcket i tvådelad grafer . Det upptäcktes självständigt, samma 1931 [3] , av Jeno Egervari i en något mer allmän form för fallet med viktade grafer .

Definitioner

En graf kallas tvådelad om dess hörn kan delas upp i två uppsättningar så att varje kant har sina ändpunkter i olika mängder.

En grafs vertextäcke är en uppsättning hörn så att varje kant på grafen har minst en ändpunkt från denna uppsättning. Ett vertextäcke kallas det minsta om inget annat vertextäcke har färre hörn.

En matchning i en graf är en uppsättning kanter som inte har gemensamma ändhörningar. En matchning kallas den största om ingen annan matchning har fler kanter.

Uttalande av satsen

I alla tvådelade grafer är antalet kanter i den största matchningen lika med antalet hörn i det minsta vertextäcket.

Exempel

Den tvådelade grafen i figuren ovan har 7 hörn i var och en av delarna. En matchning med 6 kanter markeras i blått och ett vertexskydd är markerat i rött. Detta hölje är det minsta i storlek, eftersom varje vertex i locket måste innehålla minst en ändspets av en matchande kant. På samma sätt finns det ingen större matchning, eftersom varje matchande kant måste innehålla minst en ändpunkt från vertextäcket, så denna matchning är den största. Koenigs sats hävdar bara likheten mellan storlekarna på matchningen och omslaget (i detta exempel är båda siffrorna lika med sex). ${\displaystyle \{x_{2},x_{4},x_{5},y_{2},y_{4},y_{6}\))$

Bevis

Låt en tvådelad graf ges och vara den största matchningen i . $G=(X,Y,E)$ $M$ $G$

Tänk först på fallet när matchningen mättar alla hörn av fraktionen , det vill säga storleken på matchningen är lika med . Uppenbarligen är hela aktien ett vertextäcke i grafen , därför är det också det minsta vertextäcket, och i det här fallet är påståendet om satsen sant. $M$ $X$ $M$ $|X|$ $X$ $G$

Annars tar vi alla hörn av delen som inte är mättade med matchning och kör en bredd-först genomgång från dem enligt följande regel: $X$ $M$

Från vänster till höger passerar vi bara längs kanterna som inte ingår i (vi kommer att kalla dem svarta). $M$
Från höger till vänster passerar vi bara längs kanterna som ingår i (vi kommer att kalla dem blå). $M$

Låta och vara delmängderna av hörnen av de vänstra och högra delarna som besöks under genomgången, och och vara delmängderna av de obesökta hörnen, respektive (se bilden till höger). ${\displaystyle X^{+))$ ${\displaystyle Y^{+))$ $X^{-}$ $Y^{-}$

Det finns inga svarta kanter mellan uppsättningarna och , eftersom vi annars under genomgången skulle besöka hörn från uppsättningen . Av en liknande anledning finns det inga blå kanter mellan seten och . ${\displaystyle X^{+))$ $Y^{-}$ $Y^{-}$ $X^{-}$ ${\displaystyle Y^{+))$

Låt oss bevisa att det inte finns några blå kanter mellan seten och antingen. Tvärtom , låt det finnas en sådan kant . Toppunkten kunde inte vara utgångspunkten för en bredd-första promenad, eftersom den är mättad med matchning . Därför kom den bredd-första vandringen till från någon vertex längs den blå kanten, vilket innebär att två blå kanter och är infallande till vertexen . Men detta är omöjligt, eftersom de blå kanterna bildar en matchning. ${\displaystyle X^{+))$ $Y^{-}$ $\{x^{+},y^{-}\}$ ${\displaystyle x^{+))$ $M$ ${\displaystyle x^{+))$ ${\displaystyle y^{+))$ ${\displaystyle x^{+))$ $\{x^{+},y^{-}\}$ $\{x^{+},y^{+}\}$

Därför faller varje kant av grafen G mot antingen en vertex från eller en vertex från , det vill säga det är ett vertextäcke. Låt oss visa att alla hörn i är mättade med matchning . För hörn från , är detta uppenbart, eftersom alla omättade hörn i den vänstra delen genom konstruktion ligger i . Om det finns en omättad vertex i , så finns det en -alternerande bana som slutar vid den, vilket motsäger det faktum att matchningen är störst. Nu återstår att komma ihåg att mellan uppsättningarna och det finns inga kanter från , det vill säga varje kant av matchningen är infallande med exakt en vertex från vertextäcket . Därför, och vertextäcket är det minsta [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^{+))$

Bevis via Ford-Fulkerson-satsen

Uppgiften att hitta den största matchningen i en graf kan reduceras till att hitta det största flödet i transportnätet , så att det från källan till den första andelen och från den andra delen till avloppet finns kanter av kapacitet , och för vilken kant som helst. av den ursprungliga grafen, från till att det finns en kant av kapacitet . $G=(A,B,E)$ ${\displaystyle G'_{\infty ))$ $s$ $A$ $B$ $t$ $ett$ $(a,b)\i E$ $a$ $b$ $+\infty$

Enligt Ford-Fulkerson-satsen är värdet på ett sådant flöde lika med värdet av den minsta inskärningen . Låt ett sådant snitt ges av uppsättningar av hörn och . Topparna i den ursprungliga grafen kan delas in i fyra grupper så att och , while och . Med en sådan klassificering kan den ursprungliga grafen inte ha kanter från till , eftersom sådana kanter skulle göra snittets storlek oändlig. ${\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}$

Detta innebär i sin tur att valfri kant på grafen faller in mot en vertex från , eller en vertex från . Samtidigt är själva snittet uppbyggt av kanter från till och från till . Å ena sidan är alltså vertextäcket för den ursprungliga grafen, å andra sidan är värdet för det minsta snittet i grafen , vilket innebär att uppsättningen är grafens minsta vertextäckning [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$

En följd av Königs teorem

Låta respektive vara det största matchande och det minsta vertextäcket i en tvådelad graf . Då är varje kant från infallande till exakt en vertex från . Omvänt, till någon vertex i exakt en kant från är infallande . Med andra ord, incidensrelationen definierar en bijektion mellan mängderna och . $M$ $C$ $G$ $M$ $C$ $C$ $M$ $M$ $C$

Observera att om grafen inte var tvådelad, kanske två hörn från , och vissa hörn från , kanske inte har infallande kanter från . $G$ $M$ $C$ $C$ $M$

En algoritm för att konstruera det minsta vertextäcket i en tvådelad graf

Den bredd-första promenad som beskrivs ovan från beviset för satsen konstruerar det minsta vertextäcket givet den största matchningen. [4] Denna algoritm har komplexitet . Den största matchningen i en tvådelad graf kan hittas av Hopcroft–Karp-algoritmen i tid . $O(|E|)$ ${\textstyle O(|E|{\sqrt {|V|)))}$

Anslutning med perfekta grafer

En graf sägs vara perfekt om, för en genererad subgraf , dess kromatiska nummer är lika med storleken på den maximala klicken . Varje tvådelad graf är perfekt eftersom vilken som helst av dess subgrafer är antingen tvådelad eller oberoende. I en tvådelad graf som inte är oberoende är det kromatiska antalet och storleken på den maximala klicken två, medan för en oberoende uppsättning är båda dessa tal lika med ett.

En graf är perfekt om och endast om dess komplement är perfekt [6] , och Königs sats kan anses likvärdig med påståendet att komplementet till en tvådelad graf är perfekt. Varje komplementfärgning av en tvådelad graf har storlek högst 2, och klasser av storlek 2 bildar matchningar. Klickor i komplementet till en graf G är en oberoende mängd i G , och som vi skrev ovan är en oberoende mängd i en tvådelad graf G komplementet till ett vertextäcke G . Således motsvarar varje matchande M i en tvådelad graf G med n hörn en färgning av komplementet till G med n -| M | färger, som, med hänsyn till perfektionen av komplementet av tvådelade grafer, motsvarar en oberoende mängd i G med n -| M | hörn, vilket motsvarar vertextäcket G | M | toppar. Därför bevisar Koenigs teorem perfektionen av komplementen till tvådelade grafer, det vill säga ett resultat uttryckt i en mer explicit form av Gallai [7] .

Man kan också relatera Königs linjefärgningssats till en annan klass av perfekta grafer, linjegraferna för tvådelade grafer. För en graf G har linjegrafen L ( G ) hörn som motsvarar kanterna på G , och en kant för varje par intilliggande kanter i G. Således är det kromatiska talet L ( G ) lika med det kromatiska indexet G. Om G är tvådelad är klickar i L ( G ) exakt de uppsättningar kanter i G som har en gemensam ändpunkt. Nu kan Königs linjefärgsats, som säger att det kromatiska indexet är lika med den maximala graden av hörn i en tvådelad graf, tolkas som att linjegrafen för en tvådelad graf är perfekt.

Eftersom linjegraferna för tvådelade grafer är perfekta, är komplementen till linjediagrammen för tvådelade grafer också perfekta. En klick i komplementet till ett linjediagram för G är helt enkelt en matchning av G . Och färgningen av komplementet till en linjegraf för G , om G är tvådelad, är en uppdelning av kanterna på grafen G i delmängder av kanter som har gemensamma hörn. Ändpunkten som är vanliga i dessa delmängder bildar ett vertextäcke av grafen G . Således kan Königs sats i sig också tolkas som att komplementet av linjegrafer av tvådelade grafer är perfekt.

Tillägg

För grafer som inte är tvådelade är situationen med de största matchande och minsta vertextäckningsproblemen helt annorlunda - den största matchningen kan hittas i polynomtid för vilken graf som helst, medan att hitta det minsta vertextäcket är ett NP-komplett problem . Att fylla i ett vertextäcke för vilken graf som helst är en oberoende uppsättning , och att hitta den största oberoende uppsättningen är ett annat NP-komplett problem.
Königs sats är likvärdig med en mängd andra minimaxsatser inom grafteori och kombinatorik , som Halls bröllopssats och Dilworths sats . Eftersom matchning i tvådelade grafer är ett specialfall av nätverksflöde, följer Königs sats också från Ford-Fulkersons sats . [åtta]
I den ryska Internet och vetenskaplig litteratur är följande formulering av teoremet vanlig: om en rektangulär matris består av nollor och ettor, är det minsta antalet rader som innehåller alla lika med det maximala antalet ettor som kan vara vald så att inte två av dem ligger på en och samma linje (termen "linje" betyder antingen en rad eller en kolumn i en matris). [9]

Trots likvärdigheten mellan de två problemen när det gäller exakt lösning, är de inte alls ekvivalenta för approximationsalgoritmer . Det största matchningsproblemet för tvådelade grafer kan approximeras till godtycklig noggrannhet i konstant tid med hjälp av distribuerade algoritmer , i motsats till problemet med minsta vertextäckning, som kräver åtminstone logaritmisk tid. [tio]

Anteckningar

↑ Evnin, 2005 .
↑ Kőnig, 1931 .
↑ Egerváry, 1931 .
↑ 12 Bondy , 1976 , s. 74-75.
↑ Cesa-Bianchi, Nicolò Matchningar och maxflödesmin-cut-satsen (11 april 2020). Arkiverad från originalet den 9 maj 2021. (obestämd)
↑ Lovas, Plummer, 1998 , sid. 567.
↑ Gallai, 1958 .
↑ Lovas, Plummer, 1998 , sid. 89.
↑ Rybnikov, 1972 , sid. 100.
↑ Göös, 2012 .

Länkar

Lovas L., Plummer M. Tillämpade problem med grafteori. Teori om matchningar i matematik, fysik, kemi. — M.: Mir, 1998. — 653 sid. — ISBN 5-03-002517-0 .
Rybnikov K.A. Introduktion till kombinatorisk analys. - Moscow State University, 1972.

Evnin A. Yu. Runt Halls sats // Math. arr .. - 2005. - T. 3 (34) . - S. 2-23 . (ryska)

Bondy, JA, Murty, USR Grafteori med applikationer. - North Holland, 1976. - ISBN 0-444-19451-7 .

Egervary, Jenő. Matrixok kombinatorius tulajdonságairól [Om kombinatoriska egenskaper hos matriser] (Hung.) // Matematikai és Fizikai Lapok. - 1931. - Vol. 38. - S. 16-28.

Gallai, Tibor. Maximum-minimum Sätze über Graphen // Acta Math. Acad. sci. Ungern.. - 1958. - Vol. 9. - Fråga. 3-4 . - s. 395-434. - doi : 10.1007/BF02020271 .

Herregud, Mika. Jukka Suomela. 26th International Symposium on Distributed Computing (DISC), Salvador, Brasilien, oktober 2012. - 2012.

Kőnig, Denes. Gráfok és mátrixok (ungerska) // Matematikai és Fizikai Lapok. - 1931. - Vol. 38. - S. 116-119.