Анализ графов на ЭВМ. Методические указания. Макарычев П.П - 21 стр.

                             Лабораторная работа №6
      ВНЕШНЯЯ УСТОЙЧИВОСТЬ И ПОКРЫТИЯ В ГРАФАХ
      Цель      работы       —      исследование        внешней      устойчивости
ориентированных        и      неориентированных          графов,     приобретение
практических навыков исследования структур технических систем.
                       Основные понятия и определения
      Подмножество вершин S графа G = (V,U) называется доминирующим
(внешне устойчивым), если каждая вершина из V — S смежна с некоторой
вершиной из S. Другими словами, каждая вершина графа находится на
расстоянии     не    более     единицы          от   доминирующего     множества.
Доминирующее        множество      называется        минимальным,    нет   другого
доминирующего        множества,     содержащегося        в   нем.   Минимальных
доминирующих множеств в графе может быть несколько, и они не
обязательно содержат одинаковое количество вершин. Минимальное
доминирующее множество, имеющее наименьшую мощность называется
наименьшим.
      Подмножество         вершин         графа,     являющееся     одновременно
независимым и доминирующим, называется ядром графа.
      Понятие доминирующего множества переносится и на случай
ориентированных графов. Подмножество S вершин орграфа называется
доминирующим, если для любой вершины v j ∈V − S существует такая

вершина      v j ∈ S , что (vi , v j ) ∈ A где А - множество дуг орграфа

Подмножество вершин S, являющееся одновременно и независимым, и
доминирующим называется ядром орграфа. Например, орграф на рис. 8, а
имеет два ядра S1 = {1,3}; S 2 = {2,4}.
      Орграф, изображенный на рис. 8, б, не имеет ядра.




                                           21