Остовное дерево графа. Алгоритмы Прима и Краскала

 

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

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

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

Задача. В заданном взвешенном графе, , среди всех его остовных деревьев найти остовное дерево минимального веса.

Рассмотрим два алгоритма, решающих эту задачу.

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

Шаг 0. Строим подграф, где. (Граф несвязный, все вершины изолированные).

Шаг 1. Находим ребро c минимальным весом. Строим подграф, где.

Шаг k. Находим ребро, удовлетворяющее трем условиям:

1) ребро является смежным некоторому ребру графа,

2) ребро не образует цикла при добавлении к графу,

3) ребро имеет минимальный вес среди тех ребер, которые удовлетворяют первым двум условиям.

Строим подграф =, где.

Если, то построено минимальное остовное дерево.

Следующая теорема является обоснованием алгоритма Прима.

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

Доказательство. Прежде всего, покажем, что подграф может быть построен по правилам алгоритма. Для этого достаточно показать выполнимость любого шага k. Для каждого подграфа число вершин равно n, число ребер равно, следовательно, в подграфе имеется изолированная вершина. Исходный граф G – связный, поэтому всегда найдется хотя бы одно ребро \, которое в подграфе связывает изолированную вершину с неизолированной вершиной.

Далее, по построению подграф – связный, и для него, т.е. выполняются условия теоремы 3.2 (п.3). Следовательно, – дерево, причем остовное.

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

³ . (4.1)

Пусть, , …, – последовательность ребер, которая образовала дерево (по шагам алгоритма), и пусть ребра, , , общие и для дерева и для дерева.

Рассмотрим ребро Î и Ï. Если это ребро добавить к минимальному дереву, то получим новый граф, который содержит ровно один цикл (теорема 3.2 (п. 5)). Заметим, во-первых, что среди ребер цикла найдется ребро Ï, ибо в противном случае в графе был бы цикл. Во-вторых, ребро по построению является смежным некоторому ребру подграфа G_s, поэтому вес ребра не больше веса ребра согласно требованию 3) шага k. Заменим ребро в дереве на ребро. Получим новое остовное дерево, для которого

£ . (4.2)

Далее рассмотрим ребро {i_s+2, j_s+2}Î U_{n – 1} и {i_s+2, j_s+2} Ï. Рассуждая аналогично, построим остовное дерево такое, что

£ . (4.3)

Продолжим аналогичные построения, и через конечное число шагов получим остовное дерево, состоящее из ребер, , …, , т.е. дерево. При этом из (4.2), (4.3) и аналогичных им неравенств следует, что

£ . (4.4)

Тогда из (4.1) и (4.4) получаем =, т.е. имеет минимальный вес. Теорема доказана.

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

Шаг 0. Строим подграф =, где. (Граф несвязный, все вершины изолированные).

Шаг 1. Находим ребро с минимальным весом. Строим подграф =, где =.

Шаг k. Находим ребро, удовлетворяющее двум условиям:

1) ребро не образует цикла при добавлении к графу,

2) ребро имеет минимальный вес среди тех ребер, которые удовлетворяют первому условию.

Строим подграф =, где=.

Если k = n - 1, то построено минимальное остовное дерево.

Обоснование алгоритма Краскала дает следующая теорема.

Теорема 4.2. Пусть – связный граф, у которого, и подграф построен по алгоритму Краскала. Тогда – остовное дерево минимального веса.

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

Далее, по построению подграф не содержит циклов, и для него, т.е. выполняются условия теоремы 3.2 (п. 2). Следовательно, подграф – остовное дерево.

Доказательство того, что – остовное дерево минимального веса, аналогично соответствующей части теоремы 4.1.

Пример. Рассмотрим граф, представленный на рис. 4.1. Каждому ребру графа поставлен в соответствие вес. Построить остовное дерево минимального веса согласно алгоритмам Прима и Краскала.

1) Согласно алгоритму Прима остовное дерево должно включать все вершины заданного графа. На первом шаге добавляем ребро, имеющее минимальный вес, равный 1. Далее добавляем ребро с весом 2. На третьем шаге выбор следует сделать из ребер, , , , , которые смежные ребрам и. Ребро образует цикл, поэтому его из списка исключаем. Среди остальных минимальный вес, равный 4, имеют два ребра. Выберем ребро. В дальнейшем следует последовательно добавить: ребра с весом 2, с весом 3, с весом 4, с весом 3 и ребро с весом 5. Полученное дерево представлено на рис. 4.2. Его вес равен 24.

2) Остовное дерево, построенное согласно алгоритму Краскала приведено на рис. 4.3. К несвязному графу G₀ последовательно добавлены ребра: , , , , , , , . Это ос
товное дерево отличается от дерева, построенного по алгоритму Прима, но его вес также равен 24.

 

Задания

1. Используя алгоритмы Прима и Краскала, построить остовное дерево графа на рисунке 4.1, веса ребер которого заданы в следующей таблице

 

Ориентированные графы

 

Ориентированный граф G (или орграф ), как и неориентированный, определяется заданием двух множеств I и U и обозначается также: .

Элементы множества I, как и прежде, называются вершинами. Будем их обозначать буквами i , j. Вершины изображают точками плоскости или пространства.

Множество U есть подмножество множества (декартово произведение множества I на себя). Элементами множества U являются упорядоченные пары вершин, их называются дугами. Другими словами, для двух рассматриваемых вершин указано, какая из них первая, ее называют началом дуги, какая вторая, ее называют концом дуги. Обозначать их будем либо буквами, либо парами вида, а изображать отрезками кривых или прямых линий, со стрелкой у вершины, которая является концом дуги.

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

Для ориентированного графа вводятся понятия полустепени заходавершины – количество дуг, заходящих в, и полустепени исхода – количество дуг, исходящих из. Понятно, что + =. На рис. 5.1а для вершины i₂ имеем: , , .

Как и прежде, вершина, степень которой равна нулю, называется изолированной. Вершина, степень которой равна единице, называется висячей, инцидентная ей дуга также называется висячей.

Если в графе G множество U содержит как ребра, так и дуги, то граф называется смешанным. Смешанный граф преобразуется в орграф путем замены ребра {i, j} на две дуги и. На рис. 5.1б представлен пример смешанного графа. После замены ребра на дуги и, ребра на дуги и получим орграф, который представлен на рис. 5.1в.

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

, , …, , . (5.1)

Задать маршрут (5.1) можно и последовательностью его вершин:

, (5.2)

где – начало маршрута, – конец маршрута. Говорят, что вершина достижима из вершины. Ориентированная цепь – ориентированный маршрут, все дуги которого различны. Ориентированная цепь, все вершины которой различны, называется путем.

Если в ориентированном маршруте (ориентированной цепи, пути) начало и конец совпадают: , то получаем циклический ориентированный маршрут ( ориентированный цикл, контур ).

На рис.5.1в последовательность вершин задает ориентированную цепь; последовательность вершин задает путь, который можно записать как последовательность дуг

, , ,

последовательность дуг, , задает контур.

Нетрудно убедиться, что справедлива

Лемма 5.1. Любой ориентированный маршрут содержит путь.

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

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

Так же как и для неориентированного графа вводятся понятие подграфа и понятие компоненты связности. Очевидно, что для ориентированного графа остается верной лемма 1.4.

Рассмотрим способы задания ориентированного графа. Как и неориентированный граф его можно задать рисунком или с помощью матрицы. Для простого орграфа G, в котором, , матрица смежности – это квадратная матрица А порядка n (строки и столбцы этой матрицы соответствуют вершинам графа G). Элементы матрицы определяются следующим образом:

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

Матрица инцидентности – это n´ m-матрица В (строки этой матрицы соответствуют вершинам графа G, а столбцы – дугам). Элементы матрицы определяются следующим образом:

Из определения вытекает, что каждый столбец матрицы инцидентности содержит ровно два ненулевых элемента: 1 и -1. Степень вершины равна числу ненулевых элементов строки, число единиц в соответствующей строке равно степени захода, а число отрицательных элементов есть степень исхода.

Матрицы смежности и инцидентности графа, представленного на рис.5.1а имеют вид:

, .

Еще один способ задания орграфа – списки смежности. Каждой вершине i графа ставится в соответствие список вершин, недостижимых из вершины i посредством одной дуги. Например, для графа, представленного на рис.5.1а, списки смежности следующие:

= (i₄), = (i₁, i₃), = Æ, = (i₂, i₃).

 

Задания

1. Доказать лемму 5.1.

2. Составить матрицу смежности и матрицу инцидентности орграфа, представленного на рис.5.1в.

 

⇐ Предыдущая123456Следующая ⇒

Поделиться: