Точный алгоритм раскраски графа паскаль
Алгоритмы
обхода графа
Алгоритмы поиска
кратчайшего пути
Нахождения наименьшего
остового дерева
Максимальные потоки
и паросочетания
Алгоритм раскраски графа
Алгоритм раскраски графа позволяет находить (точное или приближенное) значение хроматического числа произвольного графа и соответствующую этому значению раскраску вершин.
Граф G называют r-хроматическим, если его вершины могут быть раскрашены с использованием r цветов (красок) так, что не найдется двух смежных вершин одного цвета. Наименьшее число r, такое, что граф G является r-хроматическим, называется хроматическим числом графа G. Задача нахождения хроматического числа графа называется задачей о раскраске (или задачей раскраски) графа. Соответствующая этому числу раскраска вершин разбивает множество вершин графа на r подмножеств, каждое из которых содержит вершины одного цвета. Эти множества являются независимыми, поскольку в пределах одного множества нет двух смежных вершин.
Рассмотрим последовательный метод, основанный на упорядочивании множества вершин.
Формальное описание [вверх]
В этом простейшем из методов вершины вначале располагаются в порядке невозрастания их степеней. Первая вершина окрашивается в цвет 1; затем список вершин просматривается сверху вниз (по невозрастанию степеней) и в цвет 1 окрашивается всякая вершина, которая не смежна с другой, уже окрашенной в этот цвет. Потом возвращаемся к первой в списке неокрашенной вершине, окрашиваем ее в цвет 2 и снова просматриваем список вершин сверху вниз, окрашивая в цвет 2 любую неокрашенную вершину, которая не соединена ребром с другой, уже окрашенной в цвет 2 вершиной. Аналогично действуем с цветами 3, 4 и т. д., пока не будут окрашены все вершины. Число использованных цветов будет тогда приближенным значением хроматического числа графа.
Приведенный выше алгоритм можно модифицировать. Для этого после каждого шага нужно упорядочивать неокрашенные вершины. Простая модификация описанной выше эвристической процедуры состоит в переупорядочивании неокрашенных вершин по невозрастанию их относительных степеней. Под относительными степенями понимаются степени соответствующих вершин в неокрашенном подграфе исходного графа.
В данной модификации предполагалось, что если две вершины имеют одинаковые степени, то порядок таких вершин случаен. Такие вершины можно также упорядочить, но уже по двухшаговым степеням. Двухшаговую степень определим как сумму относительных степеней инцидентных вершин. Аналогично можно поступать и далее.
Оценка сложности [вверх]
Не учитывая время, затраченное на сортировку вершин в порядке невозрастания степеней, необходимо сделать цикл по всем вершинам графа. Для каждой необходимо найти минимальный цвет, что в худшем случае может занять o(V 2 ) для случая с полным графом. Значит, общее время составит o(V 3 ) в худшем случае.
лабы по информатике, егэ
лабораторные работы и задачи по программированию и информатике, егэ по информатике
Pascal: Занятие № 4 часть II. Графика в Паскале
Графика в Паскале
Для работы с графикой в pascal abc используется модуль GraphABC. Для его подключения используется следующий код:
uses GraphABC; begin . end.
Система координат в Паскале соответствует экранной системе координат и выглядит следующим образом:
Управление цветом
Для того, чтобы использовать цвет, необходимо применить этот цвет к инструменту перо:
- SetPenColor(color) — устанавливает цвет пера, задаваемый параметром color;
- setBrushColor(color) — устанавливает цвет кисти, задаваемый параметром color;
- либо для палитры RGB: SetPenColor(rgb(0-255, 0-255, 0-255));
или использовать для заливки:
После чего можно использовать процедуры для рисования геометрических фигур.
clBlack – черный
clPurple – фиолетовый
clWhite – белый
clMaroon – темно-красный
clRed – красный
clNavy – темно-синий
clGreen – зеленый
clBrown – коричневый
clBlue – синий
clSkyBlue – голубой
clYellow – желтый
clCream – кремовый
clAqua – бирюзовый
clOlive – оливковый
clFuchsia – сиреневый
clTeal – сине-зеленый
clGray – темно-серый
clLime – ярко-зеленый
clMoneyGreen – цвет зеленых денег
clLtGray – светло-серый
clDkGray – темно-серый
clMedGray – серый
clSilver – серебряный
Точки, отрезки и ломаные
Для отображения точки в паскале используется процедура:
SetPixel(x,y,color) — Закрашивает один пиксел с координатами (x,y) цветом color
uses GraphABC; begin SetPixel(300,200,clred); end.
Для рисования линии используется:
Line(x1,y1,x2,y2) — рисует отрезок с началом в точке (x1,y1) и концом в точке (x2,y2)
uses GraphABC; begin SetPenColor(clgreen); line(100,50,500,250); end.
Ломаные можно рисовать с помощью процедур MoveTo (x1, y1) и LineTo (x2, y2) .
Процедуры работают в паре: MoveTo передвигает курсор в определенную точку, а процедура LineTo рисует линию с этой точки до точки, определенной параметром данной процедуры. 
uses GraphABC; begin . SetPenColor(clblue); MoveTo (x1, y1); LineTo (x2, y2); LineTo (x3, y3); LineTo (x4, y4); LineTo (x5, y5); end.
Для установки размеров графического окна используется процедура
SetWindowSize(ширина, высота)
Рисование фигур
uses GraphABC; begin Rectangle(50,50,200,200); end.
uses GraphABC; begin Rectangle(50,50,200,200); FloodFill(100,100,clBlue); end.
Line(x1,y1,x2,y2);
LineTo(x,y);
uses GraphABC; begin setpenwidth(20); setpencolor(clred); moveTo(300,100); lineTo(500,300); lineto(100,300); lineto(300,100); floodfill(300,200,clgreen); end.
uses GraphABC; begin Circle(500,200,100); FloodFill(500,200,clred); end.
uses GraphABC; Begin SetPenWidth(10); Arc(300,250,150,45,135); end.
Функция random для использования окраски
* раскрасить круги случайным цветом
Нарисовать штриховку на Паскале можно, используя процедуры рисования прямоугольника и линии: 
Программа будет выглядеть следующим образом:
uses graphABC; var i, x1, x2, y1, y2, N: integer; h, x: real; begin x1 := 100; y1 := 100; x2 := 300; y2 := 200; N := 10; Rectangle (x1, y1, x2, y2); h := (x2 — x1) / (N + 1); x := x1 + h; for i:=1 to N do begin Line(round(x), y1, round(x), y2); x := x + h; end; end.
Анимация в Паскале
Анимация в программировании заключается в том, что сначала рисуется фигура цветным инструментом, затем с тем же координатами рисуется та же фигура белым цветом. После чего происходит сдвиг фигуры и действия повторяются.
uses GraphABC; var x:integer; begin x:=40; repeat SetPenColor(clWhite); Circle(x,100,10); <Рисуем белую окружность>SetPenColor(clBlack); Circle(x,100,10); <Рисуем черную окружность>x:=x+1 <Перемещаемся немного направо>until x>600; end.
Точный алгоритм раскраски вершин графа.
Пример: (задан граф пересечений)
| u1 | u2 | u3 | u4 | u5 | u6 | |
| x1 | 1 | 1 | 1 | |||
| x2 | 1 | 1 | ||||
| x3 | 1 | 1 | 1 | |||
| x4 | 1 | 1 | ||||
| x5 | 1 | 1 |
1. Определение непополнимых внутренне устойчивых вершин графа.
Подмножество несмежных вершин графа называют внутренне устойчивым. Непополнимое внутренне устойчивое подмножество вершин графа — такое подмножество, что добавление любой вершины в это подмножество приведет к нарушению свойству внутренней устойчивости.
Представим граф пересечений в виде матрицы смежности S:
Образуем конъюнкцию дизъюнкций вершин, инцидентных каждому ребру:
2. Получение матрицы V, определяющей вхождение вершины в каждое из этих подмножеств:
| F1 | F2 | F3 | F4 | |
| x1 | 1 | |||
| x2 | 1 | 1 | ||
| x3 | 1 | |||
| x4 | 1 | 1 | ||
| x5 | 1 | 1 |
3. Распределение проводников по слоям
| F1 |
F2 |
F3 |
|
| 1 | |||
| 2 |
(таким образом, у нас — два варианта исключения повторяющихся вершин). Если k — количество повторяющихся вершин, то всего возможно 2 k вариантов.
Эвристический алгоритм раскраски вершин графа.
1. Вершины графа пересечений упорядочиваются в невозрастающем порядке по локальной степени вершины.
2. Берется первая вершина (с самой большой локальной степенью вершины). Она окрашивается в цвет 1 и удаляется из списка.
3. В этот же цвет окрашиваются и другие вершины, которые не являются смежными с первой вершиной, а также между собой. Окрашенные вершины удаляются из списка.
4. Берется новый цвет и повторяются пункты 2-3 до тех пор, пока все вершины не окрашены.
Преимущество: высокое быстродействие
Недостаток: невысокое качество полученного результата
| x1 | x2 | x3 | x4 | x5 | x6 | x7 | r | ||
| x1 | 1 | 1 | 2 | ||||||
| x2 | 1 | 1 | 1 | 1 | 4 | ||||
| x3 | 1 | 1 | 1 | 1 | 1 | 5 | |||
| R= | x4 | 1 | 1 | 1 | 3 | ||||
| x5 | 1 | 1 | 1 | 3 | |||||
| x6 | 1 | 1 | 2 | ||||||
| x7 | 1 | 1 | 1 | 3 |
Упорядочиваем вершины по убыванию локальной степени:
Берём х3. Смежной с ней не является только вершина х4. Они окрашиваются в первый цвет.
Вычеркиваем из матрицы строки х3 и х4.
| x1 | x2 | x5 | x6 | x7 | r | ||
| x1 | 1 | 2 | |||||
| x2 | 1 | 1 | 1 | 4 | |||
| R¢= | x5 | 1 | 3 | ||||
| x6 | 2 | ||||||
| x7 | 1 | 3 |
Новый список:
| x1 | x5 | x7 | r | ||
| x1 | 2 | ||||
| R¢¢= | x5 | 3 | |||
| x7 | 3 |
Новый список: < x5,x7,x1 >Берём х5. Вершины х7 и х1 обе не являются смежными с х5, а также между собой. Поэтому все три оставшиеся вершины окрашиваются в третий цвет.
Не нашли то, что искали? Воспользуйтесь поиском:
Лучшие изречения: Только сон приблежает студента к концу лекции. А чужой храп его отдаляет. 9274 — 
| 7852 — 
или читать все.
Точный алгоритм раскраски графа паскаль
Минимальное число цветов, необходимое для раскраски вершин некоторого графа с использованием для пары соседних вершин различных цветов, называется хроматическим числом
графа 
и обозначается через 
Поиск хроматического числа представляет собой комбинаторную задачу. Введем обозначения: 5 — множество вершин графа; 
— множество ребер графа, т. е. множество пар вида 
принадлежащих декартову произведению 
таких, что 
связано с 
множество 
чисел натурального ряда, т. е. множество 
использованных цветов. В этих обозначениях данную задачу можно сформулировать следующим образом:
Найти функцию 
такую, что для всякой пары 
из 
нужно задать 
причем 
должно быть минимальным.
Мы можем (как в задаче о восьми ферзях) сначала раскрасить одну вершину и учесть все импликации, связанные с присвоением этого значения, а затем использовать метод неявного перебора до тех пор, пока не раскрасим все вершины. Но здесь мы должны остановиться не тогда, когда исчерпаем все возможности, а гораздо раньше — как только мы сможем доказать, что не существует решения лучшего, чем известное нам оптимальное решение. Общая схема действий приведена в алгоритме 5а.
5.10.1. Первый этап: поиск решения
Предложить первый способ раскраски нетрудно, поскольку в качестве функции 
достаточно взять функцию, такую, что 
Полученная таким образом раскраска является допустимой: все вершины раскрашены в различные цвета. В этом случае число использованных цветов 
равно мощности множества 5 вершин данного графа.
Улучшая это решение, мы сталкиваемся с такой же проблемой, как в задаче о восьми ферзях: для каждой вершины (или для каждой горизонтали шахматной доски) в исходный момент имеется 
вариантов раскраски (вместо восьми свободных клеток), причем 
Поэтому мы снова можем использовать алгоритм 
только нужно уточнить следующее:
а) как происходит выбор в случае равенства степеней свободы;
б) как осуществляется управление импликациями. Для ответа на вопрос а) воспользуемся как и раньше идеей: выбирать тот вариант, который несет больше информации. Здесь это сводится к тому, чтобы рассматривать наиболее связанную вершину графа, т. е. вершину, которая накладывает наибольшее число ограничений. Однако в данной задаче имеется только один тип ограничений: для всякой пары 
из множества 
Следовательно, наиболее связанная вершина множества 
— это вершина, из которой выходит наибольшее число ребер, принадлежащих множеству 
. В графе 
число ребер, проходящих через вершину 
мы будем называть степенью вершины 
Итак, в случае равенства вариантов мы будем выбирать ту нераскрашенную вершину, которая обладает наибольшей степенью в графе, состоящем из еще не раскрашенных вершин. Как обычно, выбранный критерий не является ни абсолютным (его можно было бы изменить), ни необходимым (без него алгоритм остается надежным); он нужен лишь для повышения эффективности. Так как эксплицитное задание ребер графа позволяет фиксировать запреты в явном виде, получение ответа на вопрос в 
не представляет трудностей. Конечно, как и в задаче о восьми ферзях, мы должны учесть цепочки импликаций, вынужденные присваивания значений (когда мы можем раскрасить вершину только в один цвет) и случаи, когда продолжать раскраску невозможно (с предусмотренным возвращением назад и восстановлением свободных вершин).
На данном этапе становится очевидным, что мы, безусловно, можем построить лучшее решение, чем то тривиальное решение, которое приписывает каждой вершине свой цвет. Для этого достаточно рассматривать только критерий, касающийся степеней вершин графа (мы ввели его при разъяснении пункта 
. В самом деле, ведь априори все степени свободы равны, и потому основанный на них критерий не является действенным. Но тогда мы можем построить хорошее решение, используя “жадный” алгоритм следующего вида:
Пример 1. В исходный момент вершины графа, изображающего географическую каргу, имеют следующие степени:
Мы раскрасим сначала вершину “Париж”, одну из двух, обладающих максимальной степенью:
I 
(Париж).
Затем мы наложим запрет на использование цвета I при раскрашивании шести соседних вершин и одновременно уменьшим на единицу степени всех этих вершин. Таким образом, мы получим вторую строку табл. 5.1. Теперь наибольшей степенью обладает вершина “Берлин”. Поскольку цвет I использовать в этом случае запрещено, мы закрасим ее цветом II:
II 
(Берлин).
Таблица 5.1. (см. скан) Раскрашивание географической карты
При этом степени вершин изменятся так, как указано в третьей строке табл. 5.1. Выбрав первую по счету вершину, обладающую степенью 2, мы получаем III 
(Брюссель), поскольку связанные с данной вершиной вершины раскрашены в цвета I и II. Теперь мы получили степени, указанные в четвертой строке табл. 5.1. Поскольку для вершины “Вена” третий цвет не запрещен, мы можем раскрасить:
III 
(Вена)
Теперь мы можем раскрасить все оставшиеся вершины:
Мы получили решение в четыре краски. Однако мы лишь узнали, что для данной карты у 4, но не доказали, что сделать
Таблица 5.2. (см. скан) Раскрашивание графа для задачи о конференции лучше невозможно.
Такой же результат дает теорема Аппеля и Хакена.
Пример 2. В первой строке табл. 5.2 приводятся зафиксированные в исходный момент степени вершин графа для задачи о конференции. Итак, в первую очередь мы раскрашиваем
Затем, используя промежуточные результаты, приведенные в табл. 5.2, последовательно получаем
Наконец, когда все оставшиеся вершины оказываются в нулевой степени, получаем
Мы можем утверждать, что для второго графа у 5.
Таким образом, мы выполнили все действия на первом этапе исходного алгоритма (алгоритм 5а). Теперь пока мы не докажем, что искомое хроматическое число равно 
мы должны установить 
и искать новое решение для этого числа цветов.