Внутренние устойчивые множества вершин графа.

Подмножества x(in) множества х вершин, графа G(X) называется внутренне устойчивым, если вершины множества x(in) не соединены ребрами. В противном случае неуст. Множество называется максимальным внутренне устойчивым, если оно становится внутренне неустойчивым при добавлении любой вершины.

Пример {x1,x3,x5},{x2.x5}- внутр. уст.

{x1,x3,x5}- максимальное внутрен.уст

{x1,x3}- просто внутр. Устр

Любое внутреннее устойчивое множество вершин графа содержится в некотором максимальном внутр. устр. Максимальных несколько.

Не особо важное определение, но можно написать:

Числом внутренней устойчивостиa (G) графа G(X) называется максимально число из чисел |x(in)|, x(in) –внутр.устр.множества, |x(in)| - число элементов множества x(in), те a(G)=max|x(in)|,1£a(G)£n

Хроматическое число и число внутр. устойчивости, графа G(X)связаны следующим неравенством:

a (G) ×n (G) ³ n = | x|

Доказательство. Пусть n (G) - хроматическое число графа G(X). Тогда множества вершин можно разбить на g (G) внутренне устойчивых множеств.

Образованных вершинами одинакового цвета. Если mi - число элементов

таких множеств, то mi =a (G). Откуда = åmi£n(G)×a(G)

Задача о четырех красках.

Подмножества множества х вершин, графа G(X) называется внутренне устойчивым, если вершины множества не соединены ребрами. В противном случае неуст. Множество называется максимальным внутренне устойчивым, если оно становится внутренне неустойчивым при добавлении любой вершины.

Пример (x₁,x₃,x₅), (x₂,x₅) - внутр. уст.

(x₁,x₃,x₅) - максимальное внутрен.

уст. (x₁,x₃) - просто внутр. устр.

Любое внутреннее устойчивое множество вершин графа содержится в некотором максимальном внутр. устр. Максимальных несколько.

Числом внутренней устойчивости (G) графа G(X) называется

максимально число из чисел | |, - внутр. устро. множества, | | - число элементов множества , т.е. (G) = max | |, 1≤ ≤n

Гипотеза четырех красок.

Достаточно ли четырех цветов для раскраски любой карты?

В 1890 году Хейвуд доказал, что достаточно пяти цветов.

Недавно американские математики Аппель и Хакон доказали гипотезу о четырех красках, существенно использовав ЭВМ. Таким образом для раскраски карты достаточно четырех красок. Для этого необходимо правильно подобрать внутренне устойчивые множества Вершин графа.

17. Задача Рамсея.

Доказать, что среди любых шести человек найдутся либо трое попарно незнакомых, либо трое попарно знакомых.

Отношение «быть знакомым» изобразим связывая вершин ребрам. Тогда три попарно знакомых образуют треугольник. В G – нет, Δ- ков, - есть.

Доказательство. Пусть - произвольная вершина графа шестью вершинами.

Подберем три другие вершины графа G с которыми связан с ребром. Если нет таких и каждая вершина соединена только двумя другими вершинами, то такие вершины найдутся в и рассмотрим дополнение. Если при этом u 1, u 2, u 3 не соед. ребром то они незнакомы, если есть хотя бы одно ребро то найдутся три знакомых. Теория доказана.