König-tétel (kombinatorika)

A gráfelméletben a König-tétel (a König-Egerváry-tétel, a magyar tétel [1] ) König Dénes által 1931-ben [2] bizonyítja a legnagyobb illeszkedés és a legkisebb csúcsfedő megtalálásának problémáinak egyenértékűségét bipartitban . grafikonok . Ugyanabban az 1931-ben [3] függetlenül fedezte fel Egervari Jenő valamivel általánosabb formában a súlyozott gráfok esetében .

Definíciók

Egy gráfot bipartitnak nevezünk, ha csúcsai két halmazra oszthatók úgy, hogy minden élnek más-más halmazban vannak a végpontjai.

A gráf csúcsborítója olyan csúcsok halmaza, ahol a gráf bármely élének legalább egy végcsúcsa van ebből a halmazból. Egy csúcsfedőt akkor nevezünk legkisebbnek , ha egyetlen másik csúcsfedőnek sincs kevesebb csúcsa.

Az illesztés a gráfban olyan élek halmaza, amelyeknek nincs közös végpontja. Egy illesztést akkor nevezünk legnagyobbnak , ha egyetlen másik illesztésnek sincs több éle.

tétel állítása

Bármely bipartit gráfban a legnagyobb illesztésben lévő élek száma megegyezik a legkisebb csúcsfedő csúcsainak számával.

Példa

A fenti ábrán látható kétrészes gráf minden részében 7 csúcsot tartalmaz. A 6 élű illesztés kék színnel, a csúcsborító pirossal van kiemelve. Ez a borító a legkisebb méretű, mivel a borító bármely csúcsának tartalmaznia kell legalább egy illeszkedő él végcsúcsát. Ugyanígy nincs nagyobb illesztés, mivel minden illeszkedő élnek tartalmaznia kell legalább egy végcsúcsot a csúcsfedőből, így ez az illesztés a legnagyobb. Koenig tétele éppen az illesztés és a fedő méretének egyenlőségét állítja (ebben a példában mindkét szám hat. $\{x_{2},x_{4},x_{5},y_{2},y_{4},y_{6}\}$

Bizonyítás

Legyen adott egy kétrészes gráf , és legyen a legnagyobb egyezésű . $G=(X,Y,E)$ $M$ $G$

Először is vizsgáljuk meg azt az esetet, amikor az illesztés a tört összes csúcsát telíti , azaz az illesztés mérete egyenlő a -val . Nyilvánvaló, hogy a teljes rész egy csúcsfedő a gráfban , ezért egyben a legkisebb csúcsfedő is, és ebben az esetben igaz a tétel állítása. $M$ $x$ $M$ $|X|$ $x$ $G$

Ellenkező esetben vesszük a rész összes olyan csúcsát, amely nincs telítve illesztéssel , és lefuttatjuk belőlük a szélesség-első bejárást a következő szabály szerint: $x$ $M$

Balról jobbra csak azokon az éleken haladunk, amelyek nem szerepelnek benne ( feketének nevezzük őket). $M$
Jobbról balra csak a benne foglalt élek mentén haladunk (kéknek fogjuk hívni). $M$

Legyen és a bejárás során meglátogatott bal és jobb oldali rész csúcsainak részhalmazai, illetve és a nem látogatott csúcsok részhalmazai (lásd a jobb oldali ábrát). ${\displaystyle X^{+))$ ${\displaystyle Y^{+))$ $X^{-}$ $Y^{-}$

A és halmazok között nincsenek fekete élek , mert különben a bejárás során a halmaz csúcsait látogatnánk meg . Hasonló okból a és halmazok között nincsenek kék élek . ${\displaystyle X^{+))$ $Y^{-}$ $Y^{-}$ $X^{-}$ ${\displaystyle Y^{+))$

Bizonyítsuk be, hogy a halmazok között nincs kék él és egyik sem. Ellenkezőleg , legyen egy ilyen él . A csúcs nem lehet a kiindulópontja egy szélességi körbejárásnak, mivel telítve van egyezéssel . Ezért a szélesség-első séta valamelyik csúcsból jött a kék él mentén, ami azt jelenti, hogy két kék él és beesik a csúcsra . De ez lehetetlen, mivel a kék élek egyezést alkotnak. ${\displaystyle X^{+))$ $Y^{-}$ $\{x^{+},y^{-}\}$ ${\displaystyle x^{+))$ $M$ ${\displaystyle x^{+))$ ${\displaystyle y^{+))$ ${\displaystyle x^{+))$ $\{x^{+},y^{-}\}$ $\{x^{+},y^{+}\}$

Ezért a G gráf bármely éle vagy egy -ból származó csúcsra, vagy egy -ból származó csúcsra esik , azaz csúcsfedő. Mutassuk meg, hogy a -ben lévő összes csúcs telített illesztéssel . A -ból származó csúcsok esetében ez nyilvánvaló, mivel a konstrukció alapján a bal oldali rész összes telítetlen csúcsa -ben van . Ha van egy telítetlen csúcs -ban, akkor ott egy -alternating útvonal végződik, ami ellentmond annak, hogy az illesztés a legnagyobb. Most nem szabad elfelejtenünk, hogy a és halmazok között nincsenek élek -ból , vagyis az illesztés minden éle pontosan egy csúcsponttal esik a csúcsfedőből . Ezért , és a csúcsfedő a legkisebb [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^{+))$

Bizonyítás a Ford-Fulkerson tételen keresztül

A legnagyobb egyezés megtalálásának feladata egy gráfban lecsökkenthető a legnagyobb áramlás megtalálására a szállítási hálózatban úgy, hogy a forrástól az első megosztásig és a második megosztástól a lefolyóig vannak kapacitásélek , és bármely élnek Az eredeti gráf tól -ig van egy kapacitás széle . $G=(A,B,E)$ ${\displaystyle G'_{\infty ))$ $s$ $A$ $B$ $t$ $egy$ $(a,b)\in E$ $a$ $b$ $+\infty$

A Ford-Fulkerson tétel szerint egy ilyen áramlás értéke egyenlő a minimális bevágás értékével . Adjanak meg egy ilyen vágást csúcsok és . Az eredeti gráf csúcsai négy csoportra oszthatók úgy, hogy és , while és . Ilyen besorolás esetén az eredeti gráfnak nem lehetnek élei től -ig , mivel az ilyen élek végtelenné tennék a vágás méretét. ${\displaystyle G'_{\infty ))$ $S$ $T$ ${\displaystyle A_{S},A_{T},B_{S},B_{T))$ $A=A_{S}\cup A_{T}$ ${\displaystyle B=B_{S}\pohár B_{T))$ $A_{S},B_{S}\subset S$ $A_{T},B_{T}\subset T$ $A_{S}$ $B_{T}$

Ez viszont azt jelenti, hogy a gráf bármely éle beesik a -ból származó csúcsra , vagy egy -ból származó csúcsra . Ugyanakkor maga a vágás a -tól és -től -ig terjedő élekből áll . Így egyrészt az eredeti gráf csúcsfedője, másrészt a gráfban a minimális vágás értéke , amiből következik, hogy a halmaz a gráf minimális csúcsfedője [5] . $A_{T}$ $B_{S}$ $s$ $A_{T}$ $B_{S}$ $t$ $A_{T}\kupa B_{S}$ $|A_{T}|+|B_{S}|$ $A_{T}\kupa B_{S}$ $G$

König tételének következménye

Legyen és legyen a legnagyobb egyező és a legkisebb csúcsfedő egy kétrészes gráfban . Ekkor bármely -ból származó él pontosan egy csúcsra esik -ból . Megfordítva, bármely csúcshoz , amely pontosan egy élből van, incidens . Más szóval, az előfordulási reláció bijekciót határoz meg a és a halmazok között . $M$ $C$ $G$ $M$ $C$ $C$ $M$ $M$ $C$

Vegye figyelembe, hogy ha a gráf nem kétrészes, akkor a -ból származó két csúcsnak és néhány -ból származó csúcsnak nem lehet incidens éle -ból . $G$ $M$ $C$ $C$ $M$

Algoritmus a legkisebb csúcsfedő megszerkesztésére egy bipartit gráfban

A tétel bizonyításából a fent leírt szélesség-első lépés a legnagyobb illesztés mellett a legkisebb csúcsfedőt konstruálja meg. [4] Ez az algoritmus összetett . A bipartit gráfban a legnagyobb egyezést a Hopcroft–Karp algoritmus találja meg időben . $O(|E|)$ ${\textstyle O(|E|{\sqrt {|V|)))}$

Kapcsolat tökéletes grafikonokkal

Egy gráfot tökéletesnek mondunk, ha bármely generált részgráf kromatikus száma megegyezik a maximális klikk méretével . Bármely kétrészes gráf tökéletes, mivel bármelyik részgráfja kétrészes vagy független. Egy nem független kétrészes gráfban a maximális klikk kromatikus száma és mérete kettő, míg független halmaz esetén mindkét szám eggyel egyenlő.

Egy gráf akkor és csak akkor tökéletes, ha a komplementere tökéletes [6] , és König tétele ekvivalensnek tekinthető azzal az állítással, hogy egy kétrészes gráf komplementere tökéletes. A kétrészes gráf bármely komplementer színezése legfeljebb 2-es mérettel rendelkezik, és a 2-es méretű osztályok egyezést alkotnak. A G gráf komplementerében lévő klikkek független halmazok G -ben, és ahogy fentebb írtuk, a G kétrészes gráfban egy független halmaz egy G csúcsborító komplementere . Így egy n csúcsú G kétrészes gráfban bármely illeszkedő M megfelel G komplementerének színezésének n -| M | színek, ami a kétrészes gráfok komplementerének tökéletessége miatt G -ben egy független halmaznak felel meg n -| M | csúcsok, ami a G | csúcsfedőnek felel meg M | csúcsok. Ezért Koenig tétele bizonyítja a kétrészes gráfok komplementereinek tökéletességét, vagyis Gallai által kifejezettebb formában kifejezett eredményt [7] .

König vonalszínezési tétele a tökéletes gráfok egy másik osztályához, a kétrészes gráfok vonalgráfjaihoz is vonatkoztatható. Egy G gráf esetén az L ( G ) vonalgráfnak G éleinek megfelelő csúcsai vannak , és G -ben minden szomszédos élpárhoz egy él . Így az L ( G ) kromatikus szám egyenlő a G kromatikus indexszel . Ha G kétrészes, akkor az L -beli klikkek ( G ) pontosan azok a G -beli élhalmazok , amelyeknek közös végcsúcsa van. König vonalszínezési tétele, amely kimondja, hogy a kromatikus index megegyezik a csúcsok maximális fokával egy bipartit gráfban, úgy értelmezhető, hogy egy bipartit gráf vonalgráfja tökéletes.

Mivel a kétrészes gráfok vonalgráfjai tökéletesek, a kétrészes gráfok vonalgráfjainak komplementerei is tökéletesek. A G vonalgráf komplementerében lévő klikk egyszerűen G illesztése . A G vonalgráf komplementerének színezése pedig , ha G kétrészes, a G gráf éleinek felosztása olyan élek részhalmazaira, amelyeknek közös csúcsai vannak. Az ezekben a részhalmazokban közös végcsúcsok alkotják a G gráf csúcsborítóját . Így maga König tétele is értelmezhető úgy, hogy a kétrészes gráfok vonalgráfjainak komplementere tökéletes.

Kiegészítések

Azoknál a gráfoknál, amelyek nem kétrészesek, a helyzet a legnagyobb illesztési és a legkisebb csúcsfedési problémákkal egészen más - a legnagyobb illeszkedés polinomiális időben megtalálható bármely gráf esetében, míg a legkisebb csúcsfedő megtalálása NP-teljes probléma . Tetszőleges gráf csúcsfedőjének befejezése független halmaz , a legnagyobb független halmaz megtalálása pedig egy másik NP-teljes probléma.
König tétele egyenértékű a gráfelmélet és a kombinatorika számos minimax-tételével , például Hall esküvőtételével és Dilworth tételével . Mivel a bipartit gráfokban történő illesztés a hálózati áramlás speciális esete, König tétele a Ford-Fulkerson tételből is következik . [nyolc]
Az orosz internetes és tudományos irodalomban általános a tétel következő megfogalmazása: ha egy téglalap alakú mátrix nullákból és egyesekből áll, akkor az összes egyest tartalmazó sorok minimális száma megegyezik az egyesek maximális számával. úgy kell megválasztani, hogy ne legyen kettő egy és ugyanazon a vonalon (a "vonal" kifejezés egy sort vagy egy oszlopot jelent egy mátrixban). [9]

Annak ellenére, hogy a két probléma ekvivalenciája az egzakt megoldás szempontjából, egyáltalán nem ekvivalens a közelítő algoritmusok esetében . A bipartit gráfok legnagyobb illesztési problémája tetszőleges pontossággal közelíthető állandó időben elosztott algoritmusok segítségével , ellentétben a legkisebb csúcsfedő problémával, amelyhez legalább logaritmikus idő szükséges. [tíz]

Jegyzetek

↑ Evnin, 2005 .
↑ Kőnig, 1931 .
↑ Egerváry, 1931 .
↑ 12. Bondy , 1976 , pp. 74-75.
↑ Cesa-Bianchi, Nicolò Matchings és a max-flow min-cut tétel (2020. április 11.). Archiválva az eredetiből 2021. május 9-én. (határozatlan)
↑ Lovas, Plummer, 1998 , p. 567.
↑ Gallai, 1958 .
↑ Lovas, Plummer, 1998 , p. 89.
↑ Rybnikov, 1972 , p. 100.
↑ Göös, 2012 .

Linkek

Lovas L., Plummer M. A gráfelmélet alkalmazott problémái. Matematika, fizika, kémia illesztések elmélete. — M.: Mir, 1998. — 653 p. — ISBN 5-03-002517-0 .
Rybnikov K.A. Bevezetés a kombinatorikus elemzésbe. - Moszkvai Állami Egyetem, 1972.

Evnin A. Yu. Hall-tétel körül // Math. arr .. - 2005. - T. 3 (34) . - S. 2-23 . (Orosz)

Bondy, JA, Murty, USR Graph Theory with Applications. - Észak-Hollandia, 1976. - ISBN 0-444-19451-7 .

Egervary, Jenő. Matrixok kombinatorius tulajdonságairól [On combinatorial properties of matrices] (Hung.) // Matematikai és Fizikai Lapok. - 1931. - 1. évf. 38. - P. 16-28.

Gallai, Tibor. Maximum-minimum Sätze über Graphen // Acta Math. Acad. sci. Hungar.. - 1958. - Vol. 9. - Kérdés. 3-4 . - P. 395-434. - doi : 10.1007/BF02020271 .

Jaj, Mika. Jukka Suomela. 26th International Symposium on Distributed Computing (DISC), Salvador, Brazília, 2012. október - 2012.

Kőnig, Dénes. Gráfok és mátrixok (Hungarian) // Matematikai és Fizikai Lapok. - 1931. - 1. évf. 38. - P. 116-119.