Теорема Менгера — основной результат о связности в конечном неориентированном графе , тесно связанный с теоремой Форда — Фалкерсона . Сформулирована и доказана в 1927 году Карлом Менгером (мл.) .

Формулировки

Теорема Менгера о вершинной связности ;

Две эквивалентные формулировки:

• Пусть G — конечный неориентированный граф и x , y — две несмежные вершины. Наименьшее число вершин, разделяющих x и y , равно наибольшему числу попарно независимых ( x , y )-цепей.

• Пусть G — конечный неориентированный граф и x , y — две несмежные вершины. x и y k -отделимы тогда и только тогда, когда x и y k -соединимы.

Теорема Менгера о реберной связности

• Пусть G — конечный неориентированный граф и x , y — различные вершины. x и y реберно k -отделимы тогда и только тогда, когда x и y реберно k -соединимы.

Примечания

Это заготовка статьи по математике . Помогите Википедии, дополнив её.