WikiSort.ru - Не сортированное

Общие тривиальные оценки

Числом независимости ${\displaystyle \alpha (G)}$ называется размер максимально независимого множества вершин в графе ${\displaystyle G}$ . Определение раскраски означает, что ${\displaystyle \alpha (G)}$ определяет максимальное количество вершин, которое можно покрасить в один цвет. Исходя из некоторой модификации принципа Дирихле, хроматическое число графа можно оценить как ${\displaystyle \chi (G)\geq {\frac {|V|}{\alpha (G)}}}$

Аналогично определяется кликовое число ${\displaystyle \omega (G)}$ как размер максимальной клики. Это число даёт оценку ${\displaystyle \chi (G)\geq \omega (G)}$

Как правило, первая оценка лучше второй — а именно, для случайного графа ${\displaystyle G}$ на ${\displaystyle n}$ вершинах вероятность того, что ${\displaystyle \alpha (G)<2\log _{2}{n}}$ стремится к единице с растущим ${\displaystyle n}$ . Из того, что каждой клике графа ${\displaystyle G}$ можно сопоставить независимое множество графа ${\displaystyle \not G}$ , можно заключить, что то же самое верно для ${\displaystyle \omega (G)}$ .

Однако кнезеровский граф даёт наглядную иллюстрацию целого класса графов, дискредитирующих изложенные выше оценки (в общем случае, а не для случайных графов).

Кликовое число

Не ограничивая общности предположим, что ${\displaystyle \{1,\dots ,k\}}$ входит в клику как вершина. Тогда, из определения клики, ни одна другая вершина не должна содержать в своём подмножестве ни один элемент из ${\displaystyle \{1,\dots ,k\}}$ . При дальнейшем аналогичном анализе это очевидным образом даёт ${\displaystyle \omega (KG_{n,k})=\left\lfloor {\frac {n}{k}}\right\rfloor }$

Число независимости

Из комбинаторных соображений очевидно, что ${\displaystyle \alpha (KG_{n,k})\geq {\binom {n-1}{k-1}}}$ . Для построения независимого множества такого размера достаточно зафиксировать одну вершину и перебрать все ${\displaystyle k}$ -элементные подмножества, содержащие её. По определению, между любой парой таких множеств не будет ребра.

Эрдёш, Ко и Радо в 1961 году опубликовали доказательство теоремы, утверждающей равенство в изложенной выше оценке. По словам математиков, они нашли доказательство ещё за несколько десятилетий до этого, но в то время его не имело смысла публиковать, потому что теорема была никому неинтересна. К слову, граф Кнезера в то время ещё не был известен, так что Эрдёш, Ко и Радо доказывали теорему в элементарной формулировке максимального количества попарно пересекающихся ${\displaystyle k}$ -элементных подмножеств ${\displaystyle n}$ -элементного множества.

Пользуясь тривиальной оценкой, из данного значения числа независимости можно получить только ${\displaystyle \chi (KG_{n,k})\geq {\frac {\binom {n}{k}}{\binom {n-1}{k-1}}}={\frac {n}{k}}}$ , то есть ${\displaystyle \chi (KG_{n,k})\geq \left\lceil {\frac {n}{k}}\right\rceil }$ . Эта оценка почти не отличается от оценки через кликовое число.

Точное значение

Сформулированная в 1955 году Мартином Кнезером и доказанная в 1977 году Ласло Ловасом теорема утверждает, что ${\displaystyle \chi (KG_{n,k})=n-2k+2}$