Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Инфоурок / Математика / Конспекты / Урок "Раскраски графов" (9 класс)

Урок "Раскраски графов" (9 класс)

Самые низкие цены на курсы профессиональной переподготовки и повышения квалификации!

Предлагаем учителям воспользоваться 50% скидкой при обучении по программам профессиональной переподготовки.

После окончания обучения выдаётся диплом о профессиональной переподготовке установленного образца (признаётся при прохождении аттестации по всей России).

Обучение проходит заочно прямо на сайте проекта "Инфоурок".

Начало обучения ближайших групп: 18 января и 25 января. Оплата возможна в беспроцентную рассрочку (20% в начале обучения и 80% в конце обучения)!

Подайте заявку на интересующий Вас курс сейчас: https://infourok.ru/kursy

  • Математика

Поделитесь материалом с коллегами:

Урок «Раскраски графов»

факультативного курса «теория графов и их приложения» (9 класс)


Одной из наиболее интересных задач теории графов, с которой необходимо знакомить школьников, является задача о раскрасках вершин графа. На практике к этой задаче сводятся такие проблемы как составление расписаний занятий в учебном заведении, распределение оборудования на предприятии, выбор расцветки проводов при монтаже электрооборудования автомобиля и многие другие. Классической задачей о раскраске графа, с помощью которой хорошо демонстрируется суть проблемы, является задача о раскраске политической карты мира. Имеется карта мира, с нанесенными границами между государствами (фрагмент такой карты представлен на рис. 1, для удобства цвета обозначены буквами: Ж – желтый, С – сиреневый, З - зеленый). Каждое государство необходимо раскрасить в определенный цвет так, чтобы граничащие с ним государства были окрашены в различные цвета – для того, чтобы они были хорошо заметны на карте. Количество используемых красок для раскраски всей карты должно быть минимальным. Очевидно, что при такой постановке проблемы государства, не граничащие между собой, могут быть окрашены в один и тот же цвет (рис. 1,б).

F:\Все, что было на ноуте\Дипломники\2014-2015\Моторина\Раскраски графов\Статья\Карта.png

Рис. 1. Фрагмент политической карты мира (а – не раскрашенный, б – раскрашенный)


Представим карту посредством графа (рис. 2). Таким образом, раскраской вершин неориентированного графа G называется такое задание цветов вершинам, что если hello_html_7e9b910b.gif – ребро, то вершины v1 и v2 имеют различные цвета (рис. 2,б). Такую раскраску называют правильной.

F:\Все, что было на ноуте\Дипломники\2014-2015\Моторина\Раскраски графов\Статья\Карта (цвет с графом).png

Рис. 2. Представление карты (а) графом (б)


Минимальное число цветов, требующихся для раскраски графа, называют хроматическим числом. Обычно его обозначают χ(G).

Возникает вопрос, а сколько существует способов раскраски графа при определенном наборе красок? На этот вопрос дает ответ хроматический полином графа. Русский синоним слову полином – многочлен. Если в это математическое выражение подставить число красок, то можно легко вычислить количество способов раскраски. Но сложность состоит в составлении хроматического полинома. Довольно легко хроматический полином определяется для пустых и полных графов. Напомним, что пустым графом (его обозначают On) называется граф, не имеющий ни одного ребра – в нем есть только вершины (рис. 3,а). Полный же граф (его обозначают Kn) наоборот, имеет связи между всеми вершинами – они соединены ребрами друг с другом (рис. 3,б)

C:\Users\WhiteRabbit\Desktop\Раскраски графов\Пустой и полный граф.png

Рис. 3. Пустой (а) граф O5 и полный (б) граф K5


Вершины пустого графа раскрашиваются независимо – ведь они не связаны между собой ребрами. Они могут быть окрашены в различные цвета или в один и тот же цвет, неважно. Поэтому хроматический полином пустого графа является числом всевозможных комбинаций от числа цветов и определяется как (1):

hello_html_16ec240f.gif,

(1)

где x – число цветов, а n – число вершин графа.

Сложнее с полными графами – все их вершины могут быть раскрашены только в различные цвета, но и здесь число различных комбинаций довольно велико. Эта формула и все дальнейшие утверждения здесь будут приведены без выводов и доказательств – они довольно сложны и заинтересованный читатель может ознакомиться с ними самостоятельно в специальной литературе. Итак, хроматический полином полного графа определяется как (2):

hello_html_m57a9f40b.gif

(2)

Такое выражение иногда называют факториальной степенью числа.

Возникает вопрос, а как же быть с графами, которые не являются полными или пустыми? Есть ли какие-нибудь методы получения их хроматических полином? На этот вопрос следует ответить утвердительно – такие методы есть. Одним из таких методов, который базируется на знании хроматических полином для пустых и полных графов является метод хроматической редукции. В данном случае слово редукция означает приведение сложного к простому, или разложение сложного на простые части. Как нетрудно догадаться для получения хроматического полинома графа, нам необходимо будет свести его к сумме (или разности) полиномов пустых или полных графов.

Для применения метода хроматической редукции необходимо ознакомиться с двумя утверждениями, доказательство которых мы приводить не будем.

Утверждение, являющееся основой для хроматической редукции по полным графам, звучит так: хроматический полином графа может быть представлен суммой хроматических полиномов двух графов и имеет вид (3):

hello_html_m426a7db.gif

(3)

где G1 – граф, полученный из графа G добавлением нового ребра (v1, v2), а граф G2 получается из графа G отождествлением вершин v1 и v2.

А утверждение, являющееся базой для хроматической редукции по пустым графам, гласит, что хроматический полином графа может быть представлен разностью хроматических полиномов двух графов и имеет вид (4):

hello_html_m6fc04232.gif

(4)

где G1 – граф, полученный из графа G удалением ребра (v1, v2), а граф G2 получается из графа G отождествлением вершин v1 и v2.

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

C:\Users\WhiteRabbit\Desktop\Раскраски графов\Добавление ребра, удаление ребра, отождествление вершин.png

Рис. 4. Исходный граф (а), добавление (б) в него ребра (v1, v3), удаление (г) из него ребра (v1, v2), отождествление вершин v1 и v3 (г)


Докажем первое утверждение (о редукции по полным графам). Число правильных раскрасок графа G в x цветов, при которых при которых цвета вершин v1 и v2 различны, не изменится, если к G присоединить ребро (v1, v2), поэтому оно равно P(G1, x). Аналогично, число правильных раскрасок графа G в x цветов, при которых цвета вершин v1 и v2 совпадают, равно P(G2, x). Сложив эти два числа, получим число правильных раскрасок графа G в x цветов.

Пользуясь представленными выше утверждениями, попытаемся вывести хроматический полином P(G,x) графа G, представленного на рис. 5. Мы будем пользоваться хроматической редукцией по полным графам, то есть будем сводить хроматический полином представленного графа к хроматическим полиномам полных графов.

C:\Users\WhiteRabbit\Desktop\Раскраски графов\G3 исх.png

Рис. 5. Граф с тремя вершинами


Эта задача может быть решена на один шаг. Покажем редукцию по полным графам с помощью рис. 6. Для этого представим исходных граф в виде двух графов – для первого в исходном графе необходимо добавить недостающее ребро (v1, v3), а во втором отождествим вершины v1 и v3.

C:\Users\WhiteRabbit\Desktop\Раскраски графов\G3=K3+K2.png

Рис. 6. Редукция графа с тремя вершинами


Оба полученных графа являются полными: первый – граф K3, второй – граф K2 и редукцию можно прекратить. То есть хроматический полином нашего исходного графа (рис.7) раскладывается на сумму двух хроматических полиномов (5):

hello_html_m1a13343d.gif

(5)

Хроматические полиномы полных графов равны (6)

hello_html_576cc045.gif

hello_html_m2a0f62fb.gif

(6)

Сложив полиномы и приведя подобные, получим (7):

hello_html_m42e73225.gif

hello_html_48485f1c.gif

hello_html_m1b394d88.gif

(7)

С помощью хроматического полинома можно найти хроматическое число. Для этого нужно в полином последовательно подставлять числа x=1, 2, 3, … и первое число, при котором полином будет отличаться от нуля и будет хроматическим числом. Для нашего примера хроматическое число равно 2. Это и есть количество способов раскраски данного графа. Оба способа раскраски для двух красок, черной и белой, представлены на рис. 7.

C:\Users\WhiteRabbit\Desktop\Раскраски графов\Варианты раскраски G2.png

Рис. 7. Варианты раскраски для графа с тремя вершинами при использовании двух цветов (черного и белого)

Выше были рассмотрены хроматический полином и хроматическое число. Но эти объекты лишь характеризуют раскраски графа и устанавливают минимальное число красок и количество способов раскраски. Но на вопрос как именно следует раскрашивать граф, ответ дан не был. Дело в том, что задача раскраски является довольно сложной и может решаться различными способами. Рассмотрим наиболее простой из них.

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

Поэтому вершины вначале располагаются в порядке убывания их степеней (точнее, невозрастания). Первая вершина, имеющая наибольшую степень, окрашивается в цвет 1 (если несколько вершин имеют одинаковые степени можно выбрать любую из них); после этого список вершин просматривается сверху вниз (по убыванию степеней) и в цвет 1 окрашивается любая вершина, которая не смежна с другой, уже окрашенной в этот цвет. Затем возвращаемся к первой в списке неокрашенной вершине, окрашиваем ее в цвет 2 и снова просматриваем список вершин сверху вниз, окрашивая в цвет 2 любую неокрашенную вершину, которая не соединена ребром с другой, уже окрашенной в цвет 2 вершиной. Аналогично действуем с цветами 3, 4 и т. д., пока не будут окрашены все вершины. Число использованных цветов будет приближенным значением хроматического числа графа.

Покажем работу этого алгоритма на примере. Пусть дан граф, вершины которого надо раскрасить (рис. 8,а). Построим список вершин по убыванию степеней: степень 3 (deg=3) имеют вершины v1 и v4; степень 2 (deg=2) имеют вершины v2, v3 и v5.


F:\Все, что было на ноуте\Дипломники\2014-2015\Моторина\Раскраски графов\Статья\Раскраска графа G5.png

Рис. 8. Процесс раскраски графа


Выберем вершину с наибольшей степенью, например, v1 и окрасим ее (рис. 8,б). Мы выбрали в качестве первого цвета синий (С). Вершины, смежные с вершиной v1, а это вершины v2, v4 и v5 не могут быть окрашены в синий цвет. Ищем вершины, которые можно окрасить в синий цвет. Это единственная вершина v3. Окрашиваем ее в синий цвет (рис. 8,в). Синий цвет исчерпан, в него нельзя больше окрасить ни одну вершину. Выбираем из списка нераскрашенных вершин вторую вершину с максимальной степенью – это вершина v4 и окрашиваем ее во второй цвет (рис. 8 г). Пусть это будет красный (К) цвет. Из оставшихся не раскрашенными вершин, вершина v5 не может быть раскрашена в красный цвет. Ищем вершины, которые можно окрасить в красный. Это единственная вершина v2. Раскрасим ее в красный. Красный цвет исчерпан. Выбираем единственную не раскрашенную вершину v5 и раскрашиваем ее в третий цвет – зеленый (З). На этом раскраска графа завершена. Количество используемых красок 3.

В качестве практической и самостоятельной работы следует рекомендовать решение задач, изложенных в пособиях О.И.Мельникова [4, с.20–23, задачи 93–101], [5, с.139–152 , задачи 176–188]. Там же можно найти подробно изложенное решение задач. При решении задач могут использоваться и специализированные математические пакеты, например, такие как Maple или Scilab [6].


Рекомендуемая литература:

  1. Березина Л. Ю. Графы и их применение: Пособие для учителей с ил. — М.: Просвещение, 1979. — 143 с.

  2. Мельников О.И. Занимательные задачи по теории графов. — Минск: ТетраСистемс, 2001. — 144 с.

  3. Мельников О.И. Теория графов в занимательных задачах. Изд.3, испр. и доп. — М.: Книжный дом «ЛИБРОКОМ», 2009. — 232 с.

Идёт приём заявок на самые массовые международные олимпиады проекта "Инфоурок"

Для учителей мы подготовили самые привлекательные условия в русскоязычном интернете:

1. Бесплатные наградные документы с указанием данных образовательной Лицензии и Свидeтельства СМИ;
2. Призовой фонд 1.500.000 рублей для самых активных учителей;
3. До 100 рублей за одного ученика остаётся у учителя (при орг.взносе 150 рублей);
4. Бесплатные путёвки в Турцию (на двоих, всё включено) - розыгрыш среди активных учителей;
5. Бесплатная подписка на месяц на видеоуроки от "Инфоурок" - активным учителям;
6. Благодарность учителю будет выслана на адрес руководителя школы.

Подайте заявку на олимпиаду сейчас - https://infourok.ru/konkurs

Краткое описание документа:

Предлагаемый материал представляет собой конспект урока "Раскраски графов" факультативного курса "Элементы теории графов и их приложения" (9 класс). Академик И.М.Яглом, в предисловии к книге О.Оре «Графы и их применение» отмечает, что несмотря на значительную важность для прикладной науки, «учение о графах очень подходит для изложения начинающим, поскольку соединяет большую геометрическую наглядность с математической содержательностью и с возможностью обходиться без громоздкого аппарата». Именно поэтому изучение теории графов можно рекомендовать в старших классах общеобразовательной школы.

Автор
Дата добавления 18.02.2016
Раздел Математика
Подраздел Конспекты
Просмотров236
Номер материала ДВ-467465
Получить свидетельство о публикации

УЖЕ ЧЕРЕЗ 10 МИНУТ ВЫ МОЖЕТЕ ПОЛУЧИТЬ ДИПЛОМ

от проекта "Инфоурок" с указанием данных образовательной лицензии, что важно при прохождении аттестации.

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

Список всех тестов можно посмотреть тут - https://infourok.ru/tests

Похожие материалы

Включите уведомления прямо сейчас и мы сразу сообщим Вам о важных новостях. Не волнуйтесь, мы будем отправлять только самое главное.
Специальное предложение
Вверх