8(25). Задача об остове экстремального веса.

Пусть G=(V,E,Ω) – связная сеть, где V – множество вершин, E – множество ребер, Ω – матрица весов. Часто в приложениях возникает задача о построении остова графа G, имеющего наименьший вес.

Пусть G=(V,E,Ω) служит моделью железнодорожной сети, соединяющей пункты V, а ( ) – это расстояние между пунктами .

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

Существует несколько алгоритмов построения экстремального остовного дерева. Рассмотрим алгоритм Прима. Этот алгоритм еще называют алгоритмом ближайшего соседа. Алгоритм представляет собой итерационную процедуру, состоящую из двух шагов и выполняющуюся (n-1) раз в графе G с n-вершинами. Алгоритм может получить минимальное или максимальное по весу дерево в зависимости от того, находится ли в формуле min или max.

Разобьем множество вершин графа G на два непересекающихся подмножества – таких, что V’  V’’ = V;

V’  V’’ = 

Определим пошаговое расстояние между множествами V’ и V’’ следующим образом: d(V’, V’’)=min{( )};  V’ ;  V’’; где - дуга, содержащая вершины и .

В алгоритме Прима остовное дерево строится в результате последовательного расширения исходного поддерева. На каждой итерации число вершин и ребер поддерева увеличивается на 1.

Основные шаги алгоритма Прима:

1. Присвоение начальных значений. Полагаем, что V’={ }; где – произвольная вершина из множества V.

V’’= V \ V’ E’ = 

2. Обновление данных. Находится ребро такое, что  V’ ;  V’’; ( ) = min { ()};

V’ :=V’ { } ; V” :=V \ V’; E’ := E’  { }

3. Проверка на завершение. Если V’=V => G’ = (V’,E’) – искомый остов. В ином случае переход к шагу 2

9(26) Эйлеровы графы и циклы. Алгоритм Флерн. Гальмитоновые графы и циклы

Опр. Эйлеровой цепью (циклом) в графе G наз. цепь (цикл), проходящий по одному разу через каждое ребро графа

Опр. Граф наз. Эйлеровым, если он имеет эйлеров цикл

Т1. Связный граф явл. Эйлеровым тогда и только тогда, когда степени его вершин четные

Т2. Чтобы связный граф обладал эйлеровой цепью необходимо и достаточно, чтобы он имел ровно 2 вершины нечетной степени

Алгоритм Флерн

1) Произвольно выбираем вершину V₁ и ребро е₁ инцидентное V₁. Этому ребру присваивают номер 1. Вычеркивают это ребро и переходят в вершину V₂ по ребру е₁=(V₁, V₂)

2) Находясь в вершине Vi, следует не выбирать ребро, соединенное с V₁, если имеется возможность иного выбора

3) Находясь в вершине Vi, не следует выбирать ребро, которое является перешейком, т.е. ребро при удалении которого граф, образованный невычеркнутыми ребрами распадается на 2 компоненты связности каждая из которых состоит хотя бы из 1 ребра

4) После того как в графе будут задействованы все ребра, образуется эйлеровый цикл, при чем порядок нумерации соответствует последовательности обхода ребер

Прим. Построить эйлеров цикл в графе G изображенном на рисунке

Д ля этого проверим, что граф эйлеров

P(V₁)= P(V₂)= P(V₄)= P(V₅)= P(V₆)= P(V₇)=3

P(V₃)=4

По т1 граф G эйлеров

1. Выберем вершину V₁ и ребро е₁=( V₁, V₂) и присвоим е₁ номер 1

2. Переходим в вершину V₂ и не выбираем е₁=(V₁, V₂) остается только (V₂, V₃)

3. В вершину V_3. Можем пойти в вершины V_4, V₆ и V_7, при этом (V₃, V₇)– перешеек, поэтому вершину V₇ не можем выбрать. Тогда в V₄

4. После 8 шагов опять приходим в вершину V_1, т.о. построили эйлеров цикл

(V₁, V₂)- (V₂, V₃)- (V₃, V₄)- (V₄, V₅)- (V₅, V₆)- (V₆, V₃)- (V₃, V₇)- (V₇, V₁)

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

Опр. Граф у которого есть гальмильтоновый цикл, наз. Гальмильтоновым

П рим. G1 – не гальмильтоновый

G2 - гальмитоновый

Зам: Гальм. Цикл не обязательно содержит все ребра графа, гальмит. Может быть олько связный граф

Т1 Если для любой пары u и v не смежных вершин графа G, где n≥3 выполняется условие P(u)+p(v)≥n, то G гамил. граф

Сл. Если в простом графе G с n≥3 вершинами и для любой вершины u графа G, выполняется, что, P(u) ≥n/2, то G гальм. граф