Menger-tétel

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

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

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

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

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

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

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

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 $G^{\prime }$. Alkalmazzuk az él-összefüggőségi változatot $G^{\prime }$ gráfra. Tekintsünk egy minimális lefogó élhalmazt. Az $u^{″}-v^{\prime }$ élek helyett tekinthetjük a $v^{\prime }-v^{″}$ éleket. Így nem növeljük a lefogó élek számát. Ekkor a $G^{\prime }$ gráfban a minimális lefogó élhalmaz megfeleltethető a $G$ gráfban egy minimális lefogó csúcshalmazzal. Így ez a megfeleltetés bizonyítja a tételt.

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

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

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 $G^{\prime }$. Legyen $G$-ben a lefogó élek minimális száma $k$. $G^{\prime }$-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.

Nézzünk egy maximális irányított éldiszjunkt élhalmazt $G^{\prime }$-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 $G^{\prime }$-beli éldiszjunkt utak megfeleljenek $G$-beli éldiszjunkt utaknak. Erre a $G^{\prime }$ gráfra alkalmazzuk az irányított gráfokról szóló tételt, így megkapjuk az állítás bizonyítását.

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

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

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^{\prime }$ gráfra az irányított, csúcsösszefüggőségi tételt.

Általánosítások

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

• Katona Gyula Y., Recski András, Szabó Csaba: A számítástudomány alapjai, Typotex, Budapest, 2002, 69-70. old.
• Menger's Theorems and Max-Flow-Min-Cut
• Connectivity and the theorems of Menger

• Sablon:Cite journal

• Sablon:Cite journal

Lásd még

• Maximális folyam – minimális vágás
• Gráfelméleti fogalomtár
• Erdős Pál