Пусть 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.
В следующей таблице приведены оценки вариантов.
Показатели
П1
П2
П3
П4
Варианты
Будем считать, что вариант x лучше варианта y, если x не содержит ни одной нулевой оценки и число показателей, по которым он лучше варианта y, больше, чем число показателей, по которым y лучше, чем x. На рис. 5 изображен
соответствующий граф предпочтений.
5 6
1 2
Рис. 5
Единственным ядром графа служит множество {2, 5}. Это и есть множество «хороших» вариантов. Чтобы сделать выбор
между вторым и пятым вариантом, требуется привлечь дополнительную информацию.
Пример. Граф на рис. 6 обладает двумя ядрами: {1, 5, 7}