Menger tétele

Menger tétele  egy véges irányítatlan gráf összekapcsoltságának alapvető eredménye, amely szorosan kapcsolódik a Ford-Fulkerson tételhez . 1927 -ben fogalmazta meg és bizonyította Carl Menger Jr.

Formulációk

Két egyenértékű készítmény:

• Legyen G  véges irányítatlan gráf és x , y  pedig két nem szomszédos csúcs. Az x -et és y -t elválasztó csúcsok legkisebb száma egyenlő a páronkénti független ( x , y )-útvonalak legnagyobb számával. [egy]

• Legyen G  véges irányítatlan gráf és x , y  pedig két nem szomszédos csúcs. x és y akkor és csak akkor k -elválasztható, ha x és y k -összekapcsolható.

• Legyen G  véges irányítatlan gráf és x , y  különálló csúcsok. x és y akkor és csak akkor k - él - elválasztható, ha x és y k - él - összekapcsolható.

Jegyzetek

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