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

Ташкентский Университет Информационных Технологий имени Мухаммад аль Хорезма
Вычисление чисел внутренней и внешней устойчивости

Выполнила студент 2-курса группы 813-20 ТРр

Тогаева Мукаддас


План:

1. 
   Внутренне устойчивое множество вершин.
   

2. Внешняя устойчивость.

3. 
   Основная идея алгоритма поиска минимального покрытия.
   

4. 
   Примеры.
   

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

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

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

Рядом с каждой вершиной получившегося уровня выписываем вершины, несмежные с ней, входящие в метку вершины-родителя на предыдущем уровне. Например, несмежными с вершиной 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} и др.

Вершины	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, это и есть число вершинной внешней устойчивости.
Ответ. є₀ = 3, (3₀ = 2.