5.9. Внутренне и внешне устойчивые
МНОЖЕСТВА ВЕРШИН ГРАФОВ
При изучении и использовании моделей, систем, основанных на графах, оказываются полезными множества вершин, обладающие специальными свойствами. Некоторые характеристики вершин графов, такие, как связность или степень вершин, уже рассматривались ранее.
ОПРЕДЕЛЕНИЕ
Множество
E
вершин
графа G
=
(V,
U)
называется внутренне устойчивым, если
для любых двух вершин a
и b
из E
справедливо
соотношение (a,
b)
U.
Определение
Множество I вершин графа G = (V, U) называется внешне устойчивым, если для любой вершины a V \ I найдется такая вершина b I, что (a, b) U.
То есть всякое множество таких вершин графа, никакие две из которых не являются соседними, внутренне устойчивое.
Произвольное множество вершин графа считается внешне устойчивым, если всякая из остальных вершин графа является соседней хотя бы для одной вершины из этого множества.
В качестве примера рассмотрим граф, изображенный на рис. 5.26. a b c
g e
f
d
Рис. 5.26
В этом графе множества:
I = {a, d, c} внутренне устойчивое;
E = {d, e, c, f, g} внешне устойчивое;
K = {g, b, e} является одновременно как внутренне, так и внешне устойчивым.
Нетрудно видеть, что удаление элементов внутренне устойчивого множества вершин графа приводит к внутренне устойчивому множеству вершин. Добавление новых вершин к внешне устойчивому множеству вершин графа приводит к внешне устойчивому множеству вершин.
Определение
Числом внутренней устойчивости графа называется значение максимальной мощности для внутренне устойчивых множеств этого графа.
Число
внутренней устойчивости графа G
обозначается
как
(G).
Определение
Числом внешней устойчивости графа G называется значение минимальной мощности для внешне устойчивых множеств этого графа.
Число
внешней устойчивости графа G
обозначается как
(G).
Пример.
Для графа G,
изображенного на рис. 5.27.,
(G)=3
и
(G)=2.
Рис. 5.27.
В качестве примера использования введенных понятий рассмотрим две задачи:
определим максимальное количество ферзей, которые могут быть расставлены на шахматной доске так, чтобы ни один из них не находился под ударом другого ферзя.
найдем минимальное число ферзей, которые можно так расставить на шахматной доске, чтобы всякое поле доски находилось под боем хотя бы одного ферзя.
Представим шахматную доску графом, вершины которого соответствуют полям на доске, а ребра между вершинами указывают, что ферзь, стоящий на поле, соответствующем одной вершине, бьёт поле, соответствующее другой вершине.
Тогда первая задача состоит в нахождении значения (G) для графа G, представляющего шахматную доску.
Вторая задача заключается в нахождении значения (G) для того же графа.
ОПРЕДЕЛЕНИЕ
Множество K вершин графа G = (V, U) называется ядром этого графа, если оно является внутренне и внешне устойчивым.
Нетрудно видеть, что если K ядро графа G, то должно выполняться неравенство (G) |K| (G). Следовательно, условие (G) (G) является необходимым условием существования ядер графов.
Г
раф
G
может не иметь ни одного ядра. Например,
это так для графа на рис. 5.28.:
Рис. 5.28
Для графа G можно непосредственно определить, что (G) = 1 и (G) = 2. Поэтому для этого графа не выполнено необходимое условие существования ядер. Следовательно, граф G не имеет ядра.
ТЕОРЕМА 5.9
Всякий неориентированный граф без петель имеет ядро.
Доказательство
Проведем доказательство, определив процедуру построения ядра K для произвольного неориентированого графа G = (V, U), не имеющего петель.
1.
Положим K
=
.
2. Возьмем произвольную вершину v V, которая не является соседней с вершинами из K. Добавим v к множеству K.
3. Продолжаем процесс добавления вершин к множеству K до тех пор, пока в V имеются вершины, не являющиеся соседними с вершинами, включенными в K.
Так как множество V является конечным, то через конечное число шагов приведенная процедура заканчивает свою работу. При этом множество K является ядром графа G, поскольку по построению никакие две вершины из K не являются соседними, а всякая вершина из V \ K не может быть несоседней для хотя бы одной вершины из K.
Доказательство окончено.
Из рассмотренного выше примера следует, что в ориентированных графах ядра существуют не всегда.
Можно обобщить понятие ядра, при котором ориентированные графы, подобные графу на рис. 5.28., имеют обобщенные ядра.
Соответствующее обобщение состоит в ослаблении условий на множество вершин, образующих ядро.