Главная » 2017 » Октябрь » 31 » Теорема Менгера
03:50
Теорема Менгера
[править | править вики-текст]
Материал из Википедии — свободной энциклопедии


Перейти к: навигация, поиск

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

Примечания[править | править вики-текст]

↑ Харари Ф. Теория графов М.,2003

Для улучшения этой статьи желательно:

Найти и оформить в виде сносок ссылки на независимые авторитетные источники, подтверждающие написанное.
Добавить иллюстрации.

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


Источник — «https://ru.wikipedia.org/w/index.php?title=Теорема_Менгера&oldid=83962233»
Категория: Теоремы теории графовСкрытые категории: Википедия:Статьи без ссылок на источникиВикипедия:Статьи без источников (тип: теорема)Википедия:Статьи без изображений (тип: теорема)Незавершённые статьи по математике
Просмотров: 171 | Добавил: nataliya_igorevna_1969 | Рейтинг: 0.0/0
Всего комментариев: 0
avatar