Mengerin lause

Wikipedia
Loikkaa: valikkoon, hakuun

Verkkoteoriassa Mengerin lause on äärellisten suuntaamattomien verkkojen yhtenäisyyttä koskeva lause. Lauseen todisti Karl Menger vuonna 1927 ja yleisti lauseen myöhemmin maksimivirtaus minimileikkaus -lauseeksi.

Olkoon G äärellinen suuntaamaton verkko ja x ja y G:n kaksi solmua, joiden välillä ei ole särmää. Tällöin x:n ja y:n minimaalinen särmäleikkaus (minimimäärä särmiä, jotka poistamalla x ja y kuuluvat verkon eri komponentteihin) on yhtä suuri kuin maksimimäärä pareittaisia särmäriippumattomia polkuja x:stä y:hyn.

Tämä matematiikkaan liittyvä artikkeli on tynkä. Voit auttaa Wikipediaa laajentamalla artikkelia.