Алгоритм раскраски графа с перекраской двуцветных компонент
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
?а, выполняются одновременно. Наилучшее использование ресурсов (т. е. выполнение всех n работ за наименьшее время) достигается при оптимальной раскраске вершин графа .
Задача составления расписаний
Предположим, что нужно прочесть несколько лекций за кратчайшее время. Чтение каждой лекции в отдельности занимает один час, но некоторые лекции не могут читаться одновременно (например, их читает один и тот же лектор). Построим граф G, вершины которого биективно соответствуют лекциям, и две вершины смежны тогда и только тогда, когда соответствующие лекции нельзя читать одновременно. Очевидно, что любая правильная раскраска этого графа определяет допустимое расписание: лекции, соответствующие вершинам графа, составляющим цветной класс, читаются одновременно. И, обратно, любое допустимое расписание определяет правильную раскраску графа G. Оптимальные расписания соответствуют минимальным раскраскам, а число часов, необходимое для прочтения всех лекций, равно.
Задача распределения оборудования
Заданы множества и работ и механизмов соответственно. Для выполнения каждой из работ требуется некоторое время, одинаковое для всех работ, и некоторые механизмы. При этом никакой из механизмов не может быть одновременно занят в нескольких работах. Нужно распределить механизмы так, чтобы общее время выполнения всех работ было минимальным.
Построим граф G, положив VG= Vи объявив вершины viи vjсмежными тогда и только тогда, когда для выполнения работ viи vj требуется хотя бы один общий механизм. При правильной раскраске графа Gработы, соответствующие вершинам одного цвета, можно выполнять одновременно, а наименьшее время выполнения всех работ достигается при минимальной раскраске.
Оценки хроматического числа
Поскольку задачу правильной раскраски точно решить трудно, то актуальны оценки хроматического числа, выражаемые в терминах более или менее просто вычислимых параметров графа. Рассмотрим некоторые теоремы и оценки, относящиеся к хроматическим числам.
Обозначим через множество всех порожденных подграфов графа G, а через ?(G) - минимальную из степеней вершин графа G.
Теорема 1.Для любого графаG верно неравенство
Доказательство. Утверждение теоремы очевидно для пустых графов. Пусть G- произвольный - хроматический граф, , а - его минимальный порожденный подграф, удовлетворяющий условию . В этом случае для любой вершины графа .
Предположим, что . Граф правильно раскрасим цветами. Окрасив затем вершину в один из этих цветов, не использованный при окраске смежных с ней вершин, получим правильную - раскраску графа . Следовательно, и
Обозначим черезнаибольшую из степеней вершин графа .
Теорема 2.Простой граф- - раскрашиваемый.
.
Доказательство. Даны различных цветов, получим - раскраску графа G следующим образом.
Возьмем произвольную вершину и присвоим ей любой из цветов. Затем выберем нераскрашенную вершину, например . Присвоим вершине цвет, который не был присвоен смежным с ней вершинам. Это всегда возможно, поскольку и, следовательно, вершинам, смежным с вершиной , будет присвоено самое большое, - цветов. Повторим этот процесс до тех пор, пока не раскрасятся все вершины. В результате получится правильная - раскраска. ?
Очевидно, что для полных графов и циклов нечетной длины. Очень интересно то, что для всех остальных графов . Этот результат получен Бруксом[9] и доказывается ниже. Приводимое здесь доказательство предложили Мельников и Визинг[11]. Другое доказательство можно найти в работе [10].
Теорема 3(Брукс). Пусть G - связный простой граф. Если он не цикл нечетной длины и не полный граф, то есть когда G не содержит в качестве компонент граф или и цикл нечетной длины является компонентой G, то
Доказательство. Теорема очевидна для
Чтобы доказать теорему для , допустим противное, то есть что существуют графы, не являющиеся полными, для которых и . Выберем такое графс минимальным числом вершин.
Пусть , а - граф, полученный в результате удаления из графа вершины . Из выбора графа G следует, что - раскрашиваемый. Следовательно, , иначе бы для раскраски вершины можно было использовать один из ? цветов, применяемых для раскраски графа , что противоречит равенству . Другим важным следствием является следующее:
Свойство 1. В любой ?-раскраске графа вершины, смежные с вершиной , раскрашиваются по-разному.
Пусть - вершины, смежные с вершиной . Пусть получают в раскраске графа цвета 1, 2,…,?соответственно. Обозначим черезпорожденный подграф на вершинах, которым присвоены цвета и .
Свойство 2. Вершины и находятся в одной компоненте связности.
В противном случае, заменяя цвета и в компоненте, содержащей , мы получим новую ?-раскраску графа , в которой и присвоен одинаковый цвет, что противоречит свойству 1.
Пусть - компонента, содержащая вершины и .
Свойство 3. - путь от вершины к вершине .
Предположим, что степень в больше 1. Тогда смежна не менее чем с двумя вершинами цвета . Поскольку в графе , мы можем перекрасить в цвет , так что в получившейся новой раскраске вершины и имеют одинаковый цвет, что противоречит свойству 1.
Аналогично можно показать, что степень в равна 1.
Степень всех остальных вершин равна 2. Допустим противное. Пусть - первая вершина степени (в ) больше 2 на пути от вершины к вершине и . Если раскрашена в цвет , то она смежна по крайней мере с тремя вершина