§ 31. Ядра графа

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

Отсюда следует, что ядро содержит всякую вершину и не содержит вершин с петлями. Очевидно, что 0 не есть ядро графа.

Граф может обладать несколькими ядрами или вообще не иметь ядра.

Например, подмножество ядро графа на рис. 126, а ядро графа на рис. 127.

Отыскание ядер графа. Метод Магу. Полагаем если и рассмотрим уравнения из (30 11) и (30.25) соответственно. Так как эти равенства должны выполняться, то

или

Пример (рис. 120). Для этого графа вычислены ранее (см. (30.15) и Итак, находим

Рис. 126.

Рис. 127.

(замечая, что

Итак, граф обладает двумя ядрами:

Свойства ядер графа. Эти свойства будем рассматривать в виде теорем.

Теорема Пусть задан граф Ядро графа есть максимальное внутренне устойчивое подмножество.

Предположим, что собственное подмножество максимального внутренне устойчивого множества А. Тогда существует вершина Следовательно, Отсюда следует, что А не является внутренне устойчивым подмножеством, вопреки предположению. Итак, совпадает с А.

Теорема II. Пусть задан симметрический граф без петель. Тогда любое максимальное внутренне устойчивое подмножество является ядром

Рассмотрим максимальное внутренне устойчивое подмножество Требуется показать, что для произвольной вершины

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

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

Пусть граф имеет ядро. Как мы видели раньше (см. (31.3)), условие

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

Рис. 128.

Пусть некоторые одночлены из соответственно. Если выполнено (31.9), то

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

Обратно, пусть задано подмножество, являющееся одновременно максимальным внутренне устойчивым и минимальным внешне устойчивым. Тогда для соответствующих переменных, связанных с его элементами, выполняется соотношение е. это подмножество — ядро графа.

Теорема IV. Для ядра графа выполняется неравенство

Это следует из определения ядра.

Теорема Если граф допускает функцию Гранди то подмножество

— ядро графа.

В самом деле, вершины, для которых удовлетворяют условиям (30.1) и (30.17).

Например, подмножество ядро графа на рис. 128 (функция Гранди этого графа построена ранее (см. рис.

Теорема VI. Симметрический граф без петель всегда допускает ядро.

Это — следствие теоремы II.

Теорема VII. Рассмотрим булеву функцию на множестве А:

Условие

необходимо и достаточно для того, чтобы А было ядром графа

При этом полагаем

Необходимость. В самом деле, если А — ядро, то в силу внутренней устойчивости

а в силу внешней устойчивости

т. е. имеем (31.14).

Достаточность. Действительно, из (31.14) для А имеем

т. е. А — ядро.

Теорема может быть также доказана с помощью метода Магу для нахождения ядер.

Теорема VIII. Граф без контуров всегда обладает ядром. Для такого графа существует порядковая функция, а значит, функция Гранди и, следовательно, ядро (теорема V).

Теорема IX (Ричардсон). Граф, не имеющий контуров не четной длины, допускает ядро.

Доказательство приведено в [8], стр. 56.

УПРАЖНЕНИЯ

(см. скан)