7 Остовное дерево наименьшей стоимости Пусть связный неориентированный граф, для которого задана функция стоимости, отображающая рёбра в вещественные числа icon

7 Остовное дерево наименьшей стоимости Пусть связный неориентированный граф, для которого задана функция стоимости, отображающая рёбра в вещественные числа


Смотрите также:
Это конечный связный граф с выделенной вершиной...
8 Двусвязность Рассмотрим приложение метода поиска в глубину к выделению в неориентированном...
Программа кандидатского экзамена по специальности 08. 00. 10. Финансы...
1. Методы расчета стоимости активов предприятия...
Правила определения стоимости активов и величины обязательств Закрытого паевого инвестиционного...
Программа семинара понятие и значение кадастровой стоимости для определения размера земельного...
Об аналоге формулы блэка-шоулза для инвестиционной стоимости акций...
I. деньги, денежное обращение и денежная система тема 1 Сущность и функции денег...
Отчет № А0/08 Об определении рыночной стоимости объектов недвижимости в составе автозаправочной...
Задачи Для достижения данной цели потребовалось решение следующих теоретических и практических...
Методика оценки стоимости поврежденных транспортных средств...
Лекция 20. Производная и дифференциал функции нескольких переменных...



Загрузка...
скачать

Лекция 07. Алгоритмы на графах


Многие задачи теоретического и прикладного характера можно сформулировать в терминах неориентированных или ориентированных графов. Мы в основном будем рассматривать задачи, в которых речь идет о связности графа. Сюда входят алгоритмы для нахождения остовных деревьев, двусвязных компонент, сильно связных компонент и путей между узлами.

Тема 7.1. Остовное дерево наименьшей стоимости


Пусть – связный неориентированный граф, для которого задана функция стоимости, отображающая рёбра в вещественные числа.

Определение: остовным деревом для графа называется неориентированное дерево вида , где .

Стоимость остовного дерева определяется как сумма стоимости его рёбер. Наша цель – найти для графа остовное дерево наименьшей стоимости. Многие алгоритмы нахождения остовного дерева основаны на следующих утверждениях.

Лемма 1. Пусть – связный неориентированный граф и - остовное дерево для него. Тогда:

    • для путь между и в единственный;

    • если к добавить ребро из , то возникнет ровно один цикл.

Лемма 2. Пусть – связный неориентированный граф и – функция стоимости, заданная на его рёбрах. Пусть – произвольный остовной лес для , , и



Допустим, что – ребро наименьшей стоимости в , при чём и . Тогда найдётся остовное дерево для , содержащее , стоимость которого не больше стоимости любого остовного дерева для , содержащего .

Опишем алгоритм нахождения остовного дерева наименьшей стоимости для неориентированного графа .

Вход: Неориентированный граф , с функцией стоимости , заданной на его дугах.

Выход: Остовное дерево наименьшей стоимости для .

Метод: Этот алгоритм работает с набором непересекающихся множеств узлов. Каждое множество из представляет связное множество узлов, образующее остовное дерево в остовном лесу, представленное набором . Дуги выбираются из в порядке возрастания стоимости. Дуги рассматриваются по очереди. Если v и w принадлежат одному и тому же множеству из , то ребро исключается из рассмотрения. Если и принадлежат разным множествам и (это означает, что и ещё не соединены), то сливаем их в одно множество и добавляем к множеству дуг, входящих в окончательное остовное дерево.

Алгоритм:

T  

VS  

построить очередь с приоритетами Q, содержащую все рёбра из Е

for v  V do добавить {v} к VS

while VS  > 1 do

выбрать в Q ребро (v, w) наименьшей стоимости

удалить (v, w) из Q

if v и w принадлежат различным множествам W1 и W2 из VS then

заменить W1 и W2 на W1  W2 в VS

добавить (v, w) к Т

end if

end while


П
ример:


Рассмотрим неориентированный граф. Перечислим его ребра в порядке возрастания их стоимостей:


Ребро

Стоимость

Ребро

Стоимость



1



17



3



20



4



23



9



25



15



28



16



36


На самом деле дуги не сортируются, а хранятся в виде сортирующего дерева, 2-3 дерева или какой-нибудь другой приемлемой структуры данных, пока они не потребуются. Сортирующее дерево фактически даёт идеальный способ реализации очереди с приоритетами. 6 строка может быть реализована алгоритмом СОРТДЕРЕВОМ. Вначале каждое ребро находится в одноэлементном множестве, входящем в и состоящем из одного этого ребра. Наименьшую стоимость имеет дуга , так что оно добавляется к дереву и множества и в сливаются.

Затем рассматривается дуга . Т.к. и принадлежат разным множествам из , добавляем к дереву и сливаем и . Далее добавляем и сливаем c . Добавляем так же четвёртую дугу и сливаем с .

Затем рассматриваем дугу . Оба узла и принадлежат одному множеству . Следовательно, из в идёт путь из дуг, уже вошедших в остовное дерево, и потому не добавляется. И т.д.


Ребро

Действие

Множество из (связные подграфы)



Добавить





Добавить





Добавить





Добавить





Отвергнуть






Отвергнуть






Добавить





Отвергнуть






Добавить





^

Тема 7.2. Метод поиска в глубину


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

Осуществляя поиск в глубину на связном неориентированном графе мы посещаем каждый узел и исследуем каждую дугу. Если граф несвязен, то отыскивается его связная компонента. Закончив работу с ней, выбирают в качестве нового начального узла узел, который ещё не посещался, и начинают новый поиск.

Поиск в глубину на неориентированном графе разбивает дуги, составляющие , на два множества и . Дугу помещается в множество , если узел не посещался до того момента, когда мы, рассматривая дугу , оказались в узле . В противном случае ребро помещается в множество . Ребра из будем называть древесными, а из – обратными. Подграф представляет собой неориентированный лес, называетмый остовным лесом для . Если этот лес состоит из единственного дерева будем называть его по аналогии глубинным остовным деревом. Заметим, что если граф связен, то глубинный остовной лес будет деревом. Узел, с которого начинался поиск, считается корнем соответствующего дерева.

Изложим алгоритм поиска в глубину.

Вход: Неориентированный граф , представленный списками смежности для .

Выход: Разбиение множества на два множества: древесных дуг и обратных дуг .

Метод: Рекурсивная процедура ПОИСК(), которая добавляет к ребро , если узел был впервые достигнут во время прохождения по дуге из . Все узлы вначале помечены как «новые».

Алгоритм:

procedure ПОИСК_В_ГЛУБИНУ

T  (6)

for v V do пометить узел v как «новый» (7)

while существует узел vV, помеченный как «новый» do (8)

call ПОИСК(v) (9)

end while

next v

end proc


procedure ПОИСК(v)

пометить узел v как «старый» (1)

for wL[v] do (2)

if узел w помечен как «новый» then (3)

добавить (v, w) к Т (4)

call ПОИСК(w) (5)

end if

next w

end proc


П
ример
: Будем изображать ребра, входящие в – сплошными линиями, а ребра из В – штриховыми. Корень дерева будем изображать вверху.


Вначале все узлы помечены как новые. Пусть в строке 8 выбирается узел - в качестве корня дерева. Выполняя ПОИСК(), можно в строке 2 взять . Т.к. этот узел помечен как «новый», добавляем к и вызываем ПОИСК(). Теперь можно было бы выбрать узел из , но он уже помечен как «старый». Тогда выберем . Т.к. – «новый» узел, добавляем к и вызываем ПОИСК(). Каждый узел, смежный с является теперь «старым», так что снова вызываем ПОИСК().

Выполняя процедуру ПОИСК() находим дугу , добавляем его к и вызываем ПОИСК(v4). Никакие «новые» узлы не смежны с , так что опять вызываем ПОИСК(). На этот раз мы не обнаруживаем «новых» узлов, смежных с , и потому вызываем ПОИСК(). Далее ПОИСК() находит , а ПОИСК() находит . .Все узлы находятся на дереве и они помечены как «старые». Т.о. алгоритм закончил свою работу.




Скачать 77.59 Kb.
оставить комментарий
Дата04.03.2012
Размер77.59 Kb.
ТипЛекция, Образовательные материалы
Добавить документ в свой блог или на сайт

Ваша оценка этого документа будет первой.
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

Рейтинг@Mail.ru
наверх