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.