Участник:Savelin
Необходимые определения
Рассмотрим связный неориентированный взвешенный граф , где — множество вершин, — множество ребер. Вес ребра определяется, как функция .
Определение: |
Минимальное остовное дерево (англ. minimum spanning tree) графа | — это его ациклический связный подграф, в который входят все его вершины, обладающий минимальным суммарным весом ребер.
Заметим, что граф может содержать несколько минимальных остовных деревьев. Для формулировки и доказательства леммы о безопасном ребре рассмотрим следующие определения.
Определение: |
Пусть Ребро называется безопасным, если при добавлении его в , также является подграфом некоторого минимального остовного дерева графа .Разрезом неориентированного графа Ребро (англ. cut) называется разбиение на два непересекающихся подмножества: и . Обозначается как . пересекает разрез , если один из его концов принадлежит множеству , а другой — множеству . | — подграф некоторого минимального остовного дерева графа .
Лемма о безопасном ребре
Теорема: |
Рассмотрим связный неориентированный взвешенный граф с весовой функцией . Пусть — подграф некоторого минимального остовного дерева , — разрез , такой, что ни одно ребро из не пересекает разрез, а — ребро минимального веса среди всех ребер, пересекающих разрез . Тогда ребро является безопасным для . |
Доказательство: |
Достроим до некоторого минимального остовного дерева, обозначим его . Если ребро , то лемма доказана, поэтому рассмотрим случай, когда ребро . Рассмотрим путь в от вершины до вершины . Так как эти вершины принадлежат разным долям разреза, то хотя бы одно ребро пути пересекает разрез, назовем его . По условию леммы . Заменим ребро в на ребро . Полученное дерево также является минимальным остовным деревом графа , поскольку все вершины по-прежнему связаны и вес дерева не увеличился. Следовательно можно дополнить до минимального остовного дерева в графе , то есть ребро — безопасное. |
Cм. также
Источники информации
- Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. — Алгоритмы. Построение и анализ.