Diszkrét matematika epizód tartalma:
Mit jelent az, hogy egy gráf k-szorosan útösszefggő és k-szorosan pontösszefüggő. Na és mire jó ez egyáltalán. Szuper érthető példákon keresztül megnézzük, hogyan lehet egy gráfról kideríteni, hogy hányszorosan élösszefüggő és pontösszefüggő.
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.
Diszkrét matematika epizód.