Полная версия

Главная arrow Математика, химия, физика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

Вычисление чисел внутренней и внешней устойчивости

Теоретические сведения

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

Вершинное число независимости графа (или число внутренней устойчивости графа) — мощность наибольшего пустого подграфа, обозначается как е0(б).

Любая вершина покрывает саму себя, смежные вершины и инцидентные ребра. Вершинное число внешней устойчивости графа С — минимальная мощность множества вершин, покрывающих все вершины графа, обозначается как (30.

Задачи

Задача 2.133. Для графа на рис. 2.23 найти:

  • а) все пустые подграфы и вершинное число независимости (число внутренней устойчивости);
  • б) все внешне устойчивые множества вершин и вершинное число внешней устойчивости.
Условие задачи 2.133

Рис. 2.23. Условие задачи 2.133

Решение.

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

Выбираем среди них любую вершину (в рассматриваемом примере это вершина 1) и изображаем ее и все смежные с ней вершины — {2, 3} — на первом уровне дерева. Выбор первой вершины уровня, вообще говоря, произволен, но удобнее выбрать такую вершину, чтобы остальные вершины уровня (смежные ей) были смежны и между собой, — так уменьшается количество повторных путей в результирующем дереве (рис. 2.24).

Рядом с каждой вершиной получившегося уровня выписываем вершины, несмежные с ней, входящие в метку вершины-родителя на предыдущем уровне. Например, несмежными с вершиной 3 среди вершин {1, 2, 3, 4, 5, 6, 7} являются вершины {5, 6, 7} — получили метку вершины 3. Продолжаем построение дерева до тех пор, пока метки всех вершин нижних уровней не станут пустыми. Так, для вер-шин-потомков вершины 3 — смежных между собой {5, 6, 7} — метки будут пустыми, так как в метку родителя входили только они сами.

Получившееся дерево пустых подграфов представлено на рис. 2.24. Выпишем все пустые подграфы — пути от первой фиктивной вершины до каждого листа дерева, за исключением повторных: {1, 4, 5}, {1, 4, 6}, {1, 4, 7}, {2, 4, 5}, {2, 4, 6}, {2, 4, 7}, {3, 5}, {3, 6}, {3, 7}. Мощность наибольшего пустого подграфа равна 3 — это и есть число внутренней устойчивости.

В рассмотренном примере удалось избежать появления повторных путей, но если бы первой при построении дерева была выбрана, к примеру, вершина 3, результирующее дерево имело бы вид, представленный на рисунке ниже, где повторными являются пути {1,4, 5} и {4, 1, 5}, {2, 4, 5} и {2, 5, 4} и др.

Для поиска числа внешней вершинной устойчивости построим матрицу покрытий (табл. 2.11).

Решение задачи 2.133

Вершины

1

2

3

4

5

6

7

1

1

1

1

0

0

0

0

2

1

1

1

0

0

0

0

3

1

1

1

1

0

0

0

4

0

0

1

1

0

1

0

5

0

0

0

0

1

1

1

6

0

0

0

1

1

1

1

7

0

0

0

0

1

1

1

Составим логическое выражение, используя логическое умножение как знак для операции «и» и логическое сложение для операции «или».

(1 + 2 + 3)- (1 +2 + 3)-(1 + 2 + 3 + 4)- (3 + 4 + 6)- (5 + 6 + 7) х

х (4 + 5 + 6 + 7) • (5 + 6 + 7) = (1 + 2 + 3) • (3 + 4 + 6) • (5 + 6 + 7) =

= (3+1-4+1-6 + 2- 4 + 2-6)-(5 + 6 + 7) =

= 3- 5 + 3- 6 + 3- 7+1 - 4- 5 + ...

После раскрытия скобок получим список всех внешне устойчивых множеств, мощность самого короткого слагаемого равна 2, это и есть число вершинной внешней устойчивости.

Ответ. є0 = 3, (30 = 2.

Задача 2.134. Чему равно число внешней вершинной устойчивости простого цикла на восьми вершинах?

Задача 2.135. Чему равно число внешней вершинной устойчивости простого цикла на девяти вершинах?

Задача 2.136. Чему равно число внешней вершинной устойчивости простого цикла на 31 вершине?

Задача 2.137. Чему равно число внешней вершинной устойчивости полного двудольного графа К4 9?

Задача 2.138. Чему равно число внутренней вершинной устойчивости полного графа на семи вершинах?

Задача 2.139. Чему равно число внутренней вершинной устойчивости пустого графа на семи вершинах?

Задача 2.140. Чему равно число внутренней вершинной устойчивости простого цикла на семи вершинах?

Задача 2.141. Чему равно число внутренней вершинной устойчивости простого цикла на восьми вершинах?

Задача 2.142. Чему равно максимальное число внешней вершинной устойчивости дерева на шести вершинах?

Задача 2.143. Чему равно минимальное число внешней вершинной устойчивости дерева на шести вершинах?

Задача 2.144. Чему равно максимальное число внутренней вершинной устойчивости дерева на шести вершинах?

Задача 2.145. Чему равно минимальное число внутренней вершинной устойчивости дерева на шести вершинах?

Задача 2.146. У какого графа на 15 вершинах числа внутренней и внешней вершинной устойчивости совпадают и равны 15?

Задача 2.147. Для графа на рис. 2.25 найти:

  • а) все пустые подграфы и вершинное число независимости (число внутренней устойчивости);
  • б) все внешне устойчивые множества вершин и вершинное число внешней устойчивости.
Условие задачи 2.147

Рис. 2.25. Условие задачи 2.147

Задача 2.148. Для графа на рис. 2.26 найти:

  • а) все пустые подграфы и вершинное число независимости (число внутренней устойчивости);
  • б) все внешне устойчивые множества вершин и вершинное число внешней устойчивости.

Задача 2.149. Вычислить число внешней устойчивости графа (7 = = С5 и К-,-,, где С5 — простой цикл на пяти вершинах; АГ77 — полный граф на 77 вершинах. Графы имеют одну общую вершину.

5

Условие задачи 2.148 Задача 2.150. Для графа на рис. 2.27 найти

Рис. 2.26. Условие задачи 2.148 Задача 2.150. Для графа на рис. 2.27 найти:

  • а) все пустые подграфы и вершинное число независимости (число внутренней устойчивости);
  • б) все внешне устойчивые множества вершин и вершинное число внешней устойчивости.
Условие задачи 2.150

Рис. 2.27. Условие задачи 2.150

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

Таблица 2.12

Условие задачи 2.151

Вершины

1

2

3

4

5

6

7

8

9

1

1

1

1

1

2

1

1

1

1

3

1

1

1

1

4

1

1

1

1

5

1

1

1

6

1

1

1

1

7

1

1

1

8

1

1

1

1

9

1

1

1

1

 
<<   СОДЕРЖАНИЕ   >>