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 | forrásszöveg szerkesztése]

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

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 | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

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 minimá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 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 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 lehet 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 | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

Mengerk irtt cs.png

A G 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 \scriptstyle{G'}. Alkalmazzuk az él-összefüggőségi változatot \scriptstyle{G'} gráfra. Tekintsünk egy minimális lefogó élhalmazt. Az u''-v' élek helyett tekinthetjük a v'-v'' éleket. Így nem növeljük a lefogó élek számát. Ekkor a \scriptstyle{G'} gráfban a minimális lefogó élhalmaz megfeleltethető a G 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 | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

Az látszik, hogy a lefogó élek minimális száma legalább annyi, mint az éldiszjunkt utak száma, mert k darab éldiszjunkt út lefogásához kell k 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 \scriptstyle{G'}. Legyen G-ben a lefogó élek minimális száma k. \scriptstyle{G'}-ben a lefogó pontok száma legalább k, mivel ha k-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 G-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 \scriptstyle{G'}-ben. Ezeknek a utaknak a megfelelői G-ben nem feltétlenül éldiszjunktak. Alakítsuk át az utakat úgy, hogy azok G-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 G-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 \scriptstyle{G'}-beli éldiszjunkt utak megfeleljenek G-beli éldiszjunkt utaknak. Erre a \scriptstyle{G'} 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 | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

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 G' gráfra az irányított, csúcsösszefüggőségi tételt.

Általánosítások[szerkesztés | forrásszöveg szerkesztése]

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 van a-t és b-t összekötő utak egy F rendszere és a-t és b-t elválasztó pontok egy 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 | forrásszöveg szerkesztése]

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

Lásd még[szerkesztés | forrásszöveg szerkesztése]