21-07-2023
В теории графов и связанных с ней областях математики теорема Менгера — основной результат о связности в конечном неориентированном графе. Сформулирована и доказана в 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-соединимы. |
| Это заготовка статьи по математике. Вы можете помочь проекту, исправив и дополнив её. |
Теорема Менгера.