Barion Pixel k-szorosan útösszefüggő és pontösszefüggő gráfok | mateking
 

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ő.

A képsor tartalma

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.

BelépekvagyRegisztrálok Back arrow Ugrás az
összeshez