Menger tételei | mateking
 

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.

Egy lépésre vagy attól, hogy a matek melléd álljon és ne eléd.
  • Ez a legjobban áttekinthető, értelmezhető, használható és a legolcsóbb tanulási lehetőség.

    Eszter, 23
  • Értelmes, szórakoztató, minden pénzt megér.

    Tibor, 23
  • Sokkal jobb, mint bármelyik egyetemi előadásom.

    Dani, 20
  • Felsőbb éves egyetemisták ajánlották, "kötelező" címszóval.
    Ricsi, 19
BelépekvagyRegisztrálok Back arrow Ugrás az
összeshez
Hurrá, itt már nincs következő!