Государственный университет Республики Молдова

 
 

Физический  факультет

Кафедра физики и информатики 
 
 
 
 
 
 
 
 
 
 

Лабораторная  работа №3

“ Раскраска Графа”

 
 
 
 
 
 
 
 
 
 
 
 

Выполнил:

студент 4-го курса

группа 4.2 TI

Цилинский Александр 
 
 
 

Проверила:

Новак Людмила 
 
 
 
 

Кишинев 2011

 

Условия задания: Создание программы для раскраски рёбер графа минимальным количеством цветов.

Определения.

Вершина, Узел — базовое понятие: точка, где могут сходиться/выходить рёбра и/или дуги. Множество вершин графа G обозначается V(G)

Ребро графа — базовое понятие. Ребро соединяет две вершины графа.

Инцидентность — если v₁,v₂ — вершины, а e = (v₁,v₂) — соединяющее их ребро, тогда вершина v₁ и ребро e инцидентны, вершина v₂ и ребро e тоже инцидентны.

Окружение — длина наибольшего простого цикла в графе.

Степень вершины v — количество рёбер, инцидентных вершине v. Обозначается d(v). Минимальная степень вершины графа G обозначается δ(G). а максимальная — Δ(G).

Цепь в графе — маршрут, все рёбра которого различны.

Маршрут в графе — это чередующаяся последовательность вершин и рёбер v₀,e₁,v₁,e₂,v₂,...,e_k,v_k, в которой любые два соседних элемента инцидентны.

Раскраска графа — разбиение вершин на множества (называемые цветами). Если при этом нет двух смежных вершин принадлежащих одному и тому же множеству (то есть две смежные вершины всегда разного цвета), то такая раскраска называется правильной.

Хроматическое число графа — минимальное количество цветов, требуемое для раскраски вершин графа, при которой любые вершины, соединенные ребром, раскрашены в разные цвета. 

Пример  работы программы и её алгоритма.

     В примере буду работать со следующим  произвольным графом: 

 
 

Для программного задания графа использую матрицу  инцидентности:

            X0        X1      X2       X3       X4 X5 X6 X7

E0 1 1 0 0 0 0 0 0

E1 0 1 1 0 0 0 0 0

E2 0 0 1 1 0 0 0 0

E3 0 0 0 1 1 0 0 0

E4 0 0 0 0 1 1 0 0

E5 0 0 0 0 0 1 1 0

E6 0 0 0 1 0 0 0 1

E7 1 0 0 0 0 0 1 0

E8 0 1 0 0 0 0 1 0

E9 0 0 1 0 0 0 1 0

E10 0 0 0 1 0 0 1 0 
 

Запускаю программу  и ввожу размерность матрицы (Рис. 1). Далее ввожу матрицу из примера и нажимаю кнопку «Ввод» (Рис. 2), после чего начинает работать алгоритм программы:

                                                           

                           (Рис. 1)                      (Рис. 2)

1. Выбирается вершина максимальной степени.
2. Каждому ребру, из окружения вершины максимальной степени, присваиваются разные цвета, и данная вершина исключается из дальнейшего поиска.
3. До тех пор пока не будут окрашены все рёбра, проводить следующие операции:
1. Найти неокрашенное ребро, и окружение вершин, образующих это ребро, а так же цвет каждого из рёбер окружения.
2. Найти минимальный свободный цвет из окружения неокрашенного ребра.
3. Раскрасить ребро минимальным свободным цветом.

Результат можно  увидеть на рисунке ниже:  

 

Вывод.

     В результате выполненной работы были изучены основные понятия и термины  относительно раскраски графов. Были рассмотрены основные алгоритмы  раскраски графов, и применён на практике один из них. Предложенный алгоритм является универсальным для любых графов, так как берутся в расчёт все рёбра из окружения вершин, образующих неокрашенное ребро. Это полностью исключает повторение цветов. Благодаря первоначальной раскраске рёбер окружения вершины максимальной степени, исключается чрезмерное использование цветов. Даже если в графе существует две, и более вершин с максимальной степенью, то алгоритм выберет одну из них (ту из них, которая попадётся последней), раскрасит всё её окружение, а затем все остальные рёбра, что в итоге не повлияет на верность вычисления программы.