Barion Pixel Élfüggetlen és pontfüggetlen utak | mateking
 

Számítástudomány epizód tartalma:

Itt szuper-érthetően elmeséljük, mit jelent az, hogy két út élfüggetlen vagy éppen pontfüggetlen. Megnézzük mik azok a lefogó élhalmazok és lefogó ponthalmazok. És az is kiderül, hogy mi az összefüggés az élfüggetlen utak száma és a k-szoros élösszefüggőség között, valamint a pontfüggetlen utak száma és a k-szoros pontösszefüggőség között.

A képsor tartalma

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.

Egy lépésre vagy attól, hogy a matek melléd álljon és ne eléd.
  • Konkrétan a hetedikes öcsém megtanult deriválni, ez elég bizonyíték, hogy az oldal érthetően magyaráz.

    Gábor, 18
  • Jó árban van és hihetetlenül világos a magyarázat és annyiszor lehet visszatérni az egyes lépésekre, ahányszor arra csak szükség van a megértéshez.

    Lili, 22
  • Olyan weboldal, ami még egy vak lovat is megtanítana integrálni.

    Petra, 26
  • Sokkal jobb, mint bármelyik egyetemi előadásom.

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