Верхние и нижние оценки хроматического числа
Версия от 17:08, 13 января 2016; 5.18.163.38 (обсуждение)
Содержание
Верхняя оценка длиной максимального нечетного цикла
Лемма (оценка хроматического числа длиной максимального нечётного цикла): |
Пусть — произвольный связный неориентированный граф и — длина максимального простого цикла графа , . Тогда, . |
Доказательство: |
Опишем на графе следующий алгоритм раскраски:
Докажем от противного, что после выполнения описанного алгоритма граф Таким образом в графе будет правильно раскрашен. Предположим, что после выполнения алгоритма покраски в графе существует ребро, соединяющее вершины одного цвета. Пусть — цвет вершины после выполнения алгоритма раскраски.Заметим, что для произвольной вершины графа , , .Тогда, .Поскольку в дереве dfs между вершинами находящимися на одинаковом расстоянии от корня нет перекрестных ребер, то . То есть, вершины лежат на простом цикле длины по крайней мере . Получается противоречие с условием потому, что длина максимального простого цикла получается больше чем . после выполнения алгоритма раскраски нет вершин одного цвета соединенных ребром и при этом каждая вершина покрашена в один из , то есть правильно раскрашен в цвет, следовательно |
Нижняя оценка числом независимости
Определение: |
Подмножество | вершин графа называется независимым, если любые две вершины из не смежны в
Определение: |
Число независимости | графа — и независимо в G
Лемма (нижняя оценка): |
Пусть — произвольный связный неориентированный граф с вершинами .Тогда, . |
Доказательство: |
Пусть, Заметим, что для произвольного множеств вершин окрашенных в соответствующие цвета при правильно покраски графа .Каждое из — независимое множество (поскольку вершины множества покрашены в один цвет при правильной покраски графа , следовательно, они попарно не смежны внутри множества ). , (т.к независимое множество). То есть, , следовательно . |
Верхняя оценка количеством ребер
Лемма (верхняя оценка): |
Пусть — произвольный связный неориентированный граф с ребрами.Тогда, . |
Доказательство: |
Пусть, Тогда, множеств вершин окрашенных в соответствующие цвета при правильно покраски графа . Заметим, что между любыми двумя различными множествами существует хотя бы одно ребро (в противном случаи эти множества можно было бы покрасить в один цвет). . |
Нижняя оценка количеством ребер и количеством вершин
Лемма (нижняя оценка Геллера): |
Пусть — произвольный связный неориентированный граф с вершинами и ребрами. Тогда, . |
Доказательство: |
Пусть, множеств вершин окрашенных в соответствующие цвета при правильно покраски графа . . |