Презентация на тему "Каркасы минимального веса"

Содержание

• 
  Слайд 1

  Каркасы минимального веса

• 
  Слайд 2

  Подграфы

  Пусть – граф Будем говорить, что граф является подграфом графа , если: При этом будем говорить, что: – подграф, индуцированный множеством вершин , если – частичный граф, если В общем случае , будем говорить, что – фрагмент, или подграф в широком смысле  

• 
  Слайд 3

  Остовные подграфы

  Частичный граф, т.е. подграф , где , также называют остовным подграфом Остовное дерево – это остовный подграф, являющийся деревом, остовный лес – остовный подграф, являющийся лесом, и т.д. Остовные деревья также называют каркасами  

• 
  Слайд 4
  

  Ясно, что, если граф является связным, то у него может существовать более одного каркаса Например, унициклический граф, содержащий цикл длины , имеет различных каркасов (впрочем, возможно, с точностью до изоморфизма их меньше)  

• 
  Слайд 5

  Каркасы минимального веса

  Рассмотрим граф , ребра которого взвешены весовой функцией Пусть – каркас. Определим его вес естественным образом: Нас будет интересовать задача поиска в данном графе каркаса, вес которого минимален В случае существования нескольких каркасов минимального веса, необходимо найти любой из них  

• 
  Слайд 6

  Алгоритмы

  Мы рассмотрим два алгоритма решения задачи Алгоритм Крускала Алгоритм Прима Оба алгоритма относятся к классу жадных алгоритмов

• 
  Слайд 7

  Алгоритм Крускала

  Пусть –связный граф, – весовая функция на ребрах Будем строить каркас минимального веса Начнем с , где Будем повторять следующие шаги Найдем ребро минимального веса, добавление которого в не приводит к образованию цикла Положим Ясно, что алгоритм закончит свою работу и построено будет действительно дерево  

• 
  Слайд 8
  

  Алгоритм Крускала корректен, т.е. он действительно строит каркас минимального веса Предположим, что это не так, т.е. существует каркас такой, что Пусть – ребро минимального веса, вошедшее в и не вошедшее в Пусть также Ясно, что граф не содержит циклов, т.к. это подграф как графа , так и графа  

• 
  Слайд 9
  

  Добавление в граф ребра не приводит к образованию цикла, т.к. получающийся при этом граф является подграфом Значит, ребро могло быть добавлено в граф без образования цикла и при этом имело вес меньший, чем то ребро, что было добавлено алгоритмом Но это противоречит описанию алгоритма: он добавляет в граф ребро минимального веса, добавление которого не приводит к появлению циклов  

• 
  Слайд 10
  

  Алгоритм проще всего реализовать, сначала отсортировав ребра по невозрастанию их весов: Теперь алгоритм реализуется однократным проходом по отсортированному списку ребер Для проверки того, что добавление ребра не приводит к образованию цикла, можно проверить, принадлежат ли эти вершины различным компонентам связности текущего подграфа; это можно сделать, используя лес непересекающихся множеств  

• 
  Слайд 11
  

  Затраты на сортировку множества ребер составят Затраты на осуществление прохода по отсортированному списку ребер при использовании леса непересекающихся множеств составят Таким образом, временная сложность алгоритма Крускала составляет  

• 
  Слайд 12

  Алгоритм Прима

  Рассмотрим иной способ построения каркаса минимального веса Будем строить дерево следующим образом: Изначально , где – произвольная вершина графа Теперь на каждом шаге находим ребро минимального веса в графе , соединяющее вершину, входящую в , с вершиной, в нее не входящей; пусть это ребро Модифицируем граф:  

• 
  Слайд 13
  

  Предположим, что существует каркас , имеющий вес меньший, чем вес каркаса, найденного алгоритмом Прима Рассмотрим первый момент времени, когда в было добавлено ребро, не входящее в . Пусть это было ребро , а – множество вершин графа на тот момент В графе вершины и соединены некоторым путем; пусть - ребро на этом пути, одна из вершин которого принадлежит , а другая нет. Из алгоритма ясно, что , т.к. в случае было бы добавлено ребро , а не  

• 
  Слайд 14
  

  Таким образом, можно рассмотреть новый остовный подграф, содержащий ребро и не содержащий ребра : ; ясно, что он также будет обладать минимальным возможным весом Повторяя эту операцию необходимое число раз, придем к каркасу , чем и докажем, что он является каркасом минимального веса  

• 
  Слайд 15
  

  Для реализации этого алгоритма необходимо организовать хранение множества ребер с возможностью извлекать из него ребро минимального веса, удалять и добавлять ребра Мы будем хранить множество ребер, один конец которых принадлежит текущему множеству вершин, а другой – нет После добавления очередного ребра в граф необходимо удалить это ребро из множества хранимых ребер, но в него необходимо добавить все ребра, смежные с добавленной вершиной, второй конец которых находится вне текущего множества вершин

• 
  Слайд 16
  

  Подходящей структурой является бинарная куча: она позволяет проводить добавлять, удалять элементы и извлекать элемент с минимальным значением ключа за логарифмическое время Каждое ребро будет добавлено или удалено не более одного раза, поэтому общая временная сложность алгоритма составит