Mengers teorem

Mengers sats  är ett grundläggande resultat om samband i en finit oriktad graf , nära besläktad med Ford-Fulkersons sats . Formulerad och bevisad 1927 av Carl Menger Jr.

Formuleringar

Två likvärdiga formuleringar:

• Låt G  vara en ändlig oriktad graf och x , y  vara två icke intilliggande hörn. Det minsta antalet hörn som separerar x och y är lika med det största antalet parvis oberoende ( x , y )-kedjor. [ett]

• Låt G  vara en ändlig oriktad graf och x , y  vara två icke intilliggande hörn. x och y är k -separerbara om och endast om x och y är k -sammanfogbara.

• Låt G  vara en finit oriktad graf och x , y  vara distinkta hörn. x och y är k - kant -separerbara om och endast om x och y är k - kant - sammanfogningsbara.

Anteckningar

1. ↑ Harari F. Graph Theory M., 2003