Menger tételei, többszörös összefüggőség
Élösszefüggőség
Egy $G$ gráf $k$-szorosan élösszefüggő, ha bárhogyan hagyunk el belőle $k$-nál kevesebb élt, a maradék gráf összefüggő marad.
Pontösszefüggőség
Egy $G$ gráf $k$-szorosan pontösszefüggő, ha legalább $k+1$ pontja van és bárhogyan hagyunk el belőle $k$-nál kevesebb pontot, a maradék gráf összefüggő marad.
Menger tételei
Egy $G$ irányított gráfban az $u$-ból $v$-be vezető élidegen utak maximális száma megegyezik az $u$-ból $v$-be vezető utakat lefogó élek minimális számával.
Egy $G$ gráfban az $u$-ból $v$-be vezető élidegen utak maximális száma megegyezik az $u$-ból $v$-be vezető utakat lefogó élek minimális számával.
Egy $G$ irányított gráfban $u$ és $v$ legyen két különböző nem szomszédos csúcs. Ekkor az $u$-ból $v$-be vezető pontidegen utak maximális száma megegyezik az $u$-ból $v$-be vezető utakat lefogó ($u$-tól és $v$-től különböző) pontok minimális számával.
Egy $G$ gráfban $u$ és $v$ legyen két különböző nem szomszédos csúcs. Ekkor az $u$-ból $v$-be vezető pontidegen utak maximális száma megegyezik az $u$-ból $v$-be vezető utakat lefogó ($u$-tól és $v$-től különböző) pontok minimális számával.
Mi történik, ha egy 100 pontú teljes gráfból elhagyunk két élt. Hányszorosan élösszefüggő és hányszorosan pontösszefüggő lesz a megmaradó gráf?
a) Itt egy gráf, és próbáljuk meg kideríteni, hogy hány élidegen út vezet $u$ és $v$ között.
b) Egy 100 pontú teljes gráfból elhagyunk 10 élt. Legalább hányszorosan élösszefüggő lesz a megmaradó gráf?
c) Bizonyítsuk be, hogy egy háromszorosan élösszefüggő gráfban mindig van páros hosszú kör.
Vannak olyan hálózatok, amelyek egy kicsit ellenállóbbak a terrorista akciókkal szemben.
Nézzük például ezt.
Ha egy élt felrobbantunk, nem történik semmi.
Ha felrobbantunk még egyet…
A gráf még mindig összefüggő marad.
Na persze ez attól is függ, hogy melyik két élt robbantjuk föl.
Hogyha mondjuk ezt a két élt hagyjuk el…
Akkor a gráf szétesik.
Egyetlen élt még bárhonnan elhagyhatunk, a gráf biztosan összefüggő marad.
De kettőt már nem.
A gráfnak ezt a tulajdonságát élösszefüggőségnek nevezzük.
Egy G gráf k-szorosan élösszefüggő, ha bárhogyan hagyunk el belőle k-nál kevesebb élt, a maradék gráf összefüggő marad.
Ez a gráf kétszeresen élösszefüggő.
Mert egy élt még bárhonnan elhagyhatunk, de a másodiknál már adódhatnak problémák.
A terroristák kézikönyvének második leckéje az, hogy pontokat is föl lehet robbantani.
Egy G gráf k-szorosan pontösszefüggő, ha legalább k+1 pontja van és bárhogyan hagyunk el belőle k-nál kevesebb pontot, a maradék gráf összefüggő marad.
Kezdjünk el robbantgatni…
Három csúcs felrobbantásával már elég nagy károkat lehet okozni.
De ahhoz, hogy kettévágjuk a gráfot…
Két csúcs felrobbantása is elég.
Egyetlen pont elhagyásával viszont a gráf mindig összefüggő marad.
Ez egy kétszeresen pontösszefüggő gráf.
Most nézzük, mi a helyzet ezzel.
Ez a gráf egy fa.
Ha valaki már kertészkedett életében, akkor tudja, hogy a fák mindig egyszeresen élösszefüggők.
Amikor elvágunk egy ágat…
ezzel a fát mindig két komponensre osztjuk.
És bizony ez a művelet az egyik komponens számára végzetes.
De ennyit a kertészkedésről.
A fák egyszeresen pontösszefüggők is.
És ha valakit esetleg ez a feltétel nem hagyott eddig nyugodni…
Akkor nézzük, hogy mi a szerepe.
Bárhogyan hagyunk el ebben a gráfban 2-nél kevesebb pontot, a maradék gráf összefüggő lesz.
Tehát a feltétel nélkül ez a gráf kétszeresen pontösszefüggőnek számítana.
És, hát ez azért mégiscsak túlzás lenne.
Na, erre való ez a feltétel.
Vizsgáljuk meg a teljes gráfokat, és derítsük ki, hogy hányszorosan összefüggők.
A kétpontú teljes gráf egy fa.
Egyszeresen élösszefüggő és egyszeresen pontösszefüggő.
Itt jön aztán K3.
Bármelyik élt hagyjuk el, a gráf összefüggő marad.
Ha viszont két élt hagyunk el, akkor már szétesik.
Ez a gráf kétszeresen élösszefüggő.
Ha egy pontját elhagyjuk, a maradék gráf továbbra is összefüggő.
Sőt, ha még egy pontot elhagyunk, akkor is.
Ezek alapján K3 még akár háromszorosan pontösszefüggő is lehetne.
De az extra feltétel közbeszól...
Maradunk a kettőnél.
Nézzük K4-et.
Egy élt bátran felrobbanthatunk.
Sőt kettőt is.
Ahhoz, hogy egy csúcsot elszakítsunk a kis társaitól, legalább 3 élt kell felrobbantani.
Minden csúcs foka 3, ezért a gráf háromszorosan élösszefüggő.
És egyébként háromszorosan pontösszefüggő is.
Lássuk aztán, hogy mi a helyzet K5-tel.
Itt minden csúcs foka 4.
Ez a gráf négyszeresen élösszefüggő.
És négyszeresen pontösszefüggő is.
A Kn teljes gráf mindig n-szeresen élösszefüggő és n-szeresen pontösszefüggő.
Nézzük aztán, hogy mi történik, ha egy 100 pontú teljes gráfból elhagyunk két élt. Hányszorosan élösszefüggő és hányszorosan pontösszefüggő lesz a megmaradó gráf?
Hát, mind a 100 csúcsot most nem fogjuk lerajzolni…
Egy ilyen kis ábra éppen jó is lesz.
Kezdjük az élösszefüggéssel.
Hogyha a két törölt él ugyanabból a csúcsból indul…
Akkor az ebbe a csúcsba vezető további 97 él törlésével a csúcsot izolálni tudjuk.
De 96 darab élt törölve, a gráf még összefüggő marad.
A gráf ilyenkor 97-szeresen élösszefüggő.
Hogyha a két törölt él nem ugyanabból a csúcsból indul…
Akkor van négy 98 fokú csúcs.
A gráfból 97 élt bárhogyan elhagyhatunk, az összefüggő marad.
De 98 élt már tudunk úgy törölni, hogy a gráf szétessen.
A gráf ilyenkor 98-szorosan élösszefüggő.
Most nézzük a pontösszefüggést.
Kezdjük megint azzal az esettel,
amikor a két törölt él ugyanabból a csúcsból indul…
Hogyha a három érintett csúcson kívül a többi 97 darab csúcsot töröljük…
Akkor a gráf két részre esik szét.
De ha eggyel kevesebb csúcsot törlünk, akkor az így megmaradó negyedik csúcs mindhárom csúccsal össze lenne kötve.
Vagyis 96 csúcsot törölve a gráf még összefüggő maradna.
Ebben az esetben a jelek szerint 97-szeresen csúcsösszefüggő a gráf.
De az izgalmak csak most jönnek…
Most nézzük, mi van akkor, ha a két törölt él nem ugyanabból a csúcsból indul…
A 4 érintett csúcson kívül töröljük ki az összes többit.
Ilyenkor a gráf két részre esik szét.
Ha eggyel kevesebb csúcsot törlünk, akkor az így megmaradó csúcs mind a 4 csúccsal össze lenne kötve.
Vagyis 95 csúcsot törölve a gráf még összefüggő maradna.
Ebben az esetben tehát 96-szorosan csúcsösszefüggő a gráf.
Van itt ez a gráf, és vegyünk benne két különböző pontot.
Vegyük mondjuk ezt a kettőt.
A két pont között vezet egy út itt felül…
és vezet egy másik út ott alul is.
Ezek az u és v közötti utak egymástól élidegenek, vagy másként fogalmazva éldiszjunktak.
Ez azt jelenti, hogy a két útnak nincsen közös éle.
Hogyha ezt az élt baleset érné…
akkor errefelé tudunk kerülni.
Az nem jelent gondot, hogy a két útnak így már van közös belső pontja.
Ettől még továbbra is élidegenek.
Van itt ez a gráf, és vegyünk benne két különböző pontot.
Vegyük mondjuk ezt a kettőt.
A két pont között vezet egy út itt felül…
és vezet egy másik út ott alul is.
Ezek az u és v közötti utak egymástól élidegenek, vagy másként fogalmazva éldiszjunktak.
Ez azt jelenti, hogy a két útnak nincsen közös éle.
Hogyha ezt az élt baleset érné…
akkor errefelé tudunk kerülni.
Az nem jelent gondot, hogy a két útnak így már van közös belső pontja.
Ettől még továbbra is élidegenek.
Vannak aztán olyan élek is, ahol nincs lehetőség kerülőre.
Hogyha ezeket az éleket érné baleset…
Akkor volt-nincs összeköttetés u és v között.
Egy G gráfban az éleknek egy R halmaza lefogja az u és v pontok közti utakat, ha R elhagyása után már nincs út u és v között.
Ez az élhalmaz például lefogja az u és v pontok közti utakat.
És ez is.
De ez nem.
Ha felrobbantjuk őket…
még mindig van út u és v között.
Vannak aztán pontdiszjunkt, vagy másként fogalmazva pontidegen utak is.
Ez a felső…
és ez az alsó két pontidegen út.
Két út akkor pontidegen, ha a kezdő és a végpontjuk kivételével nincs közös pontjuk.
Ezek az utak például élidegenek, de nem pontidegenek.
Egy G gráfban a csúcsoknak egy T halmaza lefogja az u és v pontok közti utakat, ha T elhagyása után már nincs út u és v között.
Ez a két pont például lefogja az u és v közti utakat.
Itt jön most egy másik gráf.
És próbáljuk meg kideríteni, hogy hány élidegen út vezet u és v között.
A jelek szerint 4 ilyen út van.
Ez nem kizárólag a véletlen műve.
Ha egy gráf k-szorosan élösszefüggő, bármely két pontja között létezik k darab páronként élidegen út.
Ez a gráf 4-szeresen élösszefüggő, így hát 4 ilyen út van.
A dolog fordítva is igaz. Ha egy gráfban bármely két pont között létezik k darab páronként élidegen út, akkor a gráf k-szorosan élösszefüggő.
G bármely két pontja között létezik k darab páronként élidegen út.
Egy G gráfban az éleknek egy R halmaza (a csúcsoknak egy T halmaza) lefogja az u és v pontok közti utakat, ha R (T) elhagyása után már nincs út u és v között.
Ugyanez működi a pontokra is…
G-nek legalább k+1 pontja van, és bármely két pontja között létezik k darab páronként pontidegen út.
Egy 100 pontú teljes gráfból elhagyunk 10 élt. Legalább hányszorosan élösszefüggő lesz a megmaradó gráf?
Kezdjük azzal, hogy teljes gráfban két pont között hány darab pontidegen út vezet.
Nézzük először K5-öt.
Van egy közvetlen út…
És bármely u-tól és v-től különböző csúcson keresztül vezet egy kétélű út.
Három ilyen csúcs van…
így hát 3 ilyen út lesz.
Most nézzük, mi van K8-ban.
Itt is van egy közvetlen út…
És minden u-tól és v-től különböző csúcson keresztül vezet egy kétélű út.
Itt a K8-ban 6 darab ilyen csúcs van, tehát 6 darab kétélű út lesz.
És K100-ban pedig 100-2=98 darab ilyen út létezik.
Plusz egy, a közvetlen.
Ha 10 élt hagyunk el K100-ból, az legrosszabb esetben 10 utat tud elrontani a 98 + 1 darab út közül.
Tehát marad, lássuk csak 99 – 10 = 89 darab út.
Ennyi pontidegen út biztosan van.
A gráf tehát legalább 89-szeresen élösszefüggő.
Bizonyítsuk be, hogy egy háromszorosan élösszefüggő gráfban mindig van páros hosszú kör.
Hogyha egy gráf háromszorosan élösszefüggő, akkor bármely két pontja között létezik 3 különböző páronként élidegen út.
Ha van köztük két páros hosszú út, akkor az egyesítésük egy páros kör.
Ha nincs két páros hosszú út, akkor kell lennie két páratlan hosszú útnak.
És ezek egyesítése is egy páros kör.
Ezzel igazoltuk, hogy mindenképpen van a gráfban páros kör.
Sőt, a gráf bármely pontján át vezet páros kör.
Az u és v pontok közti utak kérdése még az eddigieknél is izgalmasabbá válik akkor, hogyha a gráf irányított.
Ilyenkor ugyanis az u-ból v-be vezető utak…
különböznek a v-ből u-ba vezető utaktól.
Így aztán az u-ból v-be vezető utakat lefogó élhalmaz…
nem esik egybe a v-ből u-ba vezető utak lefogó élhalmazával.
Egy G irányított gráfban az éleknek egy R halmaza lefogja az u-ból v-be vezető utakat, ha R elhagyása után már nincs út u-ból v-be.
Egy G irányított gráfban az éleknek egy R halmaza lefogja az v-ből u-ba vezető utakat, ha R elhagyása után már nincs út v-ből u-ba.
Ugyanez a helyzet a lefogó ponthalmazokkal is.
Egy G irányított gráfban a csúcsoknak egy T halmaza lefogja u-ból v-be vezető utakat, ha R elhagyása után már nincs út u-ból v-be.
Egy G irányított gráfban a csúcsoknak egy T halmaza lefogja v-ből u-ba vezető utakat, ha R elhagyása után már nincs út v-ből u-ba.
u-ból v-be két élidegen út vezet.
Az egyik ez a sárga…
A másik pedig a piros.
Az u-ból v-be vezető élidegen utak maximális száma tehát 2.
Éppen annyi, mint az u-ból v-be vezető utakat fogó élek minimális száma.
Ez az egybeesés nem kizárólag a véletlen műve.
Ezt mondja ki Menger első tétele.
Egy G irányított gráfban az u-ból v-be vezető élidegen utak maximális száma megegyezik az u-ból v-be vezető utakat lefogó élek minimális számával.
Mengernek még több hasonlóan izgalmas tétele is van.
Egy G irányított gráfban az éleknek egy R halmaza (a csúcsoknak egy T halmaza) lefogja az u-ból v-be vezető utakat, ha R (T) elhagyása után már nincs út u-ból v-be.
MENGER TÉTELEI
Ugyanennek a tételnek létezik egy irányítatlan gráfokra vonatkozó változata is.
Egy G gráfban az u-ból v-be vezető élidegen utak maximális száma megegyezik az u-ból v-be vezető utakat lefogó élek minimális számával.
Mivel a gráf irányítatlan, ezért létezik itt még egy harmadik élidegen út is u-ból v-be.
És a minimális számú lefogó élhalmaz is 3 elemű.
Most lássuk, mi a helyzet a pontidegen utakkal.
Kezdjük megint az irányított gráfos esettel.
Egy G irányított gráfban u és v legyen két különböző nem szomszédos csúcs. Ekkor az u-ból v-be vezető pontidegen utak maximális száma megegyezik az u-ból v-be vezető utakat lefogó (u-tól és v-től különböző ) pontok minimális számával.
Csak úgy a kíváncsiság kedvéért nézzük meg, hogy mi van akkor, ha u és v szomszédos.
Ennek a tételnek is létezik egy irányítatlan gráfokra vonatkozó változata:
Egy G gráfban u és v legyen két különböző nem szomszédos csúcs. Ekkor az u-ból v-be vezető pontidegen utak maximális száma megegyezik az u-ból v-be vezető utakat lefogó (u-tól és v-től különböző) pontok minimális számával.
Mivel a gráf irányítatlan, ezért van még egy harmadik pontidegen út is u-ból v-be.
És a minimális számú lefogó ponthalmaz is 3 elemű.
Hát ezek itt Menger tételei.
Összesen 4 darab van belőlük.
Kettő foglalkozik az élidegen utakkal…
kettő pedig a pontidegen utakkal.
