Множина внутрішньої стійкості

Визначення. Множина SÍX графу G =<X, Г> називається внутрішньостійкою, якщо ніякі дві вершини з S не суміжні, тобто для будь-якого x_iÎS має місце Г(x_i)ÇS = Æ:

" x_i ÎS (Г(x_i)ÇS = Æ)

Множина внутрішньої стійкості, що містить найбільше число елементів, є найбільшою внутрішньостійкою множиною, а число елементів цієї множині називається числом внутрішньої стійкості графу.

Приклад. Два графи з різними числами внутрішньої стійкості

Рис. 17.4. Графи з числом внутрішньої стійкості два (ліворуч) і три (правіоруч)

Найменше число внутрішньої стійкості мають повні графи, максимальне число - нуль-графи.

Приклад. Числа внутрішньої стійкості повних і порожніх графів, що включають три і чотири вершини, відповідно рівні 1, 1, 3.

Рис. 17.5. Числа внутрішньої стійкості повних (1 – ліворуч і у центрі) і порожнього (3 – праворуч) графів