Diszkrét matematika epizód tartalma:

Itt jönnek Menger tételei, lépésről-lépésre elmeséljük, hogy pontosan mik is ezek a tételek, mi a kapcsolat az élfüggetlen utak száma és az utakat lefogó élhalmaz elemszáma között, valamint a pontfüggetlen utak száma és az ezeket az utakat lefogó ponthalmazok elemszáma között. Remek szórakozás lesz...

A képsor tartalma

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.

Hopsz, úgy tűnik nem vagy belépve, pedig itt olyan érdekes dolgokat találsz, mint például:

Itt jönnek Menger tételei, lépésről-lépésre elmeséljük, hogy pontosan mik is ezek a tételek, mi a kapcsolat az élfüggetlen utak száma és az utakat lefogó élhalmaz elemszáma között, valamint a pontfüggetlen utak száma és az ezeket az utakat lefogó ponthalmazok elemszáma között. Remek szórakozás lesz...

Végül is miért ne néznél meg
még egy epizódot?
Ugrás az
összeshez
Hurrá, itt már nincs következő!