Реферат Курсовая Конспект
Раскраски графов - раздел Математика, Остовы графов Пусть G= Неорграф Без Петель. Раскраской (Вершин) Графа G ...
|
Пусть G= неорграф без петель. Раскраской (вершин) графа G называется такое задание цветов вершинам G, что если ребро, то вершины и имеют различные цвета. Хроматическим числом χ(G) графа G называется минимальное число цветов, требующееся для раскраски G.
П р и м е р 4.14.1. Так как в полном графе Kn любые две различные вершины связаны ребром, то χ(Kn)=n.
Многие практические задачи сводятся к построению раскрасок графов.
П р и м е р 4.14.2 1. Рассмотрим задачу составления расписания. Предположим, что нужно прочесть несколько лекций за кратчайшее время. Чтение каждой лекции в отдельности занимает один час, но некоторые лекции не могут читаться одновременно ( например, их читает один и тот же лектор). Построим граф G, вершины которого биективно соответствует лекциям и две вершины смежны тогда и только тогда, когда соответствующие им лекции нельзя читать одновременно. Очевидно, что любая раскраска этого графа определяет допустимое расписание: лекции, соответствующие вершинам одного цвета, могут читаться одновременно. Напротив, любое допустимое расписание определяет раскраску графа G. Оптимальные расписания соответствуют раскраскам с минимальным числом цветов, а число часов, необходимое для прочтения всех лекций, равно χ(G).
2.Рассмотрим граф G, вершины которого-страны, а ребра соединяют страны, имеющие общую границу. Числу χ(G) соответствует наименьшее число красок, необходимых для раскраски карты так, чтобы никакие две соседние страны не были окрашены в один цвет.
Существуют и практические задачи, связанные с раскраской ребер в мультиграфе.
Раскраска ребер в мультиграфе G может быть определена с помощью раскраски вершин так называемого реберного мультиграфа L(G). Для произвольного неориентированного мультиграфа G= реберным мульграфом L(G) называется тройка , где U M и выполняется тогда и только тогда, когда в мультиграфе G вершина является концом ребер и . Раскраской ребер мультиграфа G называется раскраска вершин мультиграфа L(G).
П р и м е р 4.14.3. Проводится монтаж аппаратуры. Чтобы не перепутать проводники , необходимо их окрасить таким образом, чтобы два проводника, идущие к одной плате, имели разные цвета. В этом случае вершинами являются платы, а ребрами- проводники.
Неорграф G называется бихроматическим, если χ(G)=2. Неорграф G= называется двудольным, если множество всех ребер графа G образует разрез графа G, т.е. для некоторого разбиения множества вершин концы любого ребра принадлежат разным частям разбиения.
Теорема 4.14.1.Пусть G-неорграф без петель, имеющий хотя бы одно ребро. Тогда следующие условия эквивалентны:
1) G-бихроматический граф;
2) G-двудольный граф;
3) G не содержит циклов нечетной длины.
Следствие 4.14.2.Если G-лес, то χ(G) 2.
Оценим хроматическое число графа G через его параметры. Обозначим через deg(G) максимальную степень вершин графа G.
Теорема 4.14.3.Для любого неорграфа G без петель выполняется неравенство χ(G) deg(G)+1.
Рассмотрим простой алгоритм построения раскраски, который во многих случаях приводит к раскраскам, близким к минимальным.
Алгоритм последовательной раскраски.
1. Произвольная вершина графа G принимает цвет 1.
2. Если вершины раскрашены цветами 1,2, … , , то новой произвольно взятой вершине припишем минимальный цвет, не использованный при раскраске вершин из множества .
Для некоторых классов графов последовательная раскраска является минимальной. В общем случае это не так.
– Конец работы –
Эта тема принадлежит разделу:
тема quot Элементы теории графов Виды и способы задания графов quot... Даны населенные пункты расстояния между которыми известны Требуется найти маршрут проходящий через все пункты по...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Раскраски графов
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов