Тема лекции: Построения остовного дерева

Постановка задачи

 

Пусть имеется связный неориентированный граф G, на ребрах которого задана весовая функция c(e). Связный подграф графа G, являющийся деревом и содержащий все его вершины, называют покрывающим деревом этого графа (иногда используют термин остовное дерево или остов). Весом остовного дерева будем считать сумму весов всех его ребер. Тогда возникает задача о нахождении максимального покрывающего дерева, т.е. такого, что его вес наибольший, либо равен весу любого из покрывающих деревьев для данного графа. Будем обозначать наибольшее покрывающее дерево графа G как MAX(G).

Методы решения данной проблемы

Остовным деревом графа называется дерево, содержащее все вершмины V графа.

Стоимость остовного дерева вычисляется как сумма стоимостей всех ребер.

Идея решения:

Для остовного дерева верно следующее свойство:

Пусть G=(V,E) - свызный граф с заданной функцией стоимости, определенной на множестве ребер. Обозначим через U подмножество множества вершин V. Если (u,v) - такое ребро наибольшей стоимости, что u из U и v из V\U, тогда для графа G существует остовное дерево максимальной стоимости, содержащее ребро (u,v)

На этом свойстве основан алгоритм Прима. В этом алгоритме строится множество вершин U, из которого "вырастает" остовное дерево. Пусть V={1,2,...n}. Сначала U={1}. На каждом шаге алгоритма находится ребро наименьшей стоимости (u,v) такое, что u из U и v из V\U, затем вершина v переносится из множества V\U в множество U. Процесс продолжается до тех пор, пока множество U не станет равным множеству V.

Детали реализации:

 Удобно выбрать представление в виде списка дуг

Допустим, необходимо проложить кабель по территории университета, связав все его здания, так, чтобы из каждого здания кабель по какому-либо пути доходил до любого другого здания. Кроме того, предположим, что надо минимизировать общую длину прокладываемого кабеля. Если рассматривать здания как вершины, а кабели между зданиями как ребра, то эта работа с прокладыванием кабеля превращается в задачу определения каркаса, охватывающего здания территории университета, в котором общая длина проложенного кабеля должна быть минимальной. Такую задачу называют нахождением каркаса минимального веса. В нашей работе длина проложенного кабеля должна быть максимальной.

Определим понятие каркаса более формально. Если дан связный неориентированный граф G=(V, E), то каркас (также называемый остовным или стягивающим деревом) T=(V, E’), где E’E – это связный граф без циклов. Иными словами, каркас неориентированного графа G – это подграф графа G, дерево, содержащее все вершины графа. Понятно, что для того, чтобы T имело тот же набор вершин, что и связный граф G, и чтобы T не имело циклов, оно должно содержать ровно |V|–1 ребро.

Предположим, что для каждого ребра eE существует вес w(e), причем такой вес может выражать, например, цену, длину или время, необходимое для прохода по ребру (в нашем примере – длину кабеля между зданиями). Во взвешенном графе вес подграфа – это сумма весов его ребер. Тогда каркас T максимального веса– это каркас G, в котором вес дерева максимален относительно всех остовных деревьев G.

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

В алгоритме Краскала используется жадный подход к решению задачи, т. е. в любой момент выполнения данных алгоритмов существует множество ребер E’, представляющее подмножество некоторого минимального остовного дерева графа G. На каждом шаге алгоритмов из оставшихся ребер выбирается «лучшее» ребро, обладающее определенными свойствами, и добавляется к формируемому каркасу максимального веса. Одним из важных свойств любого ребра, добавляемого к E’, является его безопасность, т. е. то, что обновленное множество ребер E’ будет продолжать представлять подмножество некоторого минимального остовного дерева.

Описание алгоритма Краскала

Алгоритм Краскала может строить дерево одновременно для нескольких компонент связности, которые в процессе решения объединяются в одно связанное дерево.

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

Алгоритм состоит из следующей последовательности действий:

1. Создается список ребер R, содержащий длину ребра, номер исходной вершины ребра (i),номер конечной вершины ребра (j), признак включения данного ребра в дерево.

2.  Данный список упорядочивается в порядке возрастания длин ребер.

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

4.  Если все вершины включены в дерево и количество ребер на единицу меньше количества вершин, то алгоритм свою работу закончил. В противном случае осуществляется возврат к пункту 3.

Или в терминах теории графов:

Дан граф с n вершинами; длины ребер заданы матрицей. Найти остовное дерево максимальной длины.

В задаче Прима–Краскала, которая не кажется особенно простой, жадный алгоритм дает точное оптимальное решение.

Как известно (это легко доказать по индукции), дерево с n вершинами имеет n-1 ребер. Оказывается, каждое ребро нужно выбирать жадно (лишь бы не возникали циклы). То есть n-1 раз выбирать самое короткое ребро из еще не выбранное ребро при условии, что оно не образует цикла с уже выбранными.

А как следить, чтобы новое ребро не образовывало цикла со старыми? Сделать это просто. До построения дерева окрасим каждую вершину i в отличный от других цвет i. При выборе очередного ребра, например (i, j), где i и j имеют разные цвета, вершина j и все, окрашенные в ее цвет (т.е. ранее с ней соединенные) перекрашиваются в цвет i. Таким образом, выбор вершин разного цвета обеспечивает отсутствие циклов. После выбора n-1 ребер все вершины получают один цвет.

Докажем, что описанный алгоритм получает в точности максимальное решение. Для доказательства нам понадобится очень простое утверждение:

Если к дереву добавить ребро, то в дереве появится цикл, содержащий это ребро.

Действительно, пусть добавлено ребро (u, v) – “добавлено” означает, что ребро – новое, что раньше его в дереве не было. Поскольку дерево является связанным графом, то существует цепь C(u, …, v) из нескольких ребер, соединяющая вершины u и v. Добавление ребра (u, v) замыкает цепь, превращая ее в цикл.

Теорема. Алгоритм Прима–Краскала получает максимальное остовное дерево.

 

Пример   Для заданного графа произвольно пронумеровать вершины и построить кратчайшее остовное дерево, определить его длину.

Решение:

Для построения кратчайшего остовного дерева воспользуемся алгоритмом Крускала.

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

Начнем с ребер наименьшего веса, равного 1, то есть с ребер AB, BE, ED, EL, LK. 

Ребер веса 2 нет.

Следующими добавляем ребра веса 3, при этом следим, чтобы в графе не появлялись циклы. Добавляем ребра BC, CF.

К результирующему графу последовательно добавляются ребра веса 4- EG.

Добавление остальных ребер приведет к появлению цикла в уже построенной части МОД.

Таким образом, кратчайшее остовное дерево для заданного графа имеет вид:

Длина построенного кратчайшего остовного дерева равна 15.

 

 

Тема 4.3.Виды графов

 

Двудольные графы

Определение: Граф называется двудольным, если существует такое разбиение множества его вершин на две части (доли), что концы каждого ребра принадлежат разным частям.

Если при этом любые две вершины, входящие в разные доли, смежны, то граф называется полным двудольным.

  Полный двудольный граф, доли которого состоят из р и из q вершин, обозначается символом K _{p , q}. При р =1 получаем звезду K _{1, q}. На рис.1 изображены звезда К_1,5 и полный двудольный граф K_3,3.

Аналогично двудольным графам определяются k -дольный и полный k -дольный графы для k = 3, 4,... На рис.2 приведен трехдольный граф.

 

Рис. 1                                Рис. 2

 

 Для решения примеров удобно применять теорему

Теорема: Граф является двудольным т. и т.т., к. все его простые циклы имеют четную длину.

Легко подсчитать число всех графов с фиксированным множеством вершин X. Эти графы различаются своими ребрами, и потому их число равно количеству подмножеств в X⁽²⁾, т.е. 2  , где п= |X|. Однако эти графы не всегда следует различать. Как в применениях теории графов, так и в самой этой теории чаще существенно лишь то, что есть объекты (вершины графа) и связи между объектами (ребра). С этих позиций графы, которые получаются один из другого изменением наименований вершин, разумно не различать. Оформим эти соображения в виде следующего определения.

Изоморфные графы

Определение: Два графа G₁ и G ₂ называются изоморфными, если существует взаимно-однозначное отображение между множествами их вершин, сохраняющее смежность. Такое отображение называется изоморфизмом.

Два орграфа изоморфны, если существует изоморфизм между их основаниями, сохраняющий порядок вершин на каждой дуге.

Например, три графа, представленные на рис. 4, изоморфны, а графы на рис. 5 не изоморфны. Вопрос о том, изоморфны ли два данных графа, в общем случае оказывается сложным.

Рис. 4.

Рис. 5

 

Очевидно, что отношение изоморфизма графов является эквивалентностью, т. е. оно симметрично, транзитивно и рефлексивно. Следовательно, множество всех графов разбивается на классы так, что графы из одного класса попарно изоморфны, а графы из разных классов не изоморфны. Изоморфные графы можно отождествлять, т. е. считать совпадающими (их можно изобразить одним рисунком). Они могли бы различаться конкретной природой своих элементов, но именно это игно­рируется при введении понятия «граф».

В некоторых ситуациях все же приходится различать изоморфные графы, и тогда полезно понятие «помеченный граф». Граф порядка п называется помеченным, если его вершинам присвоены некоторые метки, например, номера 1, 2,..., n. Отождествив каждую из вершин графа с ее номером (и, следовательно, множество вершин – с множеством чисел {1, 2,..., n }), определим равенство помеченных графов G ₁ =(X, V ₁) и G ₂ =(X, V ₂) одного и того же порядка: G ₁ = G ₂ тогда, когда V ₁ = V ₂. На рис. 6 изо­бражены три разных помеченных графа.

При необходимости подчеркнуть, что рассматриваемые графы различаются лишь с точностью до изоморфизма, говорят: «абстрактный граф». Строго говоря, абстрактный (или непомеченный) граф – это класс изоморфных графов.

Рис. 6

Контрольные вопросы:

1. Двудольные графы.

2. Изоморфные графы.

3. Решить задачи:

1. Определите, является ли граф двудольным?

а) Граф К_3,3  (задача о колодцах);

б) ;

в) граф – додекаэдр (пятиугольник).

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

а) б)

3. Сколько можно построить графов с 3 вершинами с точностью до изоморфизма? (4)