Теорема Менгера

Теорема Менгера — основной результат о связности в конечном неориентированном графе, тесно связанный с теоремой Форда — Фалкерсона. Сформулирована и доказана в 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-соединимы.

Примечания
  1. Харари Ф. Теория графов М.,2003
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.