Teorema lui Menger

Teorema lui Menger  este un rezultat de bază al conexiunii într-un graf finit nedirecționat , strâns legat de teorema Ford-Fulkerson . Formulat și dovedit în 1927 de Carl Menger Jr.

Formulări

Două formulări echivalente:

• Fie G  un graf finit nedirecționat și x , y  două vârfuri neadiacente. Cel mai mic număr de vârfuri care separă x și y este egal cu cel mai mare număr de lanțuri ( x , y ) independente pe perechi . [unu]

• Fie G  un graf finit nedirecționat și x , y  două vârfuri neadiacente. x și y sunt k -separabile dacă și numai dacă x și y sunt k -unibile.

• Fie G  un graf finit nedirecționat și x , y  vârfuri distincte. x și y sunt k - muchie -separabile dacă și numai dacă x și y sunt k - muchie -unibile.

Note

1. ↑ Harari F. Teoria graficelor M., 2003