Теорема Менгера | это... Что такое Теорема Менгера? (original) (raw)

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