Множество внешней устойчивости графа

 

Множество внешней устойчивости – множество вершин, для которых выполняется одно из следующих правил:

1). Любая вершина входит в это множество

2) Либо вершина не входит в это множество, но из этой вершины есть дуга в данное множество.

Пусть дан граф . Тогда для множества внешней устойчивости справедливо следующее:

(3.12)

Число внешней устойчивости (β) – это наименьшая мощность из всех множеств внешней устойчивости.

 

Алгоритм Магу для определения множества внешней устойчивости.

Пусть дан граф . Для данного графа существует множество внешней устойчивости .

Вводятся булевые переменные и по тому же правилу, что и для алгоритма Магу для определения множества внутренней устойчивости.

Тогда определение множества внешней устойчивости (3.12) запишется следующим образом:

(3.13)

Для справедливо следующее

(3.14)

Данное уравнение лежит в основе алгоритма Магу

Алгоритм Магу состоит из следующих этапов:

1. Для графа составляется матрица смежности

2. Матрица смежности дополняется единицами (1) по главной диагонали.

3. Для каждой строки выписываются дизъюнкции.

4. Выражение приводится к ДНФ.

5. Все вершины, входящие в элементарную конъюнкцию, образуют множество внешней устойчивости

 

ПРИМЕР

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

Матрица смежности имеет вид:

 

Дополним матрицу смежности единицами по главной диагонали

 

Для каждой строки выписываются дизъюнкции:

(3.15)

Приведем выражение к ДНФ:

(3.16)

Множества внутренней устойчивости:

Числом внешней устойчивости = 2.

 

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

Граф, представленный на рис. 3.7. имеет ядро

 

Множество путей в графе

 

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

Если элемент матрицы :

- между i -той и j - той вершины не существует пути длиной в к единиц;

- между i -той и j - той вершины существуют различных путей длиной в к единиц;

Если - нулевая матрица, это означает, что графе нет путей в к единиц, а максимальный путь – это путь длиной в (к -1) единиц.

 

А лгоритм фронта волны. Поиск минимального пути в графе.

 

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

Рассмотрим некоторые свойства минимальных путей

1. Любой минимальный путь является простым путем.

2. Если путь - минимальный, то любые пути внутри минимального пути также будут минимальны.

Пусть Г^-1_х – прообраз вершины x_i – это множество вершин, из которых исходят дуги в вершину x_i.

Одним из алгоритмов поиска минимального пути в графе является алгоритм фронта волны (FW –Front Wave)

 

Алгоритм фронта волны.

 

Пусть необходимо найти минимальный путь из вершины в вершину .

1. Выписываются все вершины с 1 по n. Вершина помечается индексом 0.

2. Находится первый фронт волны как множество вершин образа вершины .

(3.17)

3. Все вершины, принадлежащие первому фронту волны, помечаются индексом 1.

4. Вводится счетчик шагов (фронтов волны) .

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

6. Если , то переходим к пункту 8. В противном случае существует путь из вершины в вершину длиной в единиц, и этот путь минимальный:

7. Находятся промежуточные вершины z по правилу:

, (3.18)

где - прообраз вершины - множество вершин, из которых заходят дуги в вершину

8. Определяется фронт волны как все непомеченные вершины, принадлежащие образу вершин - го фронта волны. Помечаются индексом вершины фронта волны. Далее осуществляется переход к пункту 5.

 

ПРИМЕР

Пусть задан граф матрицей смежности:

 

Необходимо найти минимальный путь из вершины в вершину (по алгоритму «фронта волны»).

1. Выпишем все вершины. Вершина помечается индексом «0»

 

2. Находится первый фронт волны:

3. Все вершины, принадлежащие первому фронту волны, помечаются индексом «1».

0 1 1

4. Так как , и , то определяем второй фронт волны:

5. Все вершины, принадлежащие второму фронту волны, помечаются индексом «2».

0 2 2 1 1

6. Так как , и , то определяем третий фронт волны:

7. Так как , то существует путь из вершины в вершину длиной 3 единицы:

8. Находятся промежуточные вершины :

Выберем

Выберем

Таким образом, минимальный путь из вершины в вершину имеет вид: