Занятие 6: Правильные раскраски графов



Скачать 26.23 Kb.
Дата08.10.2012
Размер26.23 Kb.
ТипЗанятие

Занятие 6: Правильные раскраски графов


Определение. Раскраска вершин графа правильная, если концы каждого ребра – разного цвета. Граф называется k-раскрашиваемым, если его можно правильно в k цветов. Если граф k-раскрашиваемый граф G не (k–1)-раскрашиваем, то назовем его k-хроматическим, а число k назовем хроматическим числом графа и обозначим k(G).

Упр1. Найдите хроматические числа а) Kn – полного графа с n-вершинами; б) Cn – цикла с n–вершинами; в) графа Петерсена (см. рис).

Упр2. а) Найдите все 1-хроматические графы.

б) Какие из двудольных графов являются 2-хроматическими?

Определение. Подграф – это подмножество вершин графа и все соединяющие их ребра графа. Подграф, изоморфный полному графу, называется кликой, а пустому антикликой. Число вершин наибольшей клики называется плотностью, а наибольшей антиклики – неплотностью графа.

Упр3. Найдите плотности и неплотности графов а) Kn; б) Cn; в) графа Петерсена.

Упр4. Докажите, что

а) хроматическое число графа не меньше хроматического числа подграфа;

б) хроматическое число не меньше плотности;

в) число вершин графа не превосходит произведения неплотности на хроматическое число.

Зад5. В булке запечен изюм двух сортов. Докажите, что внутри булки найдутся две такие точки на расстоянии 1 см, что они либо не принадлежат никаким из изюмин, либо принадлежат изюминам одного сорта.

Зад6. На шахматной доске стоят несколько королей. Докажите, что их можно раскрасить в 4 цвета так, чтобы короли одинакового цвета друг друга не били.

Пред7. Если наибольшая из степеней вершин графа равна p, то граф (p+1)-раскрашиваем.

Зад8. а) В каждой из клеток шахматной доски провели диагональ. Доска разбилась на треугольники. Докажите, что их можно раскрасить в 4 цвета так, что треугольники с общей стороной будут разного цвета. б) Докажите, что треугольники можно правильно раскрасить и в 3 цвета.

Зад9. Если наибольшая из степеней вершин связного графа равна p, и есть вершина степени <p, то граф p-раскрашиваем.

Пред 10. Пусть наибольшая из степеней вершин связного графа равна p, и в нем есть три такие вершины A, X, B, что AX и BX – ребра, AB – не ребро, и при выкидывании A и B получается связный подграф. Тогда граф p-раскрашиваем.

Теорема.
(Брукс 1941) Пусть G – связный граф, наибольшая из степеней вершин которого равна p. Тогда граф p-раскрашиваем за кроме случаев, когда G – полный граф с (p+1)-й вершиной или цикл нечетного порядка.

Указание. Покажите, что G удовлетворяет условию зад.9 или пред.10.

Интернет-кружок 11 класса, 1543 школа. Рук. А.Шаповалов sasja@shap.homedns.org. 15 октября 2010 г.

Для самостоятельного решения


РГ1. Найдите примеры p-хроматических графов, у которых каждый подграф с меньшим числом вершин (p–1)-раскрашиваем.

РГ2. Каждую грань куба 3×3×3 разбили на 3 прямоугольника 3×1 так, что на каждом ребре куба одна длинная сторона граничит с тремя короткими. В какое наименьшее число цветов можно раскрасить 18 полученных прямоугольников, чтобы любые два прямоугольника с общим куском границы были разного цвета?

РГ3. а) Все точки плоскости раскрашены в 2 цвета. Докажите, что найдутся две одинаково окрашенные точки на расстоянии 1;

б) то же, если плоскость раскрашена в 3 цвета.

РГ4. Остров Толпыго имеет форму многоугольника. На нем расположено несколько стран, каждая из которых имеет форму треугольника, причем каждые две граничащие страны имеют целую общую сторону (т.е. вершина одного треугольника не лежит на стороне другого). Докажите, что карту этого острова можно так раскрасить тремя красками, чтобы каждая страна была закрашена одним цветом и любые две граничащие страны были раскрашены в разные цвета.

РГ5. Расположите на плоскости 11 одинаковых квадратов так, чтобы получилась не 3-раскрашиваемая карта.

Интернет-кружок 11 класса, 1543 школа. Рук. А.Шаповалов sasja@shap.homedns.org. 15 октября 2010 г.

Похожие:

Занятие 6: Правильные раскраски графов iconТеория графов и ее приложения
Основные понятия. Графы неориентированные и ориентированные. Способы задания графов. Матрицы смежности и инцидентности графа. Понятие...
Занятие 6: Правильные раскраски графов iconМетодические указания к самостоятельным и семинарским занятиям по теории графов Москва 2006
Предназначены для решения задач по теории графов как при самостоятельном изучении теории графов, так и при решении задач на семинарах...
Занятие 6: Правильные раскраски графов iconО методе раскраски одной задачей. (Д. Ю. Кузнецов)
На математических олимпиадах часто встречаются задачи, решаемые методом раскраски. Ознакомимся с этим методом, продемонстрировав...
Занятие 6: Правильные раскраски графов iconПрограмма наименование дисциплины: Теория конечных графов
Основной целью освоения дисциплины является изучение классической теории конечных графов, а также применение методов теории конечных...
Занятие 6: Правильные раскраски графов icon20. Правильные многогранники и их симметрия
По аналогии с правильными плоскими фигурами многоугольниками в пространстве определяют правильные многогранники: многогранник называется...
Занятие 6: Правильные раскраски графов iconПрограмма наименование дисциплины: Теория конечных графов
Цели и задачи дисциплины: Основной целью освоения дисциплины является изучение классической теории конечных графов, а также применение...
Занятие 6: Правильные раскраски графов iconПрограмма дисциплины «теория графов»
Таким образом, теория графов стала существенной частью математического аппарата кибернетики, языком дискретной математики. В значительной...
Занятие 6: Правильные раскраски графов iconПрименение различных инвариантов графов к проверке изоморфизма некоторых видов графов
Мельникова Е. А., Сайфуллина Е. Ф. Применение различных инвариантов графов к проверке изоморфизма некоторых видов графов. // Проблемы...
Занятие 6: Правильные раскраски графов iconВопросы к экзамену Основные понятия теории графов (определение графа, виды графов, смежность, инцидентность, кратность ребер, степень вершины). Примеры
Способы задания графов. Матричный способ задания. Свойства матриц смежности и инцидентности. Привести примеры
Занятие 6: Правильные раскраски графов iconРабочая программа дисциплины (модуля) Теория графов Направление подготовки
Целями освоения дисциплины (модуля) «Теория графов» являются получение теоретических знаний по основам теории графов
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org