WikiSort.ru - Не сортированное

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

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

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

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

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

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

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

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

Примечания

В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники. Эта отметка установлена 19 июня 2018 года.

Это заготовка статьи по математике. Вы можете помочь проекту, дополнив её.