Теорема (верхняя оценка): если граф G имеет максимальную степень вершины, равную S, то хроматическое число χ(G) ≤ S+1.

Доказательство: Индукцией по числу p вершин.
Базис: Если число вершин в графе G не превосходит S+1, то Теорема тривиально справедлива, ибо S+1 вершин можно правильно раскрасить в S+1 цветов. По 1-му цвету на каждую вершину.

Предположение индукции: Допустим, что Теорема верна для графа с числом вершин k < p, причем p ≥ S+1 Шаг индукции: Покажем, что если граф G имеет p вершин, то хроматическое число χ(G) ≤ S+1. Пусть v произвольная вершина в G. Удалим из G вершину v вместе с ее ребрами. Получившийся граф G’ = G –v имеет число вершин k < p ⇒ по предположению индукции граф G’ S+1 раскрашиваем. В графе G вершина v имеет не более, чем S соседних вершин, окрашенных в не более, чем S красок. Сопоставим вершине v одну из оставшихся красок, тогда граф G правильно раскрашиваем числом красок r ≤ S+1, т.е. граф G имеет хроматическое число χ(G) ≤ S+1.

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

Определение: Подмножество S вершин графа G = (V,E) называется внутренне устойчивым, если какие-либо две вершины из S не смежны в G (не есть соседние в G). Число внутренней устойчивости графа G α(G) = max {|S|:S⊆V и S внутренне устойчиво в G}.

Определение: Внутренне устойчивое множество вершин S называется максимальным (тупиковым), если всякое собственное надмножество множества S внутренне устойчивым уже не является. Внутренне устойчивое множество S называется наибольшим, если среди всех внутренне-устойчивых множеств вершин в G оно имеет наибольшую мощность.

Алгоритм вычисления всех наибольших внутренне устойчивых множеств вершин графа G = (V,E)
1) Построить функцию F = &_(u,v)∈E(x_u ∨ x_v) – условие внутренней устойчивости вершин графа G.
2) Раскрыв скобки в F и проведя поглощение, получить минимальную ДНФ D для F.
3) Для каждого дизъюнктивного слагаемого K = x_u, x_v,…,x_w в D получить ему соответствующее максимальное внутренне устойчивое множество вершин S = V – {u, v,…,w}
4) Из полученных максимальных внутренне устойчивых множеств вершин выбрать все наибольшие по мощности.

Теорема (нижняя оценка): Пусть G = (V,E) есть связанный (p,q)-граф. Пусть α(G) – есть число внутренней устойчивости графа G. Тогда хроматическое число χ(G) ≥ p /α(G).

Доказательство: Граф G χ(G)-раскрашиваем. Пусть V₁,V₂, …,V_χ(G) – множество вершин окрашиваемых в 1,2,3.., χ(G) цвета соответственно. Вершины из V_i – внутренне устойчивы, ибо окрашены в один и тот же цвет и потому не могут быть соседними. Тогда мощность |V_i| ≤ α(G) i =1,2,..,χ(G). Множества V₁, V₂, …,V_χ(G) попарно не пересекаются и в сумме дают все множество V. Тогда число вершин p = ∑_i=1…χ(G)|V_i| ≤ ∑_i=1…χ(G)α(G) = χ(G)*α(G) =>
χ(G) ≥ p/ χ(G)

Замечание: Из теорем о верхней и нижней оценках для хроматического числа χ(G) графа G получаем:
Нижняя – p/α(G) ≤ χ(G) ≤ S+1 – верхняя.

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

Определение: Множество T вершин графа G = (V,E) называется внешне-устойчивым в G, если ∀v∉T ∃u∈T (e = (u,v) ∈ E). Число внешней устойчивости графа G: β ∈G = min{|T|: T ⊆ V и Т – внешне-устойчивое множество вершин в G}

Определение: Внешне-устойчивое множество T называется минимальным (тупиковым), если Т не содержит в себе подмножеств, являющихся внешне устойчивыми. Внешне-устойчивое множество вершин называется наименьшим, если среди всех внешне-устойчивых множеств вершин в G оно имеет наименьшую мощность.

Замечание: Внешне устойчивое множество вершин связано со следующей практической задачей. Пусть есть карта городов и дорог между ними. Нужно построить наименьшее число складов не более, чем по 1ому складу в городе с прямой дорогой из каждого города к одному из складов.

Пусть Т есть внешнее устойчивое множество вершин графа G = (V,E), с каждой вершиной u∈V свяжем логическую переменную x_u и пусть x_u означает u∈T.

Алгоритм вычисления всех наименьших внешне-устойчивых множеств вершин в графе G = (V,E)
1) Построить формулу F = &_u∈V(x_u ∨ ( ∨_(u,v)∈Ex_v) – условие внешней устойчивости графа G.
2) Построить мин ДНФ в D для формулы F.
3) Для каждого дизъюнктивного слагаемого k = x_u, x₂, …,x_w получить минимальное внешне-устойчивое множество вершин Т = {u,v,..,w}
4) Из полученных минимальных внешне-устойчивых множеств выбрать все наименьшие.

Комментарии запрещены.