Раскраска вершин гиперграфа
|
|
Московский авиационный институт
(государственный технический университет)
Курсовая работа по
дискретной математике
Раскраска вершин гиперграфа
|
Москва, 2007
Задание. № 14Т
Задание: раскраска вершин гиперграфа. Найти минимальную раскраску гиперграфа.
Теоретический минимум.
Пусть V — конечное непустое множество, E — некоторое семейство непустых подмножеств множества V. Пара (V, E) называется гиперграфом с множеством вершин V и множеством ребер E. Неформально: гиперграф — это такое обобщение простого графа, когда ребрами могут быть не только двухэлементные, но и любые подмножества вершин.
Если вершина v (из V) принадлежит ребру e (из E), то говорят, что они инцидентны. Вершина гиперграфа, не инцидентная никакому ребру, называется изолированной.
Гиперграфы содержащие петли в данной задаче не рассматриваются. Две вершины v` и v`` гиперграфа H назовем смежными, если существует ребро e = EH, которое содержит обе эти вершины. Два ребра e` и e`` гиперграфа H назовем смежными, если их объединение не пустое множество.
На рисунке выше изображен гиперграф с множеством вершин V = {v1, v2, … v9} и множеством ребер E = {e1 = {v1 , v2, v3}, e2 = {v2, v4, v5, v6}, e3 = {v6, v7, v8}, e4 = {v3, v8}, e5 = {v9}, e6 = {v6} }.
Обычно считают, что ребрами гиперграфа могут быть лишь не пустые подмножества вершин. В данной работе я полагаю, для простоты построения гиперграфа на ЭВМ, что ребром может быть любое множество вершин, в том числе и пустое.
Гиперграф H называют r-хроматическим, если его вершины могут быть окрашены с использованием r цветов (красок) так, что не найдется двух смежных вершин одного цвета. Наименьшее число r, такое , что гиперграф H является r-хроматическим, называется хроматическим числом гиперграфа. Задача нахождения хроматического числа гиперграфа называется задачей раскраски. Соответствующая этому числу раскраска вершин разбивает множество вершин графа на r независимых подмножеств, каждое из которых содержит вершины одного цвета. Независимым множеством вершин графа называется любое множество попарно не смежных вершин, т.е. множество вершин, порождающее пустой подграф. Существуют так называемые точные алгоритмы раскраски графа(!), большинство из которых или слишком сложны для гиперграфа или не применимы. Но эти алгоритмы гарантируют нахождение оптимальной раскраски и истинного значения хроматического числа для любого графа. Существует много эвристических процедур раскрашивания графов, позволяющих находить хорошее приближения для хроматического числа графа в тех случаях, когда размеры графа слишком велики и получение оптимальной раскраски точными методами затруднительно.
Описание алгоритма
Алгоритм рассмотренный мной при решении задачи заключается в прямом переборе.
Множество вершин упорядоченно (по построению ). xi – i-тая вершина гиперграфа. Первоначальная допустимая раскраска может быть получена так:
1) Окрасить все вершины в цвет 1.
2) Перейти к следующей вершине (изначально берем первую ):
a) если среди смежных к данной ранее встречался ее цвет, увеличить номер цвета на 1
b) иначе вернуться в пункт 2 если еще остались вершины.
Для обычного графа дальше следует улучшение раскраски, ее минимизация. Но в данном случае мы ничего не знаем о минимально возможной раскраске ( для графа это 5 цветов).
Этот алгоритм является одним из эффективных алгоритмов раскраски гиперграфа.
Описание программы
1) Осуществляется ввод. На поле программы щелчком левой кнопки мыши создаются вершины. Правой — ребра-области. Максимальное число вершин и ребер в данной программе равно 256, хотя может быть взято произвольное число, допустимое для данного ЭВМ. Нельзя создавать вершины расположенные слишком близко друг к другу и к краям “экрана”.
2) Все введенные вершины окрашиваются в цвет “0”. Это делается для того, чтобы изолированные вершины тоже имели свой цвет.
3) Формируется матрица инцидентности, если вершина (полностью, ибо она вообще имеет некоторый размер) попала в область, то она инцидентна соответствующему ребру. Попутно, все вершины попавшие в область окрашиваются в цвет “1”
4) По матрице инцидентности формируется матрица смежности. Просматриваются все вершины. Если две вершины инцидентны одному и тому же ребру то они смежные. Обратите внимание, что для гиперграфа обратный процесс невозможен(!).
5) Собственно сам алгоритм. Просмотр всех вершин, если смежные с данной вершиной (используется матрица смежности) имеют такой же цвет, то данная вершина перекрашивается в цвет на единицу больший. Для простоты и удобства проверки, я вместо цвета каждой вершине сопоставляю число, которое называю “цветом”.
6) Вывод на экран нарисованного пользователем гиперграфа, с раскрашенными вершинами. Вывод матрицы смежности и инцидентности.
Здесь я не привожу организации ввода и вывода программы. С алгоритмической точки зрения это не столь интересно, хотя играет некоторую роль в оценке сложности программы. В пункте 3, необходим поиск максимального и минимального числа из неупорядоченного множества, для определения границ областей. В данном случае я использовал стандартные алгоритмы языка программирования C++. Но это можно сделать и вручную: объявить некоторое число первое минимальным (максимальным), если найдется число меньше (больше) этого, то его объявить минимальным (максимальным), повторять пока не завершится последовательность. Вершина представлена как структура из трех единиц ( координаты и цвет), ребро — из четырех (координаты углов прямоугольника)
Оценка сложности
Для начала проведем оценку самого алгоритма. Пусть m — число вершин, n — число ребер. В данном случае мы не рассматриваем случай когда все вершины гиперграфа изолированные, программа не даст создать такой гиперграф. Раскраска всех вершин в цвет “1” займет m шагов независимо от расположения вершин. Далее, просмотр всех вершин займет еще m шагов. Проверка среди смежных вершин ранее встречавшегося цвета — m/2 шагов (сумма арифметической прогрессии), но так как на данном этапе мы проверяем и наличие элемента в матрице смежности и цвет, то здесь имеем m шагов. В лучшем случае, граф не содержит смежных вершин. И тогда оценка алгоритма: m — присваиваний и m2 — сравнений. Итого m2 + m операций. В худшем случае, все вершины графа смежные тогда, для каждой вершины мы должны инкрементировать ее цвет согласно ее номеру. А это m2/2 операций. Тогда оценка алгоритма: m + m2/2 — присваиваний и m2 — сравнений. Итого 3m2/2 + m операций. Вообще, учитывая строение современных ЭВМ, и особенности выбранного языка программирования, можно утверждать, что мы выполняем лишь m присваиваний, ибо операция инкремента, значительно “дешевле” присваивания. Но общая оценка остается прежней. Средняя оценка 5m2/4 + m операций. Также можно сказать, что сложность алгоритма составляет O(m2);
Далее, проведем оценку самой программы без ввода-вывода. Раскраска всех вершин в цвет “0” займет m шагов. 4m на формирование границ областей. Сложность стандартных алгоритмов не учитываем. Формируется матрица инцидентности — 4mn сравнений (попадание в область) и mn присваиваний. матрице инцидентности формируется матрица смежности — m2/2 операций сравнения строчек, в каждую из которых входит n операций инкремента, т.е. m2n/2 операций присваиваний. И тогда оценка: m ( n + 5 ) + m2 n / 2
— присваиваний и 4mn + m2/2 — сравнений. Итого (n + 1)( 5m + m2/2) операций.
Вместе с алгоритмом это составляет m(5n + 6) + m2 (2n+7)/4 операций.
Также можно сказать, что сложность алгоритма составляет O(m2n). Сложность программы больше сложности алгоритма. Это связано с выбранным способом считывания данных.
При вводе, данных используются простые циклы, поэтому можно сказать, что сложность аввода составляет O(m) + O(n). При выводе, данных используются простые циклы и вложенные циклы для вывода матриц инцидентности и смежности поэтому можно сказать, что сложность вывода составляет O(m) + O(n) + O(nm) + O(m2) т.е. O(m( m + n )).
Данная оценка показывает, что сложность всей программы остается O(m2n).
Приведем иллюстрации тестовых примеров.
1) Цикл с нечетным числом вершин
Результат — 3 цвета.
2) “Цепочка”
Результат — 2 цвета.
3) Одно ребро с 8 смежными вершинами
Результат — 8 цветов.
4) “Пирамида”
Результат — 5 цветов.
5) “Матрица”
Результат — 3 цвета.
6) Цикл с нечетным числом вершин
Результат — 2 цвета.
7) Ввода 256-ой вершины и 256-ого ребра не происходит.
8) Одна вершина инцидентная одному ребру — один цвет.
9) Ввод только вершин — раскраска не происходит, ввод только ребер — раскраска не происходит.
Прикладная задача.
Задача раскраски в “чистом” виде редко встречается на практике. Однако ее разновидности находят широкое применение в большом числе прикладных задач.
С помощью составленной программы очень удобно производить распределение ресурсов.
Пользователю современной ЭВМ (с многозадачной операционной системой) требуется выполнить несколько процессов. Процессы могут выполняться параллельно, но при этом иногда они запрашивают один и тот же ресурс (принтер, факс, модем, жесткий диск), который может быть предоставлен лишь одному процессу. Составленная программа выстраивает очередность выполнения процессов. Те процессы которые не требуют одинаковых ресурсов выполняются параллельно. Необходимо процессам сопоставить вершины графа, а ресурсам ребра.
Когда я приступил к решению данной задачи, я решал ее несколько в ином контексте.
Существует набор целей (вершины гиперграфа), по которым необходимо нанести ракетно-бомбовые удары. Атаковать нужно все цели сразу. Но по некоторым тактическим причинам (погода, удаленность от базы, рельеф местности) это невозможно. Те цели которые мы не можем уничтожить вместе мы заключаем в области-ребра. Программа показывает оптимальную последовательность проведения бомбардировки.