Mengerin lause

Mengerin lause  on perustulos yhteyteen äärellisessä suuntaamattomassa graafissa , joka liittyy läheisesti Ford-Fulkersonin lauseeseen . Muotoiltu ja todistettu vuonna 1927 Carl Menger Jr :n toimesta.

Formulaatiot

Kaksi vastaavaa formulaatiota:

• Olkoon G  äärellinen suuntaamaton graafi ja x , y  kaksi erillistä kärkeä. Pienin määrä pisteitä, jotka erottavat x :n ja y :n, on yhtä suuri kuin suurin määrä pareittain riippumattomia ( x , y )-polkuja. [yksi]

• Olkoon G  äärellinen suuntaamaton graafi ja x , y  kaksi erillistä kärkeä. x ja y ovat k -erotettavissa silloin ja vain, jos x ja y ovat k -liitettävissä.

• Olkoon G  äärellinen suuntaamaton graafi ja x , y  erillisiä pisteitä. x ja y ovat k - reuna -erotettavissa silloin ja vain jos x ja y ovat k - reuna -liitettävissä.

Muistiinpanot

1. ↑ Harari F. Graafiteoria M., 2003