Элементарные алгоритмы для работы с графами

Теорема четырёх красокбыла окончательно доказана в 1977 году Кеннетом АппелемиВольфгангом Хакеномс использованием компьютерного перебора. Идея доказательства во многом опиралась на идеи Хивуда и Кемпе и игнорировала большинство промежуточных исследований.Доказательство теоремы четырёх красок является одним из первых доказательств, в которых был использован компьютер.Раскраска графов как алгоритмическая проблема начала изучаться с 1970-х годов: определениехроматического числа — входит в числодвадцати одной NP-полных задач Карпа(1972). И примерно в то же время были разработаны разнообразные алгоритмы на базепоиска с возвратом (backtracking)и рекурсивного удаления и стягивания А.А. Зыкова.Неослабевающийинтересивозрастающееиколичествоисследованийопределяютсянетолькотеоретическимпотенциаломэтойзадачи,ноимногочисленнымипрактическимприложениями,количествообластейкоторыхвпоследнеевремярастет.Первоначальнораскраскиграфовбылинужныдлясоставлениягеографическихкарт.Сегодняжеони(вчастностираскраскасиспользованиемминимальногоколичествацветов)используются,например,длясоставлениярасписаний,распределениярегистроввмикропроцессорах,распараллеливаниячисленныхметодов,распределениячастотвспектрерадиоизлученийсцельюмаксимизациипропускнойспособностиканаловсвязи,теорииконечныхавтоматов.Онатакжечастопоявляетсявразличныхзадачахпланирования,такихкакпроблемапередачифайловвкомпьютерныхсетяхидругихсетевыхзадач.С1981годараскраскаграфаприменяетсядляраспределениярегистроввкомпиляторах.Так,раскраскаграфовиспользуетсявтеориирасписаний.Вэтомслучаевершиныпредставляютсобойсобытия,которыенужнопланировать,ацвета–промежуткивремени,вкоторыемогутпараллельнопроисходитьнесколькособытий.Ребрамипользуютсядляразделениясобытий,которыенемогутпроисходитьодновременно.Примерамирасписаниймогутбыть:при составлении расписаний, как учебных занятий, так и спортивных состязаний планирование собраний, встреч[8];согласованиемаршрутовиграфиковгородскоготранспорта,авиационныхсообщений[9];расписание для коммунальных служб [10]. ДляграфаG(V,E),заданного,множествомвершинVимножествомреберЕ,к-раскраскаGявляетсяфункциейϕ:V→{1,...,k},присваивающейразличныезначениясмежнымвершинам,которыеобычноназывают“цвета”.Болееформально,длякаждогоребрае=(и,v)∈E,требуетсяϕ(и)≠ϕ(v),тоестьфункцияраскраскиϕразбиваетграфG(V,E)нанезависимыемножестваV→{1,...,k},внутрикоторыхникакиеиздвухвершиннесвязаныобщимребром.ЕслиGимеетk-раскраску,тоонназываетсяk-раскрашиваемым.Другимисловами,графявляетсяk-раскрашиваемым,еслиегоможнораскраситьтакимобразом,чтобыникакиедвесмежныевершинынеимелиодинаковыйцветизk-множествацветов.Примерыграфовираскрашиванийвключают:•Knполныйграфнаnвершинах,очевидно,n-раскрашиваемый,ноне(n - 1)-раскрашиваемый;•Km,n,полныйдвудольныйграфнагруппыmиnвершин,2-раскрашиваемый (бихроматический).Обапримерапроиллюстрированынарисунке6.Здесьраскраскапредставленадвумяспособами:ввиденомера,сопоставленногоскаждойвершинойϕ(v),ицвета.Рисунок6.ПолныеграфыК4иК5,атакжеполныедвудольныеграфыK2,2иK3,4,каждыйизкоторыхраскрашенсиспользованиемнаименьшеговозможногоколичествоцветов.Хроматическоечислоχ(G)илиγ(G)естьнаименьшеечислоkтакое,чтоGявляетсяk-раскрашиваемым.k-хроматическийграф–граф,имеющийхроматическоечисло,равноеk–егоможнораскраситьkцветами,нонеуженельзяраскрасить(k-1)–цветами.Такимобразом,дляприведенныхвышепримеровχ(Kn)=nиχ(Kmn)=2.ВсоответствиистеоремойКенига граф является бихроматическим в том и только в том случае, когда в нем нет циклов нечетной длины.Правильной раскраской ( Regular coloring) графаG(V,E) называется такое отображениеφ  из множества вершин V в множество цветов {c1, c2, . . . ct}, что для любых двух смежных вершин u и v выполняетсяφ(u)≠φ(v). . Также её называют t-раскраской.Рисунок 7. Пример правильной раскраски графаПод раскраской графа понимают как правило именно правильную раскраску.3.3 Алгоритм раскрашивания вершин графаХроматическоечисло(χ(G)определяетсякакнекийидеал:этоминимальноеk,длякоторыхмыможемнайтиk-раскраску.Кроменесколькихисключений,таких,каквпредыдущемразделе,неизвестенточныйибыстрыйалгоритмдлянахожденияоптимальной(всмысле,использованияминимальногоколичествацветов)раскраски.Темнеменее,кнастоящемувременидлязадачираскраскиграфовразработаныбольшоеколичествоэвристическихалгоритмов/4/.Наибольшееупотреблениеполучилиследующиеизвестные алгоритмыраскраски:раскраскаграфапоследовательнымобходомвершинбезихупорядочивания(Random-SequentialColour);жадныйалгоритмраскраски(Greedy-Colouring);раскраскаграфапоследовательнымобходомупорядоченныхвершин,отсортированныхпоубываниюихстепеней(Largest-First-Colour);раскраскасобменомцветами(Colour-with-Interchange),раскраскаграфапоследовательнымобходомупорядоченныхвершин,начинаясвершинмаксимальныхстепеней(Smallest-Last-Colour),раскраскавершинграфабезупорядочиваниясобменомцветами(Random-Sequential-Interchange-Colour),раскраскавершинграфасупорядочиваниемпоубываниюихстепенейсобменомцветами(LargestFirst-Interchange-Colour),раскраскаграфа,начинаясвершинмаксимальныхстепенейсобменомцветами(Smallest-Last-Interchange-Colour),жаднаяраскраскаграфа,вкоторойеговершиныупорядочиваютсятак,чтодлякаждойестьпокрайнеймереоднасоседняя,окрашеннаявпредшествующийцвет(Connected-SequentialColour),жаднаяраскрасканезависимыхподмножеств(GreedyIndependentSets-Colour);последовательнаяраскраскаграфасдинамическиупорядоченнымивершинамиграфа(Saturation-Colour);быстрая раскраскаграфасиспользованием битовых операций надматрицейсмежности, предложенная в работе Комоско Л.Ф и Бацын М.В. Рассмотрим алгоритм жадной окраски как один из наиболее распространенных. Жадные алгоритмы, в общем случае, не всегда обеспечивают минимально возможное (оптимальное) число цветов, тем не менее, их используют в других алгоритмах раскраски, а также они удобны в компьютерных программах для получения раскраски с небольшим числом цветов.3.3 Алгоритм жадной раскраскиЖаднойраскраски вершин графа (Greedy-Colouring)втеорииграфовпринятоназыватьалгоритмраскраскивершиннеориентированногографа,вкоторомобходяткаждуюизвершинграфавзаранеепредопределённойпоследовательностииокрашиваюткаждуювершинупервымдоступнымцветом.Идея жадной раскраски состоитвтом,чтобы присвоить номер первой вершине,азатем,начинаяс(v1)=1,посетитьоставшиесявершиныв последовательном порядке,назначивимцветснаименьшимномером, который ещенеиспользуетсядлясоседа.Алгоритмназываетсяжадным,потомучто он неимеетникакой долгосрочнойстратегии:онпростопроходитпоспискувершин,выбираяцвет,который,лучшевсего удовлетворяет условиям наданныймомент.Поэтому он не всегда находит минимальное количество цветов. Особенно неэффективным жадный алгоритм оказывается для полного двудольного графа («короны»): при определенной последовательности обхода вершин жадный алгоритм окрашивает вершин в nцветов, в то время, как все двудольные графы являются бихроматическими. Рисунок 8 иллюстрирует два варианта раскраски двудольного графа, в которых вершины обходились в различной последовательности. В одном варианте (слева) граф раскрашен жадным алгоритмом в два цвета, в то время как в другом варианте обхода этот же граф раскрашен n/2 цветами.Рисунок 8. Два варианта раскраски жадным алгоритмом одного и того же графа, в которых используется различная последовательность обхода вершинВ случаях с другими структурами графов жадная раскраска может попасть в яму локального минимума. Поэтому при разработке алгоритма важно предусмотреть возможность выбора различных вариантов, как начальной вершины, так и последовательности обхода вершин.ДлязаданногографаGичислацветовk,нахождениетакойпоследовательностиобходавершинграфаG,котораяобеспечитназначениежаднымалгоритмомkилиболеецветов,являетсяNP-полнойзадачей. В отношении задания этой последовательности обхода жадный алгоритм имеет различные варианты. Так, множествовершинлюбогографаможнорасположитьвтакойпоследовательности,чтожадныйалгоритмполучитоптимальнуюраскраску.Например,длялюбойоптимальнойраскраски,можноотсортироватьпоубываниюсначалавершиныизминимальнойегопоразмерусовокупностиодинаковораскрашенныхвершин.Затемсортируетсявтораяпоразмерусовокупность,итакдалее.Еслиприменитьжадныйалгоритмктакойпоследовательностивершин,тонайденнаяраскраскабудетоптимальной.Известноболеесильноеутверждение:графы,имеющиесовершенныйпорядокпозволяютполучитьпорядок,которыйоптималенкакдлясамогографа,такидлявсехегопорожденныхподграфов.ВсвоюочередьпоисктакогооптимальногопорядкадляобщегослучаяявляетсяNP-полнойзадачей(ещеипотому,чтотакоерешениеможетбытьиспользованоприпоискеоптимальнойраскраскиграфа,такжеNP-полнойзадачи).Поэтомуприраскрашиванииграфовдляуменьшенияколичествацветовиспользуются,какправило,эвристическиеалгоритмы,хотяониинегарантируютоптимальноеколичествоцветов (рис. 9).В свою очередь жадный алгоритм имеет различные варианты относительно порядка выбора последовательности перевода каждую вершину в каком-то определенном порядке и пытается раскрасить вершину с одним из цветов, используемых до сих пор. Другими словами, он пытается добавить вершину к одному из существующих цветовых классов. Если это невозможно, то создается новый класс цвета и вершине присваивается цвет этого класса.Рисунок 9. Неоптимальная и оптимальная раскраска вершин графа в зависимости от последовательности обхода вершинЭто порождает два очевидных варианта:• во-первых, когда есть больше чем один существующий класс цвета вершины, можно ввести правило, какой из них следует выбрать;• во-вторых, какой предопределяющий порядок присвоить вершинам. 1. Простой – ведет перебор классов в порядке 1 ... k последовательно и представляет собой метод, обычно называемый последовательным алгоритмом. 2.наибольший первый – назначает классы по числу вершин в текущее время, и ведет поиск по убыванию размера совокупности. Это создает тенденцию к построению больших независимых множеств. 3. Наименьший первый – назначает классы по числу вершин в текущее время в них, и ведет поиск по возрастанию размерасовокупности. Это нужно, как правило, для выравнивания размера цветовых классов. 4. случайная последовательность - выполняет поиск множества в случайном порядке. 5 Обратный порядок - выполняет поиск множества в k ...1 порядке.Эти варианты указывают, как программа должна сделать выбор, какой цвет класс использовать для вершины. Каждый из них, выбирает первый класс, встречающийся в указанном порядке поиска.Алгоритм 1 (Жадная раскраска).Задан граф G с множеством ребер E, множеством вершин V = {v1, ..., vn} и списком смежности Av. Построить функцию с: V→ N такую, что если ребро е = (vi,vj)∈Е, то с(vi) ≠с (vj).Шаг 1. Инициализация. Множество с(vj)← 0 для всех 1 ≤j≤nc(v1) ←1j← 2Шаг 2. с(vj)← min(к∈N | к> 0 и с(u)≠k∀∈Àvj)Шаг 3 Конец:j= n?• Если да, то останов: построена функция с с заданными свойствами.• Если нет, то j ← j+1 и перейти к шагу 2.Примечание. Этот алгоритм предназначен для реализации его в MATLAB. Таким образом, он включает в себя такие выражения, как j← 2, что означает "jприсваивается новое значение 2". Оператор ← иногда называют оператором присваивания. Алгоритм 2 (псевдокод).Задан граф G с множеством ребер E, множеством вершин V = {v1, ..., vn} и списком смежности Av. Построить функцию с: V→ N такую, что если ребро е = (vi,vj)∈Е, то с(vi) ≠с (vj). (1) Шаг 1. Начальное присвоение функции раскраски с(vj) нулевых значений по числу вершин: Множество с(vj)← 0 для всех 1 ≤ j≤n(2) Шаг 2. Присвоение первой вершине цвета по номером 1:c(v1) ←1.(3) Шаг 3. Организация цикла по числу вершин: for 2 ≤ j≤n {(4) Шаг 4. Выбрать цвет k > 0 для вершины vj, который будет отличаться от соседнихс(vj)← min (к∈N | к> 0 и с(u)≠k∀∈Àvj)(5) Конец цикла }Обе версии алгоритма выполняют одни и те же шаги, в том же порядке, так что сравнение этих двух примеров проясняет различные подходы к представлению алгоритмов.Алгоритм 3 Улучшенный алгоритм (псевдокод).Задание графа в этом алгоритме аналогично двум предыдущим.Шаг 1. Среди вершин графа G найти множества независимых вершин SШаг 2. Отсортировать независимые множества вершин графа по убыванию их мощности.Шаг 3. Цикл по количеству независимых множеств вершин Назначить текущий цвет i текущему множеству вершин S: c(S)=ii→ i+1Шаг 4 если все множества просмотрены V = ∅, конец цикла.Если используется алгоритм 2 для построения функции с: V→ N, то можно рассматривать его как k-раскраску, полагаяϕ(vj) = c (vj), где kзадано посредствомПо причинам, рассмотренным выше, это k дает лишь верхнюю границу хроматического числа G. Рисунок 10иллюстрирует процесс применения алгоритма жаднойраскраски двух графов, по одному в каждой колонке.Для графа в левой колонке, назовем ее G1-алгоритма производит 3-раскраску, которая на самом деле является оптимальной. Чтобы понять, почему, нужно обратить внимание, что подграф, состоящий из вершин v1, v2и v3 (вместе с соответствующимиребрами) изоморфен K3. Таким образом, нам нужно по крайней мере 3-х цвета для этих трех вершин. С другой стороны, жадный алгоритм дает явный пример 3-раскраски, откуда следует, что χ(G1) ≤ 3, таким образом, мы доказали, чтоχ(G1) = 3.Рисунок 10. Два примера применения алгоритма 2: процесс раскраски проходит сверху вниз. Граф в правой колонке (G2) изоморфен G1, но его вершины пронумерованы иначе, и это означает, что алгоритм 3,5 раскрашивает их в другом порядке и приходит к неоптимальнойk-раскраскеприk = 4.ЗаключениеРазнообразные задачи, возникающие при составлении расписаний, планировании производства коммунальных услуг, составлении графиков осмотра, хранении и транспортировке товаров и другие, могут быть представлены часто как задачи теории графов, тесно связанные как с задачей кратчайшего пути, таки сзадачей раскраски. Жадный алгоритм графа стал одним из основных и широко используемых как самостоятельно, так и в других методах.Предложенные алгоритм и их программная реализация будут полезны для решения практических приложений таких как распределениярегистроввмикропроцессорах,распараллеливаниячисленныхметодов,распределениячастотвспектрерадиоизлученийсцельюмаксимизациипропускнойспособностиканаловсвязи,теорииконечныхавтоматов.Список использованной литературыКормен Т. Х., Лейзерсон Ч. И., Ривест Р. Л., Штайн К. Алгоритмы: построение и анализ, 2-е изд. — М.: Вильямс, 2005. — 1296 с.Берж К. теория графов и ее применение: Пер. с франц. М., 1962.Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи: Пер. с англ. М., 1982.A. Kosowski, Classical Coloring of Graphs , AMS Contemporary Math, 2011, 1-20Гоппа В. Д. Введение в алгебраическую теорию информации. М.,1995.Кристофидес Н. Теория графов. Алгоритмический подход: Пер. с англ. М., 1978.R. M. Karp, Reducibility among combinatorial problems, Complexity of Computer Computations (R. E. Miller and J. W. Thatcher, eds.), New York: Plenum (1972) 85–103.(Qu, R.; E. K. Burke, B. Mccollum, L. T. G. Merlot, S. Y. Lee (2006). «A Survey of Search Methodologies and Automated Approaches for Examination Timetabling».), Kendall, Graham; Sigrid Knust, Celso C Ribeiro, Sebastián Urrutia (2009). «Scheduling in sports: An annotated bibliography».Comput. Oper. Res.(Elsevier Science Ltd.).DOI:10.1016/j.cor.2009.05.013.ISSN0305-0548;Marx, Daniel(2004). "Graph Coloring Problems and Their Applications in Scheduling".in Proc. John von Neumann PhD Students Conference: 1–2Roberts Fred S.Graph theory and its applications to problems of society. — Society for Industrial MathemaE. Malaguti, An exact approach for the Vertex Coloring Problem, Discrete Optimization, 2011, №8,174-190.D. Cosmin Porumbela, A search space “cartography” for guiding graph coloring heuristics, Computers &Operations Research, 2010, №37, 769-778.