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 ${\displaystyle 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 ${\displaystyle \scriptstyle {G'}}$. Alkalmazzuk az él-összefüggőségi változatot ${\displaystyle \scriptstyle {G'}}$ gráfra. Tekintsünk egy minimális lefogó élhalmazt. Az ${\displaystyle u''-v'}$ élek helyett tekinthetjük a ${\displaystyle v'-v''}$ éleket. Így nem növeljük a lefogó élek számát. Ekkor a ${\displaystyle \scriptstyle {G'}}$ gráfban a minimális lefogó élhalmaz megfeleltethető a ${\displaystyle 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 ${\displaystyle k}$ darab éldiszjunkt út lefogásához kell ${\displaystyle 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 ${\displaystyle \scriptstyle {G'}}$. Legyen ${\displaystyle G}$-ben a lefogó élek minimális száma ${\displaystyle k}$. ${\displaystyle \scriptstyle {G'}}$-ben a lefogó pontok száma legalább ${\displaystyle k}$, mivel ha ${\displaystyle 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 ${\displaystyle G}$-ben.

Nézzünk egy maximális irányított éldiszjunkt élhalmazt ${\displaystyle \scriptstyle {G'}}$-ben. Ezeknek a utaknak a megfelelői ${\displaystyle G}$-ben nem feltétlenül éldiszjunktak. Alakítsuk át az utakat úgy, hogy azok ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle \scriptstyle {G'}}$-beli éldiszjunkt utak megfeleljenek ${\displaystyle G}$-beli éldiszjunkt utaknak. Erre a ${\displaystyle \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.

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 ${\displaystyle G'}$ 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

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

• Aharoni, Ron and Berger, Eli. „Menger's Theorem for infinite graphs”. [2007. február 11-i dátummal az eredetiből archiválva]. (Hozzáférés: 2008. május 10.)  

Lásd még

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