1 added
1 removed
Original
2026-01-01
Modified
2026-02-26
1
<p>В этом уроке мы разберем знаменитую в теории графов теорему Менгера, которая помогает перекрыть путь от одной вершины к другой.</p>
1
<p>В этом уроке мы разберем знаменитую в теории графов теорему Менгера, которая помогает перекрыть путь от одной вершины к другой.</p>
2
<h2>Теорема Менгера</h2>
2
<h2>Теорема Менгера</h2>
3
<p>Прежде чем разобраться с теоремой Менгера, представим, что нам даны две вершины в графе. Мы хотим узнать, сколько вершин нужно удалить, чтобы разделить эти две вершины - сделать невозможным переход от одной к другой. Например, в приведенном ниже графе нам нужно удалить три вершины, чтобы сделать невозможным переход от s к t:</p>
3
<p>Прежде чем разобраться с теоремой Менгера, представим, что нам даны две вершины в графе. Мы хотим узнать, сколько вершин нужно удалить, чтобы разделить эти две вершины - сделать невозможным переход от одной к другой. Например, в приведенном ниже графе нам нужно удалить три вершины, чтобы сделать невозможным переход от s к t:</p>
4
<p>Еще нас интересует, сколько существует маршрутов из s в t, у которых нет общих вершин кроме самих s и t. В приведенном выше графе существует множество маршрутов из s в t. Мы можем найти три маршрута, у которых нет общих вершин. Мы можем пройти через вершину, низ или середину.</p>
4
<p>Еще нас интересует, сколько существует маршрутов из s в t, у которых нет общих вершин кроме самих s и t. В приведенном выше графе существует множество маршрутов из s в t. Мы можем найти три маршрута, у которых нет общих вершин. Мы можем пройти через вершину, низ или середину.</p>
5
<p>Число три совпадает с количеством вершин, которые нужно удалить, чтобы отделить s от t. Это не совпадение, а пример теоремы Менгера.</p>
5
<p>Число три совпадает с количеством вершин, которые нужно удалить, чтобы отделить s от t. Это не совпадение, а пример теоремы Менгера.</p>
6
<p>Теорема Менгера: пусть s и t - несмежные вершины в некотором графе. Минимальное число вершин, которые нужно удалить из графа, чтобы из s в t было невозможно попасть, равно максимальному числу путей из s в t, не имеющих общих вершин, кроме s и t.</p>
6
<p>Теорема Менгера: пусть s и t - несмежные вершины в некотором графе. Минимальное число вершин, которые нужно удалить из графа, чтобы из s в t было невозможно попасть, равно максимальному числу путей из s в t, не имеющих общих вершин, кроме s и t.</p>
7
<p>Если у нас есть набор вершин, которые отделяют s от t, то этот набор должен содержать вершину каждого пути между s и t. А если мы рассматриваем непересекающиеся пути от s к t, то никакая вершина не может удалить два пути одновременно. Получается, что минимальное количество вершин, которое необходимо для отделения s от t такое же, как и максимальное количество непересекающихся путей от s к t. Довольно сложно пойти в другом направлении и показать, что оно не больше.</p>
7
<p>Если у нас есть набор вершин, которые отделяют s от t, то этот набор должен содержать вершину каждого пути между s и t. А если мы рассматриваем непересекающиеся пути от s к t, то никакая вершина не может удалить два пути одновременно. Получается, что минимальное количество вершин, которое необходимо для отделения s от t такое же, как и максимальное количество непересекающихся путей от s к t. Довольно сложно пойти в другом направлении и показать, что оно не больше.</p>
8
<p>Это еще одна теорема, подобная теореме Кенига-Эгервари, где минимизация одной величины дает ответ на максимум другой. В теореме Кенига-Эгервари речь шла о том, что минимальное вершинное покрытие приводит к максимальному соответствию того же размера.</p>
8
<p>Это еще одна теорема, подобная теореме Кенига-Эгервари, где минимизация одной величины дает ответ на максимум другой. В теореме Кенига-Эгервари речь шла о том, что минимальное вершинное покрытие приводит к максимальному соответствию того же размера.</p>
9
<p>Здесь у минимального разделяющего множества вершин тот же размер, что и максимальное число вершинно-разделительных путей. Теорему Кенига-Эгервари можно использовать, чтобы доказать теорему Менгера и наоборот. Эти теоремы в некотором смысле эквивалентны.</p>
9
<p>Здесь у минимального разделяющего множества вершин тот же размер, что и максимальное число вершинно-разделительных путей. Теорему Кенига-Эгервари можно использовать, чтобы доказать теорему Менгера и наоборот. Эти теоремы в некотором смысле эквивалентны.</p>
10
<p>Существует также краевая версия теоремы Менгера. Она формулируется так:</p>
10
<p>Существует также краевая версия теоремы Менгера. Она формулируется так:</p>
11
-
<p>Максимальное количество путей между s и t равно минимальное количество ребер, которые нужно удалить, чтобы отделить s от t. При этом у s и t нет общих ребер</p>
11
+
<p>Максимальное количество путей между s и t равно минимальному количеству ребер, которые нужно удалить, чтобы отделить s от t. При этом у s и t нет общих ребер</p>
12
<p>Теорема Менгера приводит к следующей характеристике связности:</p>
12
<p>Теорема Менгера приводит к следующей характеристике связности:</p>
13
<p>Граф будет k-связным тогда и только тогда, когда между любой парой вершин есть не менее k путей, у которых нет общих вершин, кроме своих конечных точек</p>
13
<p>Граф будет k-связным тогда и только тогда, когда между любой парой вершин есть не менее k путей, у которых нет общих вершин, кроме своих конечных точек</p>
14
<h2>Выводы</h2>
14
<h2>Выводы</h2>
15
<p>В этом уроке мы познакомились с теоремой Менгера. Теперь вы умеете вычислять, сколько вершин нужно удалить, чтобы разделить две вершины. Так вы сможете упрощать и ускорять свою работу с графами, разделяя большие и сложные графы на отдельные подграфы.</p>
15
<p>В этом уроке мы познакомились с теоремой Менгера. Теперь вы умеете вычислять, сколько вершин нужно удалить, чтобы разделить две вершины. Так вы сможете упрощать и ускорять свою работу с графами, разделяя большие и сложные графы на отдельные подграфы.</p>