Графы с цветными ребрами реферат
Обновлено: 04.07.2024
Целью моей курсовой работы являются описание методов вершинной и реберной раскраски графов.
Прежде всего, хотелось бы дать определения тому понятию, с которого и начинается рассмотрение данной темы, а именно с понятия раскраска графа.
Пусть Sn — множество целых чисел от 1 до п, которые мы будем называть цветами; n-раскраской графа G назовем такое отображение множества V(G) в Sn, при котором вершины, являющиеся концами одного ребра, окрашиваются в разные цвета (т.е. таким вершинам сопоставляются разные элементы из Sn).
Содержание
Введение: 3
Глава I. Вершинная раскраска графа 5
1.1 Основные понятия вершинной раскраски графа. 5
1.2 Переборный алгоритм для раскраски 13
Глава II. Реберная раскраска графа 15
2.1 Раскрытие понятия правильной реберной раскраски графа. 15
2.2 Методы реберной раскраски графа 16
2.3 Задачи на графы с цветными ребрами и вытекающие из них свойства… .22
2.4 Задача о несцепленных треугольниках с одноцветными сторонами…..…33
Заключение………………………………………………………………………….37
Литература 38
Вложенные файлы: 1 файл
Курсовая (Раскраска графов).docx
Рассмотрим все произвольные раскраски графа G. Рассмотрим те из них, при которых вершины и окрашены в разные цвета. Если добавить к графу G ребро , то они не изменятся, то есть останутся правильными. Рассмотрим раскраски, при которых и одного цвета. Все эти раскраски останутся правильными и для графа, полученного из G слиянием вершин u и v.
Если к некоторому произвольному графу добавлять ребра последовательно, не меняя его вершин, то на каком-то шаге мы получим полный граф. Аналогично мы получим полный граф, если в произвольном графе уменьшим число вершин, путем их отождествления, не меняя числа ребер.
Если граф G порядка n является деревом, то .
Пусть граф является деревом, тогда методом математической индукции докажем, что .
Базис индукции: при n=1 , f(T, t)=t; при n=2 ,
f(T, t)=t(t–1).
Индуктивное предположение: пусть условие теоремы верно при n=k.
Индуктивный переход: покажем, что условие теоремы выполняется при n=k+1. Рассмотрим граф . Представим это дерево в виде объединения любого его концевого ребра и дерева порядка k, которое получается, если удалить это концевое ребро из дерева порядка k+1. , причем эти два графа имеют ровно одну общую вершину, поэтому .
1.2 Переборный алгоритм для раскраски
Рассмотрим алгоритм решения задачи о раскраске, похожий на описанный выше алгоритм для задачи о независимом множестве. Сходство заключается в том, что задача для данного графа сводится к той же задаче для двух других графов. Поэтому снова возникает дерево вариантов, обход которого позволяет найти решение. Но есть и одно существенное различие, состоящее в том, что теперь два новых графа не будут подграфами исходного графа.
Выберем в данном графе две несмежные вершины и и построим два новых графа: , получающийся добавлением ребра к графу , и , получающийся из слиянием вершин и . Операция слияния состоит в удалении вершин и и добавлении новой вершины и ребер, соединяющих ее с каждой вершиной, с которой была смежна хотя бы одна из вершин , . На рис. 2показаны графы и , получающиеся из графа , изображенного на рис. 1с помощью этих операций, если в качестве и взять вершины и .
Если в правильной раскраске графа вершины и имеют разные цвета, то она будет правильной и для графа . Если же цвета вершин и в раскраске графа одинаковы, то граф можно раскрасить в то же число цветов: новая вершина окрашивается в тот цвет, в который окрашены вершины и , а все остальные вершины сохраняют те цвета, которые они имели в графе . И наоборот, раскраска каждого из графов , , очевидно, дает раскраску графа в то же число цветов. Поэтому что дает возможность рекурсивного нахождения раскраски графа в минимальное число цветов. Заметим, что граф имеет столько же вершин, сколько исходный граф, но у него больше ребер. Поэтому рекурсия в конечном счете приводит к полным графам, для которых задача о раскраске решается тривиально.
Глава II. Реберная раскраска графа
2.1 Раскрытие понятия правильной реберной раскраски графа.
Наряду с задачей о раскраске вершин имеется задача о раскраске ребер графа, когда цвета назначаются ребрам.
Пусть G — кубический граф. Рассмотрим множество Т = = , элементы которого назовем цветами. Реберной раскраской (или раскраской по Тейту) графа G назовем отображение t множества E(G) в Т, при котором ребра, инцидентные одной и той же вершине, отображаются в три различных цвета. Из определения следует, что граф, содержащий петлю, не допускает реберной раскраски.
Раскраска ребер (или реберная раскраска) называется правильной, если любые два ребра, имеющие общую вершину, окрашены в разные цвета. Минимальное число цветов, необходимое для правильной раскраски ребер графа , называется хроматическим индексом графа и обозначается через .
Обозначим через максимальную степень вершины в графе. При правильной реберной раскраске все ребра, инцидентные одной вершине, должны иметь разные цвета. Отсюда следует, что для любого графа выполняется неравенство . Для некоторых графов имеет место строгое неравенство, например, , а . Следующая теорема, доказанная В.Г.Визингом в 1964 г., показывает, что может отличаться от не более чем на 1
Для реберной раскраски графа так же существует ряд теорем
Для любого графа справедливы неравенства .
Приводимое ниже доказательство дает и план алгоритма для раскрашивания ребер графа не более чем в цветов. Оно основано на двух операциях перекрашивания, с описания которых и начнем. Далее будут рассматриваться частичные реберные раскраски, т.е. правильные раскраски, при которых некоторые ребра остаются неокрашенными.
Допустим, ребра графа правильно (может быть, частично) раскрашены. Пусть и - два из использованных в этой раскраске цветов. Рассмотрим подграф , образованный всеми ребрами, имеющими цвета или . В этом подграфе степень каждой вершины не превосходит 2, следовательно, каждая компонента связности в нем является цепью или циклом. Такую компоненту будем называть -компонентой. Если в какой-нибудь -компоненте поменять местами цвета и (т.е. все ребра, окрашенные в цвет , перекрасить в цвет и наоборот), то полученная раскраска тоже будет правильной. Эту операцию назовем перекраской -компоненты.
2.2 Методы реберной раскраски графа
Другая операция применяется к частично раскрашенному подграфу, называемому веером. Будем говорить, что при данной раскраске цвет отсутствует в вершине , если ни одно из ребер, инцидентных вершине , не окрашено в этот цвет.
Веером называется подграф , , состоящий из вершин и ребер , в котором:
- ребро не окрашено;
- ребро окрашено в цвет , ;
- в вершине отсутствует цвет , ;
- все попарно различны.
Перекраска веера состоит в том, что ребра окрашиваются соответственно в цвета , а ребро становится неокрашенным. Очевидно, новая частичная раскраска тоже будет правильной. На рис. 3 слева показан веер, а справа - результат его перекраски. Цвета ребер представлены числами, а отсутствующие цвета в вершинах - числами со знаком минус. Неокрашенное ребро изображено пунктиром.
Покажем, что с помощью этих двух процедур перекрашивания можно ребра любого графа окрасить в не более чем цветов. Допустим, что уже построена частичная правильная раскраска, использующая не более чем цветов, и имеется неокрашенное ребро . Так как число разрешенных цветов больше, чем максимальная степень вершины, то в каждой вершине какой-нибудь цвет отсутствует. Допустим, в вершине отсутствует цвет .
Будем строить веер следующим образом. Положим и пусть - цвет, отсутствующий в вершине . Получаем веер . Допустим, веер уже построен. Если цвет отличен от и имеется инцидентное вершине ребро этого цвета, то увеличиваем на 1 и полагаем , - цвет, отсутствующий в вершине . Этот процесс построения веера продолжается до тех пор, пока не наступит одно из следующих событий.
Нет ребра цвета , инцидентного вершине . Перекрашиваем веер, в результате ребро становится окрашенным, а ребро - неокрашенным, причем цвет отсутствует и в вершине , и в вершине . Но тогда можно это ребро окрасить в цвет , и мы получим правильную раскраску, в которой на одно окрашенное ребро больше.
Цвет совпадает с одним из цветов (именно этот случай изображен на рис. 4). Пусть . Рассмотрим вершины . В каждой из них отсутствует какой-нибудь из цветов или . Значит, в подграфе, образованном ребрами этих двух цветов, степень каждой из этих вершин не превосходит 1. Следовательно, все три вершины не могут принадлежать одной -компоненте.
Рассмотрим две возможности:
- Вершины и принадлежат разным -компонентам. Перекрасим веер . Ребро станет неокрашенным. Теперь перекрасим -компоненту, содержащую вершину . После этого цвет будет отсутствовать в вершине и ребро можно окрасить в этот цвет.
- Вершины и принадлежат разным -компонентам. Перекрасим веер . Ребро станет неокрашенным. Теперь перекрасим -компоненту, содержащую вершину . После этого цвет будет отсутствовать в вершине и ребро можно окрасить в этот цвет.
Итак, в любом случае получаем правильную раскраску, в которой добавилось еще одно раскрашенное ребро .
На рис. 5 иллюстрируются случаи 1 и 2 на примере веера из рис. 3. Здесь , . Левое изображение соответствует случаю 1: вершины и принадлежат разным -компонентам. После перекраски веера и -компоненты, содержащей вершину , появляется возможность окрасить ребро в цвет 5. Случай 2 показан справа: здесь вершины и принадлежат разным -компонентам, поэтому после перекраски веера , , , , и -компоненты, содержащей вершину , появляется возможность окрасить ребро в цвет 5.
Итак, все графы делятся на два класса: у одних хроматический индекс равен максимальной степени вершины, у других он на единицу больше. Оказывается, определение принадлежности графа к тому или иному классу является NP-трудной задачей. Алгоритм, который можно извлечь из доказательства теоремы 3.2, за полиномиальное время находит раскраску в не более чем цветов. Его можно назвать "идеальным" приближенным алгоритмом - более высокую точность имеет только точный алгоритм.
Рассмотрим кольцо R4, состоящее из четырех элементов, которые мы обозначим через 0, 1, ω, ω 2 . Операция умножения в этом кольце подчиняется закону ω 3 = 1, а операция сложения— следующим правилам: z + z = 0 для каждого z R4 и 1+ω + ω 2 = 0.
Поскольку каждый элемент из R4 является противоположным самому себе, то циклы и кограницы графа G над кольцом R4 можно рассматривать как цепи в E(G) без указания конкретного ориентанта графа G . Реберные раскраски графа G можно трактовать как всюду ненулевые циклы над R4 если в качестве цветов использовать ненулевые элементы кольца R4.
Рассмотрим следующие теоремы:
Теорема 1. Кубический граф G допускает реберную раскраску тогда и только тогда, когда F(G; 4) > 0.
Теорема 2. Пусть В — бонд графа G, t — реберная раскраска этого графа, пα, nβ и пγ — количество ребер бонда В, которые при раскраске t получают цвет α, β и γ соответственно. Тогда числа па,, пβ и nγ имеют одинаковую четность.
Доказательство. Бонд В является носителем кограницы графа G над R4, все коэффициенты которой равны 1. Эта кограница ортогональна циклу t. Следовательно,
Учитывая, далее, правила сложения в кольце R4, получаем утверждение теоремы.
Примером графа, не допускающего реберной раскраски, является, всякий кубический граф, содержащий перешеек.
Пусть, далее, кубический граф G связен и его бонд В имеет торцевые графы Н и К. Предположим сначала, что |В|=2. Преобразуем Н в кубический граф Н1 присоединением нового ребра А1, соединяющего вершины графа Н, являющиеся концами ребер из В. Будем называть Н остаточным графом бонда В, содержащим Н; А1 назовем пополняющим ребром. Существует, конечно, и второй остаточный граф бонда В, содержащий К.
Пусть теперь |B| = 3. Построим из G новый кубический граф Н1 заменяя К одной новой вершиной k, инцидентной всем трем ребрам бонда В. Аналогичной заменой графа Н образуем граф К1. Будем называть Н1 и К1 остаточными графами бонда В, содержащими Н и К соответственно.
Задачи на графы с цветными ребрами и вытекающие из них свойства
Рассматриваем графы, соответствующие таким ситуациям, в которых одни пары элементов множества находятся между собой в одном отношении, другие пары этого множества — в другом отношении, третьи — в третьем, но каждая пара — в одном отношении. Например, среди участников шахматного турнира к какому-то моменту могут быть такие, которые уже сыграли партию друг с другом, и такие, которые не сыграли. Среди множества стран есть страны, установившие между собой дипломатические связи, и страны, между которыми не установлены дипломатические связи. Для удобства на рисунках графов ребра, соответствующие одному отношению, окрашивают в один цвет, а ребра, соответствующие другому отношению, — во второй цвет, в третий цвет и т.д. Так как мы не можем выполнить рисунок в разных цветах, то присваиваем ребрам номера. Такие графы называются графами с цветными ребрами.
Свойства полных графов с цветными ребрами
Задача 1. Шесть человек участвуют в шахматном турнире, который проводится в один круг, то есть каждый шахматист встречается со всеми участниками по одному разу. Нужно доказать, что среди них всегда найдутся три участника турнира, которые провели уже все встречи между собой или еще не сыграли друг с другом ни одной партии.
Решение. Любые два участника турнира находятся между собой в одном из двух отношений: они либо уже сыграли между собой, либо еще не сыграли.
Каждому участнику поставим в соответствие вершину графа. Соединим вершины попарно ребрами двух цветов. Пусть ребро красного цвета (обозначенное цифрой 1) означает, что двое уже сыграли между собой, а синего (пронумерованное цифрой 2) — что не сыграли. Получим полный граф с шестью вершинами и ребрами двух цветов.
Теперь для решения задачи достаточно доказать, что в таком графе обязательно найдется "треугольник" с одноцветными сторонами.
Каждая вершина полученного графа принадлежит пяти ребрам. Скольким шахматистам одного цвета может принадлежать произвольная вершина такого графа? Пять принадлежащих одной вершине ребер могут быть окрашены без учета порядка следующим образом: , , , , , . То есть каждая вершина принадлежит, по меньшей мере, трем шахматистам одного цвета. Пусть, например, вершина принадлежит трем ребрам красного цвета:
- Для учеников 1-11 классов и дошкольников
- Бесплатные сертификаты учителям и участникам
Первой работой теории графов как математической дисциплины считают статью Эйлера (1736г.), в которой рассматривалась задача о Кёнигсбергских мостах. Эйлер показал, что нельзя обойти семь городских мостов и вернуться в исходную точку, пройдя по каждому мосту ровно один раз.
Следующий импульс теория графов получила спустя почти 100 лет с развитием исследований по электрическим сетям, кристаллографии, органической химии и другим наукам.
С графами, сами того не замечая, мы сталкиваемся постоянно. Например, графом является схема линий метрополитена. Точками на ней представлены станции, а линиями – пути движения поездов. Исследуя свою родословную и возводя ее к далекому предку, мы стоим так называемое генеалогическое древо. И это древо – граф.
Методы теории графов широко применяются в дискретной математике. Без них невозможно обойтись при анализе и синтезе различных дискретных преобразователей: функциональных блоков компьютеров, комплексов программ и т.д.
В настоящее время теория графов охватывает большой материал и активно развивается.
Теоретическая часть
Основные определения
Графом называется набор точек (эти точки называются вершинами), некоторые из которых объявляются смежными (или соседними). Считается, что смежные вершины соединены между собой ребрами (или дугами). Таким образом, ребро определяется парой вершин. Два ребра, у которых есть общая вершина, также называются смежными (или соседними).
Граф определяется как совокупность множества М с заданным на нем бинарным отношением: T M .
G = M , T >.
Между элементами М и Т определено отношение инцидентности, т.е. связи между двумя элементами множества М через один элемент множества Т, представлено на рисунке 1.
Граф называется ориентированным (или орграфом), если некоторые ребра имеют направление. Это означает, что в орграфе некоторая вершина может быть соединена с другой вершиной, а обратного соединения нет.
Геометрически граф часто изображают точками плоскости, причем соседние вершины соединены дугами (для орграфа некоторые дуги имеют направление, что обычно отмечают стрелкой).
Помимо этого, в теории графов рассматриваются также мультиграфы – это такие графы, в которых могут быть петли (т. е. некоторая вершина соединена сама с собой ребром) или некоторые пары вершины могут быть соединены между собой несколькими ребрами.
Маршрут в графе – это последовательность соседних (смежных) вершин. Ясно, что можно определить маршрут и как последовательность смежных ребер (в этом случае ребра приобретают направление). Заметим, что в маршруте могут повторяться вершины, но не ребра.
Маршрут называется циклом, если в нем первая вершина совпадает с последней.
Путь в графе (иногда говорят простой путь) – это маршрут без повторения вершин (а значит, и ребер).
Контур – это цикл без повторения вершин, за исключением первой вершины, совпадающей с последней.
Последовательности вершин (рис. 2): 1–2–3–4–2–5 не простой путь, а маршрут; последовательности 1–2–3–4–7–5 и 1–2–5 – простые пути; 1–2–3–4–2–5–6–1 –это цикл (но не контур); 1–2–5–6–1 – это контур.
Если имеется некоторый маршрут из вершины t в вершину s , заданный в виде последовательности ребер, которые в этом случае приобрели направление, и если в этот маршрут входит ребро, соединяющее вершины (i, j) , то это ребро по отношению к вершине i называют иногда прямой дугой, а по отношению к вершине j – обратной дугой (или обратным ребром).
Граф называется связным, если любые две его вершины можно соединить маршрутом (или путем). На рис. 2 изображен связный граф.
Ребро, при удалении которого граф перестает быть связным, иногда называют мостом или перешейком.
Следующее определение имеет смысл только для графов или мультиграфов без петель (но не для орграфов). Степень вершины – это число ребер, входящих в эту вершину.
Вершина называется висячей, если ее степень равна единице.
Лемма 1 . Если степень всех вершин в графе больше или равна двум, то граф обязательно содержит контур.
Доказательство. Действительно, выйдя из некоторой вершины и войдя в другую, всегда можно выйти из нее по другому ребру, так как степень вершины больше или равна двум. Выйти из вершины по новому ребру невозможно только в том случае, если эта вершина уже встречалась, а это означает, что можно выделить контур из вершин этого графа.
Задача раскраски графа считается классической в информатике. Созданные алгоритмы применяются для выдачи радиочастот, составления расписаний и других задач на распределение ресурсов.
К сожалению, не существует оптимального алгоритма. Задачу можно решить либо полным перебором, либо с приближенным значением.
Сложность полного перебора равна O(nn) , где n – это количество вершин. В реальной ситуации сложность, конечно, будет меньше – O(4n) или O(5n) , поскольку большинство вводимых человеком графов скорее будут планарными, либо иметь малое количество пересечений.
Однако, в любом случае, сложность полного перебора очень высока. И, поскольку, приближенные алгоритмы показывают довольно точные результаты, было решено использовать именно их. В программе реализовано два приближенных алгоритма:
1. Неявный перебор;
2. Эвристический метод.
Неявный перебор
Назначим каждой вершине свой номер ( xi — i -я вершина). Получаем первоначальную раскраску:
1. Окрасить xi в цвет 1.
1. Находим смежную вершину с максимальным номером, который меньше, чем у нее.
2. Пытаемся перекрасить её в цвет больший собственного, но меньший, чем максимальный цвет в графе.
3. Если это не удается, то делаешь шаг возвращения из этой вершины.
4. Если это удаётся, то по правилу первой фазы перекрашиваем вершины с большим номером.
5. Если при перекрашивании какая-то вершина затребовала максимальный цвет, от которого мы пытаемся избавиться, то делаем шаг возвращения из неё.
6. Если достигнута первая вершина, то завершаем работу.
Далее улучшаем раскраску. Отыскиваем первую по номеру вершину с максимальным цветом. Из неё делаем шаг возвращения:
1. Находим смежную вершину с максимальным номером, который меньше, чем у нее.
2. Пытаемся перекрасить её в цвет больший собственного, но меньший, чем максимальный цвет в графе.
3. Если это не удается, то делаешь шаг возвращения из этой вершины.
4. Если это удаётся, то по правилу первой фазы перекрашиваем вершины с большим номером.
5. Если при перекрашивании какая-то вершина затребовала максимальный цвет, от которого мы пытаемся избавиться, то делаем шаг возвращения из неё.
6. Если достигнута первая вершина, то завершаем работу.
Эвристический метод
Вначале выбираем первый цвет.
1. Сортируем вершины по количеству неокрашенных смежных вершин.
2. Последовательно окрашиваем вершины в выбранный цвет. Если у вершины уже есть смежная вершины с выбранный цветом, то оставляем ее неокрашенной.
3. Если остались неокрашенные вершины, то выбираем следующий цвет и переходим к пункту 1.
Алгоритм неявного перебора в большинстве случае должен давать правильный решение, поскольку во время шага возвращения происходит движение по дереву поиска в ширину.
Эвристический метод дает приемлемый результат, поскольку вначале окрашивает вершины с максимальной степенью.
1.2 Раскраска графа
Раскраской вершин графа называется назначение цветов его вершинам. Обычно цвета - это числа 1,2,…, k .
Тогда раскраска является функцией, определенной на множестве вершин графа и принимающей значения в множестве k >.
Раскраску можно также рассматривать как разбиение множества вершин:
= , где - множество вершин цвета i .
Множества называют цветными классами.
Раскраска называется правильной, если каждый цветной класс является независимым множеством. Иначе говоря, в правильной раскраске любые две смежные вершины должны иметь разные цвета.
Задача о раскраске состоит в нахождении правильной раскраски данного графа G в наименьшее число цветов. Это число называется хроматическим
числом графа и обозначается ( G ).
Правильная раскраска графа G может выглядеть следующим образом:
Рисунок 3- Пример раскраски графа
Функцией Гранди называется функция на вершинах графа, отображающая вершины в множество a > , причем если вершина xi окрашена в цвет с номером k , то функция Гранди h(xi) = k .
Ясно, что для данного графа хроматическое число является единственным, но функций Гранди может быть очень много. Естественно, что найти хотя бы одну функцию Гранди – это значит, найти одну из возможных “наилучших” раскрасок (таких раскрасок может быть много).
Заметим, что если данный граф является полным, т. е. любые две вершины являются смежными, то хроматическое число такого графа равно p , где p – число вершин.
1.3 Тестовый пример
В качестве примера возьмём граф, представленный на рисунке 1:
Рисунок 4 – Пример графа
1. Раскрашиваем вершины по порядку в минимально возможные цвета: 1 –красный, 2 – зеленый, 3 – зеленый, 4 – красный, 5 – синий.
2. Вершина номер 5 имеет максимальный цвет (с номером 3). Попытаемся от него избавиться: делаем шаг возвращения из вершины 5.
3. Смежная вершина с максимальным номером, которые меньше 5 – это 3. Перекрасить ее в цвет больший ее (2) и меньший, чем максимальный (3) – нельзя. Делаем шаг возвращения из вершины 3.
4. Смежная вершина с максимальным номером, которые меньше 3 – это 1. Мы достигли первую вершину и завершаем алгоритм.
1. Сортируем вершины по степени: 1, 3, 2, 4, 5.
2. Окрашиваем в первый цвет (красный). Мы можем окрасить вершины 1. Вершины 2 и 3 окрасить нельзя, поскольку они смежны с 1. Вершина 4 не
инидентна, так что может быть окрашена в красный. Смежную с первой вершину 5 окрасить нельзя.
3. Сортируем вершины по количеству смежных неокрашенных вершин: 3, 2, 5.
4. Выбираем следующий цвет – зеленый. Мы можем окрасить в него вершины 2 и 3.
5. Сортируем вершины по количеству смежных неокрашенных вершин: остаётся только 5.
6. Выбираем следующий цвет – синий (3).
7. Окрашиваем последую вершину 5 в синий цвет.
2. Постановка задачи
Задача: разработка программы, которая бы обеспечила ввод графа и его раскраску. Раскраска графа – присвоение каждой вершине графа значения (цвета), так чтобы вершины с одинаковым значением не были инцидентны. Количество используемых значений должно быть минимально.
Программа должна быть удобной в использовании. Ввод графа должен осуществляться через графический интерфейс. Должна быть предусмотрена правка структуры графа на любом этапе работы с программой. Рассматриваемый граф неориентированный и не имеет петель.
3. Практическая часть
3.1 Разработанный алгоритм
Разработанный алгоритм работает на основе операций с матрицей смежности.
Данный алгоритм реализуется следующим образом:
За основу берется матрица смежности M для данного графа G .
Затем создается массив A, в каждой строке которого содержится множество вершин A[i] . первым элементом этого множества является вершина , номер которой совпадает с номером строки. Остальные члены этого множества – все вершины данного графа G , смежные первой вершине из этого множества.
Далее с этим массивом A проводятся следующие манипуляции:
Множество вершин A[i] в каждой строке просматривается, начиная со второго элемента этого множества A[i] , и по матрице смежности M устанавливается, смежна ли данная вершина всем предыдущим вершинам из множества A[i] , начиная с первой – . Если обнаруживается, что одна из вершин при рассмотрении не смежна с другими вершинами (k=0,j-1) этого множества A[i] , то она удаляется из этого множества. Продолжается рассмотрение остальных вершин до тех пор, пока множество не рассмотренных вершин не станет пустым. Таким образом, из данного множества вершин A[i] , смежных с первой вершиной этого множества – будут удалены все те вершины, которые не смежны всем остальным вершинам этого множества A[i]. Таким образом, оставшееся множество вершин A[i] будет являться максимальным полным подграфом от первой вершины этого множества .
После рассмотрения одного множества A[i] в массиве A рассматриваются следующие, по той же схеме. Из них также удаляются вершины. В конечном счете будет получен массив A , в каждой i -й строке которого будет содержаться максимально полный подграф A[i] , возможный от i -й вершины .
На следующем шаге алгоритма будет создан еще один массив B , содержащий множество целых чисел. Каждый i -й элемент B[i] этого множества B представляет собой количество вершин в соответствующем максимально полном подграфе A[i]. Например если 3-й элемент данного множества равен 5, это означает, что максимально полный подграф, построенный от 3-ей вершины состоит из 5 вершин, включая 3-ю. множество вершин < >, которые составляют этот подграф A[3] является множеством вершин в 3 строке массива A .
После того, как были созданы массивы A и B , создается линейный список С , каждый элемент которого содержит множество вершин X , составляющих уникальный наибольший полный подграф графа G .
Очевидно, что массив A будет содержать в себе одинаковые множества вершин. Единственным отличием этих множеств друг от друга будет то, что первый элемент каждого такого множества будет отличен от первого элемента такого же множества, находящегося в массиве A .
Например, если в массиве A имеется следующее множество вершин, составляющее полный подграф: , что означает, что во 2 строке массива А содержится это множество вершин, состоящее из 4 элементов, массив В содержит 4 одинаковых элемента – 4 по адресам 2,4,5,7. Однако это означает, что в 4, 5 и 7 строках массива А будет содержаться то же самое множество вершин.
Во время формирования списка С этот факт учитывается.
Список формируется следующим образом: в массиве В ищется максимальный элемент . Это целое число, показывающее размер наибольшего полного подграфа графа G . Затем просматривается массив В . И если соответствующий элемент B[i] по адресу i равен , то создается новый элемент в списке, в него заносится наибольший полный подграф из массива А по адресу i . Проводится дальнейший просмотр массива В и ищутся другие подграфы, содержащие вершин. Если таковые находятся (а они обязательно находятся) то на этом этапе выполняется проверка, не добавлено ли уже это множество вершин A[i] в список НПП. Проверка осуществляется следующим образом: список С просматривается сначала, и каждое множество вершин, содержащееся в элементе этого списка сравнивается с множеством A[i]. Если обнаруживается, что такое множество A[i] уже содержится в списке С , то оно пропускается, происходит дальнейшее рассмотрение массива В . В противном случае, если такое множество не было найдено в списке, то создается еще одна ячейка списка С и в нее записывается множество A[i].
Таким образом, после того, как закончится рассмотрение массива В , то есть будут рассмотрены все возможные НПП и уникальные будут добавлены в список С , полученный список С будет содержать в себе все возможные НПП для данного графа G .
3.2 Описание логической структуры программы
Программа разбита на отдельные функциональные части – подпрограммы, которые распределяются по отдельным уровням иерархии. Каждая из подпрограмм решает только свою небольшую задачу по преобразованию данных, что позволяет упростить процесс написания и отладки программы в целом. Далее приводится описания назначения всех функций.
Функция WinMain является главной функцией программы, из которой производится вызов остальных функций.
Функция ABOUTDLG является функций всплывающего окна "О программе"
find_gr – функция ищет наиболее полный подграф от текущей (переданной) вершины и возвращает массив подграфов find_podgraf – функция создания конечного списка наибольших полных подграфов(с наибольшим кол-вом вершин).
Функция cr_matr - функция создания и вывода матриц смежности и инцидентности.
Функция paint_podgraf - рисует подграф в области, выделенной для графа. Передается номер графа, который надо нарисовать и список наибольших полных подграфов.
paint_mouse - процедура рисования графа мышью.
MAINDLG - оконная процедура главного окна программы.
Целью этапа проектирования программы является разработка алгоритмов решения поставленной задачи, т.е. разработка формальной последовательности действий, обеспечивающей получение требуемых результатов для заданных исходных данных. На этом этапе решаются следующие задачи:
разработка алгоритма основной программы;
разработка детальных алгоритмов отдельных подпрограмм;
3. инструкция пользователю.
Для работы с данной программой необходимо выбрать инструмент:
ребро (в этом же окне)
выбрать тип рисуемого графа
неориентированный(в этом же окне)
Для редактирования графа:
3.3 Решение контрольных примеров
Пример 1, случай, когда все страны соседние.
Рисунок 5- Пример зарисовки графа.
Пример 2, где не все страны между собой являются соседними.
Рисунок 6- Пример зарисовки графа
Графы достаточно широко применяются в математике, технике, экономике, управлении. Знание основ теории графов необходимо в различных областях, связанных с управлением производством, бизнесом (например, сетевой график строительства, графики доставки почты).
Аннотация: Реберная раскраска. Задачи на графы с цветными ребрами и вытекающие из них свойства. Задача о несцепленных треугольниках с одноцветными сторонами.
Реберная раскраска
Граф называется реберно - раскрашиваемым , если его ребра можно раскрасить красками таким образом, что никакие два смежных ребра не окажутся одного цвета. Если граф реберно -раскрашиваем, но не является реберно -раскрашиваемым, то называется хроматическим классом или хроматическим индексом , или реберно-хроматическим числом графа . При этом используется запись (G)=k" />
. На рисунке изображен граф , для которого (G)=4" />
.
Ясно, что если наибольшая из степеней вершин графа равна , то (G)\ge \rho" />
. Следующий результат, известный как теорема Визинга, дает точные оценки для хроматического класса графа . Доказательство этой теоремы можно найти у Оре (Ore O. The four-color problem , Academic Press, New York, 1967).
Теорема 7.1.(Визинг, 1964) Пусть в графе , не имеющем петель, наибольшая из степеней вершин равна тогда (G)\le \rho +1" />
.
Задача, состоящая в выяснении того, какие графы имеют хроматический класс , а какие , не решена. Однако в некоторых частных случаях соответствующие результаты находятся легко. Например, (C_)=2" />
или 3 в зависимости от того, четно или нечетно, а (W_ )=n-1" />
, при . Хроматические классы полных графов и полных двудольных графов вычисляются тоже просто.
.
Доказательство
Без потери общности можно считать, что и что граф " />
изображен так:
вершин расположены на горизонтальной линии под вершинами. Тогда искомая реберная раскраска получается последовательным окрашиванием ребер, инцидентных этим вершинам, с использованием следующих групп красок:
при этом краски из каждой группы располагаются по часовой стрелке, вокруг соответствующей вершины.
Теорема 7.3. (K_)=n" />
, если нечетно , и (K_)=n-1" />
, если четно.
Доказательство
В случае нечетного расположим вершины графа " />
в виде правильного -угольника. Тогда его ребра можно раскрасить следующим образом: сначала окрашиваем каждую сторону -угольника в свой цвет, а затем каждое из оставшихся ребер, диагонали -угольника, окрашиваем в тот же цвет, что и параллельная ему сторона.
То, что граф " />
не является реберно -раскрашиваемым, сразу же следует из того, что максимально возможное число ребер одного цвета равно .
В случае четного граф " />
можно рассматривать как соединение полного — графа " />
и отдельной вершины. Если в " />
окрасить ребра описанным выше способом, то для каждой вершины останется один неиспользованный цвет, причем все эти неиспользованные цвета будут различными. Таким образом, чтобы получить реберную раскраску " />
, достаточно окрасить оставшиеся ребра в соответствующие "неиспользованные" цвета.
1. Основные понятия. Хроматическое число
Характерным специфическим направлением теории графов
является цикл задач, связанный с раскрасками графов, в котором
изучаются разбиения множества вершин (ребер), обладающие
определенными свойствами, например, смежные вершины (ребра)
должны принадлежать различным множествам (вершины или ребра из
одного множества окрашиваются одним цветом).
История возникновения теории графов связана с задачей о
раскраске графов.
Задача о четырех красках. Формулировка задачи проста и не
соответствует всей глубине и сложности проблемы: можно ли на любой
политико-административной карте раскрасить страны так, чтобы
никакие две страны, имеющие общую границу, не были раскрашены
одинаковой краской, и чтобы были использованы всего четыре краски.
Уточним, что если две страны граничат по точке, то они не считаются
имеющими общую границу.
Каждый многоугольный граф можно представить себе как некоторую
географическую карту, где грани - это страны, а бесконечная грань- окружающий их
океан. На такой карте все страны и океан раскрашиваются так, чтобы их можно было
отличить друг от друга. Для этого страны с общей границей должны быть раскрашены
в разные цвета. Если в нашем распоряжении имеется достаточное количество красок,
это не составит никакого труда. Намного сложнее решить вопрос о наименьшем
количестве красок, достаточного для такого раскрашивания стран данной карты
Задача эта приобрела известность с 1879 г., когда английский
математик Артур Кэпи привел ее формулировку на заседании
английского королевского научного общества; добавив, что не мог ее
решить, хотя и размышлял над ней длительное время. С тех пор
многие выдающиеся математики пробовали свои силы в решении этой
задачи.
В терминах графов задача может быть поставлена следующим
образом:
Дан произвольный полностью неориентированный плоский граф G.
Можно ли каждую вершину графа G раскрасить с помощью одной из
четырех красок так, чтобы никакие две смежные вершины (вершины,
соединенные хотя бы одним ребром) не были раскрашены в один цвет.
Проблема четырех красок до сих пор не решена. Удалось лишь доказать, что
такую раскраску можно осуществить для всех плоских графов с числом
вершин, не превосходящим 38.
Другое применение раскраски в графах может быть
использовано при:
распределение памяти в ЭВМ;
проектирование сетей телевизионного вещания;
распределение частот и областей сотовых систем связи.
Задача об определении минимального числа красок, нужных
для правильной раскраски графа, которую рассмотрим,
является одной из первых задач теории графов. При этом
рассматриваемый граф должен быть
полностью
неориентированный без кратных ребер и петель.
Виды раскрасок
Раскраска вершин.
Терминология, в которой метки называются цветами,
происходит от раскраски политических карт. Такие метки как красный
или синий используются только когда число цветов мало, обычно же
подразумевается, что метки являются целыми числами .
Раскраска с использованием k цветов называется k-раскраской.
Определение. Наименьшее число цветов, необходимое для раскраски
графа G называется его хроматическим числом и часто записывается
как X(G). ( Иногда используется Y(G), с тех пор как X(G) обозначает Эйлерову
характеристику).
Подмножество вершин, выделенных одним цветом, называется
цветовым классом, каждый такой класс формирует независимый
набор. Таким образом, k-раскраска - это то же самое, что и разделение
вершин на k независимых наборов.
Пример - Построение раскраски графа K8 в 7 цветов
Рисунок 2 - Граф может быть раскрашен 3 цветами 12 способами
Хроматический многочлен
Хроматический многочлен считает число возможных вариантов
раскраски графа с использованием не более чем заданного числа
цветов.
Например, граф на рисунке 2 может может быть раскрашен 12
способами с использованием 3 цветов. Двумя цветами он не может
быть окрашен в принципе.
Используя 4 цвета, получаем 24+4*12 = 72 вариантов
раскраски: при использовании всех 4 цветов, есть 4! = 24 корректных
способа (каждое присвоение 4 цветов для любого графа из 4 вершин
является корректным); и для каждых 3 цветов из этих 4 есть 12
способов раскраски.
11. 2. Алгоритмы раскраски графа
Алгоритм раскраски графа позволяет находить (точное
или
приближенное)
значение
хроматического
числа
произвольного графа и соответствующую этому значению
раскраску вершин.
Граф G называют r-хроматическим, если его вершины могут
быть раскрашены с использованием r цветов (красок) так, что не
найдется двух смежных вершин одного цвета.
Наименьшее число r, такое, что граф G является rхроматическим, называется хроматическим числом графа G.
Задача нахождения хроматического числа графа называется
задачей о раскраске (или задачей раскраски) графа.
Соответствующая этому числу раскраска вершин разбивает
множество вершин графа на r подмножеств, каждое из которых
содержит вершины одного цвета.
Эти множества являются независимыми, поскольку в
пределах одного множества нет двух смежных вершин.
Правильная
раскраска
следующим образом:
графа G может
выглядеть
Рассмотрим последовательный метод, основанный на
упорядочивании множества вершин.
Формальное описание
1. Упорядочить вершины по невозрастанию степени.
2. Окрасить первую вершину в цвет 1.
3. Выбрать цвет окраски 1.
4. Пока не окрашены все вершины, повторять п.4.1.-4.2.:
4.1. Окрасить в выбранный цвет всякую вершину, которая не
смежна с другой, уже окрашенной в этот цвет.
4.2. Выбрать следующий цвет.
Раскраска графа по степеням вершин
Алгоритм
1.Упорядочить вершины по степеням начиная с наибольшей
степени вершины.
2.Задать начальное значение счетчика k=1.
3.Первую вершину окрашиваем в цвет k и заносим в букет
B(k).
4.Просматриваем следующую неокрашенную вершину, если
она несмежная с вершинами букета B(k) то окрашиваем ее в
цвет k, иначе пропускаем.
5.Проверяем количество просмотренных вершин, если i n (iномер текущей вершины), то возврат в п.4, иначе k=k+1 и
просмотр списка начинается заново исключая окрашенные
вершины.
6.Проверка на окончание поиска: если неокрашенных вершин
не осталось, то конец поиска, иначе п.5.
В этом простейшем из методов вершины вначале
располагаются в порядке невозрастания их степеней.
Первая вершина окрашивается в цвет 1; затем список вершин
просматривается сверху вниз (по невозрастанию степеней) и в цвет 1
окрашивается всякая вершина, которая не смежна с другой, уже
окрашенной в этот цвет.
Потом возвращаемся к первой в списке неокрашенной вершине,
окрашиваем ее в цвет 2 и снова просматриваем список вершин
сверху вниз, окрашивая в цвет 2 любую неокрашенную вершину,
которая не соединена ребром с другой, уже окрашенной в цвет 2
вершиной. Аналогично действуем с цветами 3, 4 и т. д., пока не будут
окрашены все вершины.
Число использованных цветов будет тогда приближенным значением
хроматического числа графа.
Приведенный алгоритм можно модифицировать.
Для этого после каждого шага нужно упорядочивать
неокрашенные вершины.
Простая модификация описанной процедуры состоит в
переупорядочивании неокрашенных вершин по невозрастанию
их относительных степеней.
Под относительными степенями понимаются степени
соответствующих вершин в неокрашенном подграфе исходного
графа.
В данной модификации предполагалось, что если две
вершины имеют одинаковые степени, то порядок таких вершин
случаен. Такие вершины можно также упорядочить, но уже по
двухшаговым степеням.
Двухшаговую степень определим как сумму относительных
степеней инцидентных вершин. Аналогично можно поступать и
далее.
Алгоритм с использованием независимого
множества вершин
Независимое множество вершин S – это такое подмножество
вершин, в котором никакие две вершины этого подмножества не
соединены ребром.
Максимальное независимое множество вершин Smax - это
независимое множество вершин, не являющееся собственным
подмножеством никакого другого независимого множества вершин. Оно
содержит наибольшее число вершин. В графе может быть несколько Smax..
Для отыскания Smax существует несколько методов. Точный метод основан
на булевой алгебре. Он достаточно сложен.
Рассмотрим приближенный метод
Метод выбора Smax из нескольких S: от каждой вершины графа
определяются все независимые множества вершин, из которых выбирается
множество с максимальной мощностью.
Алгоритм определения независимого множества S
1.
2.
3.
Выбирается начальная вершина v0 и заносится в S.
Рассматривается следующая вершина vi , если vi несмежная с S,
то она включается в S, иначе не включается.
Проверка на окончание: если просмотрены все вершины, то –
конец, иначе п.2.
Алгоритм раскраски с использованием независимого
множества вершин
Рассмотрим следующую схему рекурсивной процедуры Р:
1. Выбрать в графе G некоторое максимальное независимое
множество вершин Smax.
2. Окрасить вершины множества Smax в очередной цвет.
3. Применить процедуру Р к графу G\ Smax.
Пример: задан граф
Раскрасить с использованием
независимых множеств вершин
Определим Smax
Smax1= – 1 цвет
Smax2= – 2 цвет
Smax3= – 3 цвет
Smax4= – 4 цвет
Читайте также: