ОПРЕДЕЛЕНИЕ. Множество K вершин графа G = (V, U) называется ядром этого графа, если оно является внутренне и внешне устойчивым

Множество K вершин графа G = (V, U) называется ядром этого графа, если оно является внутренне и внешне устойчивым.

Нетрудно видеть, что если K - ядро графа G, то должно выполняться неравенство (G) | K | (G). Следовательно, условие (G) (G) является необходимым условием существования ядер графов.

Граф G может не иметь ни одного ядра. Например, это так для графа на рис. 5.28.:

Рис. 5.28

Для графа G можно непосредственно определить, что (G) = 1 и (G) = 2. Поэтому для этого графа не выполнено необходимое условие существования ядер. Следовательно, граф G не имеет ядра.