Правильная раскраска вершин графов.

Раскраской вершин графа называется назначение цветов его вершинам. Обычно цвета - это числа . Тогда раскраска является функцией, определенной на множестве вершин графа и принимающей значения в множестве . Раскраску можно также рассматривать как разбиение множества вершин , где - множество вершин цвета . Множества называют цветными классами. Раскраска называется правильной, если каждый цветной класс является независимым множеством. Иначе говоря, в правильной раскраске любые две смежные вершины должны иметь разные цвета. Задача о раскраске состоит в нахождении правильной раскраски данного графа в наименьшее число цветов. Это число называется хроматическим числом графа и обозначается . В правильной раскраске полного графа все вершины должны иметь разные цвета, поэтому . Если в каком-нибудь графе имеется полный подграф с вершинами, то для раскраски этого подграфа необходимо цветов. Отсюда следует, что для любого графа выполняется неравенство . 42.Раскраска планарных графов. Граф называется плоским, если никакие два его ребра не пересекаются. Граф называется планарным, если он изоморфен некоторому плоскому графу. Любой планарный граф допускает плоское представление, в котором все ребра являются отрезками. Любой граф укладывается в трехмерном пространстве , т.е. любой граф можно изобразить в трехмерном пространстве так, чтобы его ребра не пересекались.Достаточно ли 4 х красок для такой раскраски произвольной географической карты при которой 2-е ее соединение страны имеющим общую границу окрашены в различные цвета. Картой назыв связный плоский мультиграф без мостов. грани имеющие общее ребро называются смежными тогда функция раскраски для граней ставит в соответствие каждой внутренней грани число — цвет грани. Карта назыв К раскрашиваемой если для нее существует правильная К раскраска, т.е. такая что - смежные вершины. всякая карта 4-х раскрашиваемая (всякий планарный граф и раскрашиваемая) Т.о всякий планарный граф 5-ти раскрашиваемый.

Принцип Дирихле.

Самая популярная формулировка принципа Дирихле такова: «Если в n клетках сидит m зайцев, причем m > n, то хотя бы в одной клетке сидят по крайней мере два зайца». На первый взгляд даже непонятно, почему это совершенно очевидное замечание является весьма эффективным методом решения задач. Дело в том, что в каждой конкретной задаче нелегко бывает понять, что же здесь «зайцы» и «клетки» и почему зайцев больше, чем клеток. Выбор зайцев и клеток часто неочевиден; далеко не всегда по виду задачи можно определить, что следует воспользоваться принципом Дирихле. А главное, этот метод дает неконструктивное доказательство (мы, естественно, не можем сказать, в какой именно клетке сидят два зайца, а знаем только, что такая клетка есть), а попытка дать конструктивное доказательство, т. е. доказательство путем явного построения или указания требуемого объекта, может привести к гораздо большим трудностям. Некоторые задачи решаются также методами, в какой-то мере аналогичными принципу Дирихле. Сформулируем соответствующие утверждения (все они легко доказываются методом от противного).

а) Если на отрезке длиной 1 расположено несколько отрезков. сумма длин которых больше 1, то по крайней мере два из них имеют общую точку.

б) Если на окружности радиуса 1 расположено несколько дуг, сумма длин которых больше 2, то по крайней мере две из них имеют общую точку.

в) Если внутри фигуры площадью 1 расположено несколько фигур, сумма площадей которых больше 1, то по крайней мере две из них имеют общую точку.

44.Сущность теории Рамсея. Теорема Рамсея. Числа Рамсея.

Теорема Рамсея гарантирует существование чисел Рамсея для любых k и m. Таким образом можно говорить о содержании в бесконечном графе высокоорганизованной структуры любой сложности. Но об этом позже (быть может). А пока хочется остановиться на числах Рамсея. Для удобства перефразируем определение: Число Рамсея R(k, m) это наименьшее число n такое, что в любом полном графе с n вершинами, ребра которого раскрашены в красный и синий цвета, найдется либо подграф с k вершинами, все ребра которого окрашены в красный цвет, либо подграф с m вершинами, все ребра которого окрашены в синий цвет. Чтобы понять сложность вычисления чисел Рамсея, то следует отметить что число R(5, 5) до сих пор не найдено. Можно заметить три очевидных факта, касающихся чисел Рамсея:
1. R(k, m) = R(m, k)
2. R(1, m) = 1
3. R(2, m) = m
Остальные числа вычисляются индивидуально.

Приложение теоремы Рамсея. Теорема Ван дер Вардена.

Головоломка о вечеринке представляет собой задачу, типичную для приложений теории Рамсея. Какое количество людей достаточно для того, чтобы образовать группу, в которой всегда окажется либо четверо людей знакомых друг с другом, либо четверо, друг с другом незнакомых? На этом рисунке гости представлены точками. Каждое красное ребро на этом графе соединяет гостей, знакомых друг с другом, а каждое синее — незнакомых. В группе из 17 точек, изображённых на рисунке, невозможно найти четыре точки для которых сеть соединяющих их рёбер была бы целиком красной или целиком синей Поэтому требуется более 17 человек, чтобы среди них обязательно оказалось либо четверо знакомых, либо четверо незнакомых друг с другом. На самом деле во всякой группе из 18 человек всегда найдутся либо четверо знакомых, либо четверо незнакомых друг с другом. Если множество всех натуральных чисел любым способом разбито на конечное число классов, то хотя бы один из этих классов содержит сколь угодно длинную арифметическую прогрессии.

Этот удивительный по простоте формулировки и очень нетривиальный по доказательству результат выдающийся российский математик и педагог Александр Яковлевич Хинчин (19.07.1894-18.11.1959) назвал одной из жемчужин теории чисел. Знаменитая теорема Ван дер Вардена утверждает, что для любых натуральных чисел n> 2, r> 1 найдется такое минимальное натуральное число W(n, r), что в любой раскраске множества натуральных чисел {1,..., W(n, r)} в r цветов найдется одноцветная арифметическая прогрессия длины n. Величину W(n, r) из теоремы Ван дер Вардена принято называть функцией Ван дер Вардена.

1 2 34