В этом уроке мы разберем знаменитую в теории графов теорему Менгера, которая помогает перекрыть путь от одной вершины к другой.
Теорема Менгера
Прежде чем разобраться с теоремой Менгера, представим, что нам даны две вершины в графе. Мы хотим узнать, сколько вершин нужно удалить, чтобы разделить эти две вершины — сделать невозможным переход от одной к другой. Например, в приведенном ниже графе нам нужно удалить три вершины, чтобы сделать невозможным переход от к :
Еще нас интересует, сколько существует маршрутов из в , у которых нет общих вершин кроме самих и . В приведенном выше графе существует множество маршрутов из в . Мы можем найти три маршрута, у которых нет общих вершин. Мы можем пройти через вершину, низ или середину.
Число три совпадает с количеством вершин, которые нужно удалить, чтобы отделить от . Это не совпадение, а пример теоремы Менгера.
Теорема Менгера: пусть и — несмежные вершины в некотором графе. Минимальное число вершин, которые нужно удалить из графа, чтобы из в было невозможно попасть, равно максимальному числу путей из в , не имеющих общих вершин, кроме и .
Если у нас есть набор вершин, которые отделяют от , то этот набор должен содержать вершину каждого пути между и . А если мы рассматриваем непересекающиеся пути от к , то никакая вершина не может удалить два пути одновременно. Получается, что минимальное количество вершин, которое необходимо для отделения от такое же, как и максимальное количество непересекающихся путей от к . Довольно сложно пойти в другом направлении и показать, что оно не больше.
Это еще одна теорема, подобная теореме Кенига-Эгервари, где минимизация одной величины дает ответ на максимум другой. В теореме Кенига-Эгервари речь шла о том, что минимальное вершинное покрытие приводит к максимальному соответствию того же размера.
Здесь у минимального разделяющего множества вершин тот же размер, что и максимальное число вершинно-разделительных путей. Теорему Кенига-Эгервари можно использовать, чтобы доказать теорему Менгера и наоборот. Эти теоремы в некотором смысле эквивалентны.
Существует также краевая версия теоремы Менгера. Она формулируется так:
Максимальное количество путей между и равно минимальное количество ребер, которые нужно удалить, чтобы отделить от . При этом у и нет общих ребер
Теорема Менгера приводит к следующей характеристике связности:
Граф будет -связным тогда и только тогда, когда между любой парой вершин есть не менее путей, у которых нет общих вершин, кроме своих конечных точек
Выводы
В этом уроке мы познакомились с теоремой Менгера. Теперь вы умеете вычислять, сколько вершин нужно удалить, чтобы разделить две вершины. Так вы сможете упрощать и ускорять свою работу с графами, разделяя большие и сложные графы на отдельные подграфы.
Остались вопросы? Задайте их в разделе «Обсуждение»
Вам ответят команда поддержки Хекслета или другие студенты
Для полного доступа к курсу нужен базовый план
Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.
