Внутренняя устойчивость

Пусть G = (V, E) – ориентированный граф. Множество вершин U ⊂ V называется внутренне устойчивым, если U ∩ D (U) = ∅, т. е. в графе G не существует дуги, связывающей пару вершин из U. Внутренне устойчивое множество вершин U ⊂ V является максимальным, если при добавлении к нему хотя бы одной вершины оно перестает быть внутренне устойчивым.

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

Пусть G – ориентированный граф. Так же, как и в предыдущем пункте, перенумеровав его вершины, будем считать, что вершинами графа G служат числа 1, 2, …, n. Пусть A = (aij) – матрица смежности графа G. Для множества вершин U пусть (ui) – его характеристический вектор.

Множество вершин U внутренне устойчиво тогда и только

тогда, когда для любых i, j = 1, 2, …, n выполняется условие:

если ui = 1 и aij = 1, то uj = 0.

Иными словами, множество вершин U внутренне устойчиво,

если булево выражение

(ui ∧ aij) →  uj (3)

принимает значение 1 для всех i, j = 1, 2, …, n. В равносильной форме предыдущее условие можно представить так:

 ui ∨  aij ∨  uj =1

для всех i, j = 1, 2, …, n. Положим

n

f (U) 

∧( u

∨ a

∨ u

). (4)

i, j 1 i ij j

Множество U внутренне устойчиво в том и только том случае, когда f (U) = 1. Таким образом, булева функция (4) является характеристической функцией семейства внутренне устойчивых множеств в совокупности всех подмножеств множества вершин графа G. Те множители (конъюнктивные члены), в которых ai, j = 0, обращаются в единицу, поэтому их можно опустить.

С учетом этого получаем:

f (U) 

n

∧( u

∨ u).

i j aij 1

Представим функцию f (U) в виде ДНФ. Каждый дизъюнктивный член соответствует внутренне устойчивому множеству. Если в ДНФ входит элементарная конъюнкция uiuj … uk, то на множестве вершин { i, j, …, k } функция f принимает значение 0 и, значит, дополнение этого множества внутренне устойчиво. Проведя все сокращения в соответствии с тождествами

xx = x, x ∨ x = x, x ∨ (xy) = x, x (x ∨ y) = x,

мы получим ДНФ, в которой дизъюнктивные члены соответствуют максимальным внутренне устойчивым множествам.

Пример. Составим характеристическую функцию внутренне устойчивых множеств (2) для графа G, представленного на рис. 2:

f = ( u 1 ∨  u 4)( u 2 ∨  u 1)( u 2 ∨  u 3)( u 2 ∨  u 5)∧

∧( u 3 ∨  u 4)( u 5 ∨  u 1)( u 5 ∨  u 3)( u 5 ∨  u 4).

После раскрытия скобок и упрощений получаем

f =  u 1 u 2 u 3 u 4 ∨  u 1 u 3 u 5 ∨  u 2 u 4 u 5.

Следовательно, граф G обладает следующими максимальными внутренне устойчивыми множествами вершин:

{5}, {2, 4}, {1, 3}.

Ядро графа

Пусть G = (V, E) – ориентированный граф. Множество вершин N ⊂ V называется ядром, если оно одновременно внешне и внутренне устойчиво.

Примеры. Граф на рис. 2 обладает единственным ядром {2, 4}. Граф на рис. 3 ядер не имеет.

1

Рис. 3

Граф на рис. 4 имеет два ядра: {1, 3} и {2, 4}.

2 3

1 4

Рис. 4

Теорема. Множество вершин ориентированного графа является ядром тогда и только тогда, когда оно максимальное внутренне устойчивое и минимальное внешне устойчивое множество.

Предположим, что ориентированный граф G = (V, E) представляет некоторое отношение предпочтения. Более точно: множество вершин V – это множество вариантов (альтернатив); наличие дуги из x в y означает, что y «лучше», чем x. Для ситуаций выбора типично, когда известно, что значит «лучше», но не известно, что значит «хорошо». Ядро, которое называют решением задачи выбора по Нейману – Моргенштерну, это в

некотором смысле множество «хороших» вариантов. В соответствии с определением для каждого невыбранного варианта в ядре содержится вариант, который лучше него. Кроме того, если некоторый вариант попал в ядро, худшие, чем он, варианты в это ядро уже не попадут. В «простых» случаях ядро дает естественное решение задачи выбора. Так, если граф G не содержит циклов, а отношение предпочтения транзитивно, то единственным ядром графа G служит множество вершин уровня 0 (множество недоминируемых альтернатив). Ядро дает решение задачи выбора и в более сложных случаях.

Пример. Пусть имеются шесть вариантов {1, 2, 3, 4, 5, 6}, которые оцениваются по четырем критериям. Возможные оценки по каждому критерию: 0, 1, 2, 3, 4.

В следующей таблице приведены оценки вариантов.

Будем считать, что вариант x лучше варианта y, если x не содержит ни одной нулевой оценки и число показателей, по которым он лучше варианта y, больше, чем число показателей, по которым y лучше, чем x. На рис. 5 изображен

соответствующий граф предпочтений.

5 6

1 2

Рис. 5

Единственным ядром графа служит множество {2, 5}. Это и есть множество «хороших» вариантов. Чтобы сделать выбор

между вторым и пятым вариантом, требуется привлечь дополнительную информацию.

Пример. Граф на рис. 6 обладает двумя ядрами: {1, 5, 7}

и {2, 4, 6, 8}.

1 2

3 5

6 7 8

Рис. 6

Вопросы для итогового контроля

1. Множества

1. Понятие множества

2. Подмножества

3. Пересечение и объединение множеств

4. Разность множеств. Дополнение множества

5. Свойства операций над множествами

6. Диаграммы Эйлера – Венна

7. Прямое произведение множеств

2. Отображения и соответствия

1. Понятие отображения

2. Специальные виды отображений

3. Операции

4. Характеристические функции

5. Соответствия

6. Композиция соответствий

3. Отношения

1. Понятие отношения

2. Свойства бинарных отношений

3.Отношения эквивалентности

4. Натуральные числа

1. Натуральный ряд

2. Метод математической индукции

Не нашли, что искали? Воспользуйтесь поиском: