Федоров В.Н. - Введение в теорию графов, страница 6

1a₃2c₃4f₃3d₃1e₂4h₂6i₂5k₄7m₄8l₄5 и 8j₁6g₁3b₁2.

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

1. Приведите алгоритм построения эйлеровой цепи в графе? Какому условию должен удовлетворять граф?

2. Приведите алгоритм построения эйлерового цикла в графе. Какому условию должен удовлетворять граф?

3. В чем заключается модификация алгоритмов построения эйлеровой цепи и эйлерового цикла?

4. Как можно превратить произвольный граф в эйлеров граф?

5. Приведите алгоритм покрытия графа непересекающимися по ребрам цепями.

7. Внешне устойчивые множества вершин и вершинная база графа

7.1. Внешне устойчивые множества вершин графа

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

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

Мощность минимального ДМВ обозначается β(G) и называется числом внешней устойчивости графа.

Для нахождения ДМВ образуем матрицу

A’ = E v A,

где Е – единичная матрица, А – матрица смежности.

Матрица Е вводится для учета изолированных вершин.

Найдем в матрице A’ минимальное множество строк, единицы в которых покрывают все столбцы. Множество вершин, соответствующее этому множеству строк, и есть ДМВ.

Пример. Для графа, показанного на рис. 7.1, получаем

A’ = E v A = v = .

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

Анализируя матрицу A’, замечаем, что

• для покрытия столбца 1 нужна строка 1 (v₁),

• для покрытия столбца 2 нужна строка 1 (v₁), или строка 2 (v₂), или строка 3 (v₃), что можно записать так (v₁ v₂ v₃),

• для покрытия столбца 3 нужна строка 3 (v₃),

• для покрытия столбца 4 нужна строка 2 (v₂) или строка 4 (v₄), что можно записать (v₂ v₄).

Поскольку нам необходимо покрыть строками и столбец 1, и столбец 2, и столбец 3, и столбец 4, то для покрытия всех столбцов, заменив союз И символом конъюнкции, можно записать

v₁ (v₁ v₂ v₃) v₃ (v₂ v₄).

Раскрыв скобки и проведя преобразования, получаем

v₁ v₂ v₃ v₁ v₃ v₄.

Каждое из множеств {v₁,v₂,v₃} и {v₁,v₃,v₄} является доминирующим множеством вершин.

число внешней устойчивости данного графа β(G) равно 3.

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

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

1. Получить матрицу A’ = E v A.

2. Обозначить вершины графа логическими переменными, например, x₁, x₂, x₃,…, x_n, где x_i = 1, если вершина принадлежит какому либо внешне устойчивому множеству, и x_i = 0 в противном случае.

3. Для каждой вершины графа, используя матрицу A’, записать выражение

где – x_i вершина, соответствующая выбранной строке,

x_k, x_l,…, x_q – вершины, смежные ей.

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

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

П = C_i C_j … C_k .

1. Провести преобразования логического выражения П для получения минимальной дизъюнктивной нормальной формы (МДНФ).

2. Каждая конъюнкция полученной МДНФ будет являться доминирующим множеством вершин графа, а количество переменных в минимальной из них будет числом внешней устойчивости данного графа β(G). В совокупности получим семейство из всех внешне устойчивых множеств графа.

7.3. Вершинная база

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

Для нахождения вершинной базы необходимо сформировать матрицу

A” = E v A v…v A^n-1,

где Е – единичная матрица размера n n, А,…, A^n–1 – степени матрицы смежности графа, от 1 до n–1.

Затем надо найти в матрице A” множество строк, единицы в которых покрывают все столбцы, – множество вершин, соответствующее этому множеству строк, и есть вершинная база.

В качестве примера найдем вершинную базу графа, показанного на рис. 7.1.

Составим матрицу смежности графа

A = .

Определим необходимые степени матрицы смежности

A²= * = ,

A³= * = .

Определим матрицу A”

A”= E v A v A² v A³ = .

Для определения вершинной базы необходимо найти вершины, строки которых покрывают все столбцы матрицы A”.

Анализируя матрицу A”, замечаем, что

• для покрытия столбца 1 нужна строка 1 (v₁),

• для покрытия столбца 2 нужна строка 1 (v₁), или строка 2 (v₂), или строка 3 (v₃), что можно записать так (v₁ v₂ v₃),

• для покрытия столбца 3 нужна строка 3 (v₃),

• для покрытия столбца 4 нужна или строка 1 (v₁), или строка 2 (v₂), или строка 3 (v₃), или строка 4 (v₄), что можно записать так

(v₁ v₂ v₃ v₄).

Поскольку надо покрыть единицами и первый столбец, и второй столбец, и третий столбец, и четвертый столбец, то, заменив союз И символом конъюнкции, запишем

v₁ (v₁ v₂ v₃) v₃ (v₁ v₂ v₃ v₄).

Раскрыв скобки и проведя преобразования, получаем

v₁ v₃.

Множество вершин {v₁, v₃} и есть вершинная база графа.

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

1. Поясните понятие внешней устойчивости графа.

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

3. Число внешней устойчивости графа – что это такое и как оно обозначается?

4. Поясните понятие вершинной базы графа. Чем это понятие похоже и чем отличается от внешней устойчивости графа?

5. Приведите алгоритм определения вершинной базы графа.

6. Как определяется множество строк матриц A’ и A”, покрывающих единицами все столбцы этих матриц?

8. Внутренняя устойчивость и раскраска графа

8.1. Внутренне устойчивые множества вершин графа

Множество вершин графа, среди которых нет смежных, называется независимым множеством вершин (НМВ) или внутренне устойчивым множеством вершин.

Если такое множество не является подмножеством другого множества с таким свойством, то оно максимально.

Мощность максимального независимого множества вершин (МНМВ) α(G) – называется числом внутренней устойчивости графа.

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

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

1. Составить матрицу смежности графа.

2. Обозначить вершины графа логическими переменными, например, x₁, x₂, x₃,…, x_n, где x_i = 0, если вершина принадлежит какому либо внутренне устойчивому множеству, и x_i = 1 в противном случае.

Обратите внимание на отличие значений x_i от значений этой переменной в алгоритме определения внешне устойчивых множеств вершин графа.

1. В матрице смежности выбрать строку с максимальным числом ненулевых элементов. Если таких строк несколько, то берется любая из них.

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

где x_i – вершина, соответствующая выбранной строке, x_k, x_l,…, x_q – вершины, смежные ей.

Трактовать это выражение можно так – во внутренне устойчивое множество вершин графа не должна входить вершина x_i или ни одна из вершин, смежных с ней.

1. После этого в строке и столбце матрицы смежности с индексом i единицы заменить нулями (строку и столбец с индексом i можно удалить).

2. В полученной матрице смежности снова выбрать строку с наибольшим числом ненулевых элементов (например, строку j) и записать выражение

1. Строка и столбец с индексом j обнуляются.

2. Процесс повторяется, пока все строки матрицы смежности не станут пустыми (одни нули).

В строках изолированных и тупиковых вершин первоначальной матрицы смежности стоят только 0, поэтому для них не будут составлены выражения C_i. Изолированные вершины обязательно войдут в любое из внутренне устойчивых множеств и будут учтены в п. 10 алгоритма. поэтому их можно сразу исключить из матрицы смежности, упростив тем самым решение задачи. Тупиковые вершины будут учтены в выражениях для вершин, смежных с ними.

1. Из полученных выражений C_i, C_j, , C_k составить произведение

П = C_i C_j … C_k,

в котором раскрыть скобки и провести минимизацию.

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

В совокупности получим семейство из всех независимых множеств.

1. Число внутренней устойчивости графа α(G) будет равно количеству вершин, вошедших в максимальное независимое множество вершин.

Пример. Дан граф G(6,6) рис. 8.1.

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

С
оставляем матрицу смежности графа

Рисунок 8.1

Выбираем строку 2. Записываем

Обнуляем строку и столбец с индексом 2.