Теорема Менгера
твердження про зв'язність у скінченному неорієнтованому графі
(Перенаправлено з Теорема Менґера)
Теорема Менгера — основний результат про зв'язність у скінченному неорієнтованому графі, тісно пов'язаний із теоремою Форда — Фалкерсона. Сформулював та довів 1927 року Карл Менгер[de] .
ФормулюванняРедагувати
Теорема Менгера про вершинну зв'язністьРедагувати
Два еквівалентні формулювання:
- Нехай 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-реберно-з'єднувані.
ПриміткиРедагувати
- ↑ Харари Ф. Теория графов. — М. : УРСС, 2003. — 300 с. — ISBN 5-354-00301-6.
В іншому мовному розділі є повніша стаття Menger's theorem (англ.). Ви можете допомогти, розширивши поточну статтю за допомоги перекладу з англійської.
|