КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Покрытия и раскраски
Некоторые задачи, возникающие при планировании производства, составлении графиков осмотра и транспортировки товаров, могут быть представлены как задачи теории графов, тесно связанные с так называемой «задачей раскраски». Эта задача формулируется следующим образом: для данного графа определить минимальное количество цветов, необходимых для раскраски вершин графа так, чтобы никакие две смежные вершины не были окрашены в один цвет. Задачи раскраски вершин или ребер графа занимают важное место в теории графов. К построению раскрасок сводится целый ряд практических задач. Характерной особенностью этих задач является существование объектов, которые по каким-либо причинам не могут быть объединены в одну группу. Пусть G – некоторый граф, k – натуральное число. Произвольная функция вида f: X ®{l,2,..., k }называется вершинной k-раскраской, или просто k-раскраской, графа G. Если позволяет контекст, то k в этом определении опускается. Раскраска называется правильной, если f(xi) ¹ f(xj) для любых смежных вершин xi и xj. Граф, для которого существует правильная k -раскраска, называется k-раскрашиваемым (или раскрашиваемым k цветами). В определении раскраски вместо множества {1, 2,..., k }можно взять произвольное k -элементное множество. Правильную k -раскраску графа можно трактовать как окрашивание каждой его вершины в один из k цветов, при этом смежные вершины должны получать различные цвета. Поскольку функция f не обязательно сюрьективна, то при k -раскраске фактически может быть использовано менее k цветов. Таким образом, правильную k -раскраску графа G можно рассматривать как разбиение X 1È X2 È... È Xl = X, l£k, множества вершин X на не более чем k непустых классов, каждый из которых является независимым множеством. Классы этого разбиения называются цветными классами. Множество вершин одного цвета называетсяодноцветным клаcсом. Минимальное число k, при котором граф G является k -раскрашиваемым, называется хроматическим числом этого графа и обозначается (G). Если (G) = k, то граф G называется k-хроматическим. Правильная k -раскраска графа G при k= (G) называется минимальной. В качестве иллюстрации рассмотрим граф G, изображенный на рис. 4.28, где указана одна из правильных 4-раскрасок. Меньшим числом цветов этот граф раскрасить правильно нельзя. Действительно, граф содержит цикл (x1, x2, x3, x4, x5, x1), для правильной раскраски которого нужно не менее трех цветов, а для вершины x6 требуется новый цвет. Итак, g(G)=4.
Пример. Так как в полном графе Кп любые две различные вершины связаны ребром, то g (Кn)= п. Рассмотрим некоторые практические задачи, сводящиеся к правильной раскраске графов. 1. Задача составления расписаний. Предположим, что нужно прочесть несколько лекций за кратчайшее время. Чтение каждой лекции в отдельности занимает один час, но некоторые лекции не могут читаться одновременно (например, их читает один и тот же лектор). Построим граф G, вершины которого биективно соответствуют лекциям, и две вершины смежны тогда и только тогда, когда соответствующие лекции нельзя читать одновременно. Очевидно, что любая правильная раскраска этого графа определяет допустимое расписание: лекции, соответствующие вершинам графа, составляющим цветной класс, читаются одновременно. И, обратно, любое допустимое расписание определяет правильную раскраску графа G. Оптимальные расписания соответствуют минимальным раскраскам, а число часов, необходимое для прочтения всех лекций, равно g (G). 2. Задача распределения оборудования. Заданы множества Х = { х1, х2,..., хn }и S = { s1, s2,..., sm }работ и механизмов соответственно. Для выполнения каждой из работ требуется некоторое время, одинаковое для всех работ, и некоторые механизмы. При этом никакой из механизмов не может быть одновременно занят в нескольких работах. Нужно распределить механизмы так, чтобы общее время выполнения всех работ было минимальным. Построим граф G с множеством вершин X и объявим вершины хi и хj (i≠j) смежными тогда и только тогда, когда для выполнения работ хi и хj требуется хотя бы один общий механизм. При правильной раскраске графа G работы, соответствующие вершинам одного цвета, можно выполнять одновременно, а наименьшее время выполнения всех работ достигается при минимальной раскраске. 3. Задача о проектировании коробки скоростей. Коробка скоростей – механизм для изменения частоты вращения ведомого вала при постоянной частоте вращения ведущего. Это изменение происходит за счет того, что находящиеся внутри коробки шестерни (зубчатые колеса) вводятся в зацепление специальным образом. Одна из задач, стоящая перед конструктором коробки, заключается в минимизации ее размеров, а это часто сводится к минимизации числа валов, на которых размещаются шестерни. Построим граф G, вершины которого биективно соответствуют шестерням. Если по какой-то причине две шестерни не должны находиться на одном валу (например, они могут быть в зацеплении, или их общий вес велик для одного вала и т. д.), то соответствующие вершины графа соединим ребром. Вершины, имеющие один цвет при правильной раскраске этого графа, определяют шестерни, которые могут находиться на одном валу, а хроматическое число g (G) равно минимальному количеству валов, нужных для проектируемой коробки. 4. Рассмотрим граф G, вершины которого – страны, а ребра соединяют страны, имеющие общую границу. Числу g (G) соответствует наименьшее число красок, необходимых для раскраски карты так, чтобы никакие две соседние страны не были окрашены в один цвет. Для некоторых графов хроматические числа найти несложно. Например, g (Кп) = п, g(Kn,m) = 2, g(C2n) = 2, g(C 2 n +1) = 3. Очевидно, что граф является 1-хроматическим тогда и только тогда, когда он пустой, а 2-хроматическим – когда он двудольный и непустой. Обычно 2-хроматический граф называют бихроматическим.Поэтому теорему Кёнига о двудольных графах можно сформулировать в следующем виде. Теорема 4.10.1. Непустой граф является бихроматическим тогда и только тогда, когда он не содержит циклов нечетной длины. Задачи определения хроматического числа и построения минимальной раскраски произвольного графа являются очень сложными, эффективные алгоритмы их решения неизвестны. Рассмотрим простой эвристический алгоритм построения правильной раскраски вершин графа, в ряде случаев приводящий к раскраскам, близким к минимальным. Замечание. Данный алгоритм определяет оценку y '(G) хроматического числа g(G) графа G, которая удовлетворяет соотношению g(G) £y'(G) £ max min { d (i)+l, i }, i где d (i) – степень i -ой вершины, причем индексация вершин хi осуществляется в соответствии с убыванием их степеней. Шаг 1. G – данный граф. Для каждой вершины графа определить ее степень. Расположить вершины в порядке невозрастания их степеней. Шаг 2. Первая вершина окрашивается в цвет №1. Затем список вершин просматривается сверху вниз и в цвет №1 окрашивается всякая вершина, которая не смежна с другой, уже окрашенной в этот цвет. Шаг 3. Возвращаемся к первой в списке неокрашенной вершине, окрашиваем ее в цвет №2 и, двигаясь по списку, окрашиваем вершины в цвет №2 так же, как окрашивали в цвет №1. Шаг 4. Процедура продолжается до тех пор, пока все вершины не будут окрашены. Количество использованных цветов будет приближенным значением хроматического числа. Раскраска, к которой приводит описанный алгоритм, называется последовательной. Очевидно, что это – правильная раскраска. Для некоторых классов графов (например, полных k -дольных) последовательная раскраска является минимальной. В общем случае это не так. Следующая теорема сводит задачу построения правильной раскраски графов к аналогичной задаче для двухсвязных графов. Теорема 4.10.2. Если каждый блок графа k -раскраши-ваем, то и сам граф также k -раскрашиваем. Доказательство. Воспользуемся индукцией по числу блоков рассматриваемого графа. Для графа, являющегося блоком, утверждение тривиально. Предположим, что теорема верна для графов, состоящих из m /1 блоков. Пусть теперь G – граф, имеющий ровно m+ 1 блоков, В – один из его концевых блоков, Н – объединение всех остальных блоков. По индуктивному предположению оба графа В и H являются k -раскрашиваемыми. Зафиксируем для каждого из них правильную k -раскраску. Графы В и H имеют ровно одну общую вершину х. Если ее цвета в обеих фиксированных k -раскрасках совпадают, то получена правильная k -раскраска графа G. В противном случае нужно очевидным образом переставить цвета в одной из фиксированных раскрасок. Теорема доказана. Утверждение 4.10.1. Если граф G является r -хромати-ческим, то он может быть раскрашен с использованием r красок с помощью следующей процедуры: сначала в один цвет окрашивается некоторое максимальное независимое множество S [ G ], затем окрашивается в следующий цвет множество S [ X \ S [ G ]] и т.д. до тех пор пока не будут раскрашены все вершины. Утверждение 4.10.2. Каждый планарный граф 5-раскра-шиваем. Утверждение 4.10.3. Каждый планарный граф, не содержащий треугольников, 3-раскрашиваем. Утверждение 4.10.4. Хроматическое число графа G равно кликовому числу его дополнения ` . Реберной раскраской неорграфа G =(X, V) k цветами называется функция j: V ®{l,2,.., k }, такая, что для любых двух смежных ребер v1 и v2 выполняется j (v 1)¹ j (v 2). Хроматическим индексом графа G называется наименьшее такое k, что граф G допускает реберную раскраску k цветами. Существуют и практические задачи, связанные с раскраской ребер в мультиграфе. Раскраска ребер в мультиграфе G может быть определена с помощью раскраски вершин так называемого реберного мультиграфа L(G). Для произвольного неориентированного мультиграфа G={X, V, Р}, где X – множество вершин, V – множество дуг, Р Î V X V, (x,v,y) Î Р тогда и только тогда, когда дуга v исходит из вершины х и заходит в вершину у, реберным мулътиграфом L(G) называется тройка { V, X, Р’}, где Р'ÎV X V, и выполняется (u, х, v)ÎР' тогда и только тогда, когда в мультиграфе G вершина х является концом ребер и и v. Раскраской ребермультиграфа G называется раскраска вершин мультиграфа L(G). Пример. Проводится монтаж аппаратуры. Чтобы не перепутать проводники, необходимо их окрасить таким образом, чтобы два проводника, идущие к одной плате, имели разные цвета. В этом случае вершинами являются платы, а ребрами – проводники. Теорема 4.10.3. Пусть G –неорграф без петель, имеющий хотя бы одно ребро. Тогда следующие условия эквивалентны: 1) G – бихроматический граф; 2) G – двудольный граф; 3) G не содержит циклов нечетной длины. Теорема 4.10.4.Для любого неорграфа G без петель выполняется неравенствоg (G) £ d(G) +1, где d(G) – наибольшая степень вершин графа.
Дата добавления: 2014-12-27; Просмотров: 709; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |