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

Включить эффекты
1 из 16
Смотреть похожие
Ваша оценка презентации
Оцените презентацию по шкале от 1 до 5 баллов
  • 1
  • 2
  • 3
  • 4
  • 5
0.0
0 оценок

Рецензии

Добавить свою рецензию

Аннотация к презентации

Посмотреть и скачать бесплатно презентацию по теме "Каркасы минимального веса". pptCloud.ru — каталог презентаций для детей, школьников (уроков) и студентов.

  • Формат
    pptx (powerpoint)
  • Количество слайдов
    16
  • Слова
    другое
  • Конспект
    Отсутствует

Содержание

  • Каркасы минимального веса
    Слайд 1

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

  • Слайд 2

    Подграфы

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

  • Слайд 3

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

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

  • Слайд 4

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

  • Слайд 5

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

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

  • Слайд 6

    Алгоритмы

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

  • Слайд 7

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

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

  • Слайд 8

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

  • Слайд 9

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

  • Слайд 10

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

  • Слайд 11

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

  • Слайд 12

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

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

  • Слайд 13

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

  • Слайд 14

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

  • Слайд 15

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

  • Слайд 16

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

Посмотреть все слайды

Предложить улучшение Сообщить об ошибке