Menger-tétel

A Wikipédiából, a szabad enciklopédiából

A matematikában, ezen belül a gráfelméletben Menger tétele az egyik legfontosabb eszköz gráfok összefüggőségének vizsgálatához. Karl Menger 1927-ben igazolta.

A tétel[szerkesztés]

Az él-összefüggőségi változat irányított gráfokban[szerkesztés]

Legyenek P és Q egy véges irányított gráf pontjai. Ekkor a P-ből Q-ba vezető éldiszjunkt irányított utak maximális száma megegyezik az összes P-ből Q-ba vezető irányított utat lefogó élek minimális számával.

Példa[szerkesztés]

Menger1 peldaa.png A piros és kék élek a maximális számú éldiszjunkt utakat, a szaggatott P-b és P-a élek a minimális lefogó élhalmazt jelölik.

Bizonyítás[szerkesztés]

Tegyük fel, hogy a G gráfban az éldiszjunkt irányított utak száma k. Az nyilvánvaló, hogy a lefogó élek minimális száma nem kisebb, mint a P-Q irányított utak maximális száma, mert k darab éldiszjunkt utat nem lehet lefogni k-nál kevesebb éllel. Legyen a lefogó élek minimális száma l. Annak a bizonyításához, hogy van legalább l darab éldiszjunkt irányított P-Q út, alkalmazzuk a maximális-folyam-minimális-vágás-tételt a G gráfra úgy, hogy az élek kapacitását válasszuk 1-nek. Mivel az összes P-Q irányított utat lefogó élek száma legalább l, ezért minden vágás értéke is legalább l, így a tétel miatt az élsúlyozott G gráfban a maximális folyam értéke is legalább l, és az egészértékűségi lemma miatt a maximális folyam előáll úgy, hogy az élek folyamértéke 0 vagy 1. Nyilván létezik 1 értékű élekből álló út P-ből Q-ba, mert ha nem létezne, akkor nem lehetne a gráfban a folyamérték l. Az egyik irányított útban szereplő élek kapacitását változtassuk 0-ra. Így a maximális folyamérték G-ben 1-gyel csökken, tehát legalább l-1. Ugyanezt az eljárást még l-1-szer elvégezve, kapunk l darab irányított utat P-ből Q-ba. Így a tételt igazoltuk.

A csúcs-összefüggőségi változat irányított gráfokban[szerkesztés]

Legyenek P és Q egy véges irányított G gráf pontjai úgy, hogy P-ből Q-ba nem vezet él. Ekkor a P-ből Q-ba vezető pontdiszjunkt irányított utak maximális száma megegyezik az összes P-ből Q-ba vezető irányított utat lefogó pontok minimális számával.

Példa[szerkesztés]

Menger pelda1v2.png

A piros és kék élek a maximális számú csúcsdiszjunkt utakat jelöli, a zöld 'a' és 'b' pontok a minimális számú lefogó ponthalmazt.

Bizonyítás[szerkesztés]

Mengerk irtt cs.png

A gráf pontjait húzzuk szét úgy, hogy az egyik pontba bele fussanak, a másikból kifussanak az eredeti élbe be-, illetve kifutó élek. Legyen ez a gráf . Alkalmazzuk az él-összefüggőségi változatot gráfra. Tekintsünk egy minimális lefogó élhalmazt. Az élek helyett tekinthetjük a éleket. Így nem növeljük a lefogó élek számát. Ekkor a gráfban a minimális lefogó élhalmaz megfeleltethető a gráfban egy minimális lefogó élhalmazzal. Így ez a megfeleltetés bizonyítja a tételt.

Az él-összefüggőségi változat irányítatlan gráfokban[szerkesztés]

Ha a véges G gráfban P és Q össze nem kötött csúcsok, akkor az éldiszjunkt P-Q utak maximális száma megegyezik a P és Q közötti minimális vágással, azaz a minimális élszámmal, amelyek elhagyása után már nincs P-ből Q-ba út.

Bizonyítás[szerkesztés]

Az látszik, hogy a lefogó élek minimális száma legalább annyi, mint az éldiszjunkt utak száma, mert darab éldiszjunkt út lefogásához kell darab él. Annak bizonyításhoz az irányítatlan élek helyett tegyünk be egy irányított élpárt oda-vissza a gráfba, legyen ez . Legyen -ben a lefogó élek minimális száma . -ben a lefogó pontok száma legalább , mivel ha -nál kevesebb él lefogná az összes irányított utat, akkor a lefogó élek irányítatlan megfelelői lefognák az irányítatlan utakat -ben. u,v irányítatlan élből oda-vissza irányított él lesz

Nézzünk egy maximális irányított éldiszjunkt élhalmazt -ben. Ezeknek a utaknak a megfelelői -ben nem feltétlenül éldiszjunktak. Alakítsuk át az utakat úgy, hogy azok -beli megfelelői is éldiszjunktak legyenek. Az ábra szerint változtassuk meg a bal oldali ábrán a pirossal jelölt utat a jobb oldali ábrán lévő piros útra, és ugyanezt a kékre. Látszik, hogy ezzel a lépéssel megszűnik egy olyan él, ahol a piros és kék utak -beli megfelelője közös élben találkozik, s közben nem változik az irányított utak száma. Ilyen lépések véges sorozatával elérhető, hogy a -beli éldiszjunkt utak megfeleljenek -beli éldiszjunkt utaknak. Erre a gráfra alkalmazzuk az irányított gráfokról szóló tételt, így megkapjuk az állítás bizonyítását.

Mengerk irtl el2.pngMengerk irtl el3.png

A csúcs-összefüggőségi változat irányítatlan gráfokban[szerkesztés]

Ha egy véges G gráfban P és Q össze nem kötött csúcsok, akkor a csúcsdiszjunkt P-Q utak maximális száma megegyezik a G-ben P-t és Q-t szeparáló csúcsok minimális számával.

Bizonyítás[szerkesztés]

Vezessük vissza a tételt úgy, hogy az irányítatlan élek helyett tegyünk be a gráfba irányított élpárt oda-vissza, mint az irányítatlan, élösszefüggő estben, majd alkalmazzuk erre a gráfra az irányított, csúcsösszefüggőségi tételt.

Általánosítások[szerkesztés]

Az irányított gráfokra vonatkozó él-összefüggőségi változat általánosítása a maximális-folyam-minimális-vágás-tétel, amelyet Lester Randolph Ford és Delbert Ray Fulkerson algoritmusa bizonyít, így a Menger-tétel bizonyításához felhasználható az előbbi tétel.

Végtelen gráfokra a problémát Erdős Pál vetette fel. Az általánosított Menger-sejtés állítja, hogy ha egy végtelen gráfban a és b nem szomszédos csúcsok, akkor létezik a-t és b-t összekötő utak olyan F rendszere és a-t és b-t elválasztó pontok S halmaza, hogy S minden pontja pontosan egy F-beli útra illeszkedik, és minden F-beli út pontosan egy F-beli pontot tartalmaz.

Források[szerkesztés]

  • Menger, Karl (1927.). „Zur allgemeinen Kurventhoerie”. Fund. Math. 10, 96-115. o.  

Lásd még[szerkesztés]