Министерство образования Республики Беларусь

Учреждение образования

«Гомельский государственный университет

им. Ф. Скорины»

Математический факультет

Кафедра МПУ

Алгоритмы на графах. Правильные раскраски. Потоки в сетях, паросочетания

Курсовая работа

Исполнитель:

Студентка группы М-32

Голубкина А.Ю.

Гомель 2007

Содержание

• Введение
• 1 Правильные раскраски
• 2. Поиск минимальной раскраски вершин графа
• 3. Использование задачи о наименьшем покрытии при раскраске вершин графа
• 4. Потоки в сетях, паросочетания
• 4.1 Постановка задачи
• 4.2 Метод построения максимального потока в сети
• 4.3 Наибольшее паросочетание в двудольном графе
• Заключение
• Литература

Введение

Определим граф как конечное множество вершин V и набор E неупорядоченных и упорядоченных пар вершин и обозначим G=(V,E). Мощности множеств V и E будем обозначать буквами N и M. Неупорядоченная пара вершин называется ребром, а упорядоченная пара - дугой. Граф, содержащий только ребра, называется неориентированным; граф, содержащий только дуги, - ориентированным, или орграфом. Вершины, соединенные ребром, называются смежными. Ребра, имеющие общую вершину, также называются смежными. Ребро и любая из его двух вершин называются инцидентными. Говорят, что ребро (u, v) соединяет вершины u и v. Каждый граф можно представить на плоскости множеством точек, соответствующих вершинам, которые соединены линиями, соответствующими ребрам. В трехмерном пространстве любой граф можно представить таким образом, что линии (ребра) не будут пересекаться.

Способы описания. Выбор соответствующей структуры данных для представления графа имеет принципиальное значение при разработке эффективных алгоритмов. При решении задач используются следующие четыре основных способа описания графа: матрица инциденций; матрица смежности; списки связи и перечни ребер. Мы будем использовать только два: матрицу смежности и перечень ребер.

Матрица смежности - это двумерный массив размерности N*N.

A[i,j]=

Для хранения перечня ребер необходим двумерный массив R

размерности M*2. Строка массива описывает ребро.

1. Правильные раскраски

Пусть G=(V,E) - неориентированный граф. Произвольная функция f:V{1,2,...,k}, где k принадлежит множеству натуральных чисел, называется вершинной k-раскраской графа G. Раскраска называется правильной, если f(u)f(v), для любых смежных вершин u и v. Граф, для которого существует правильная k-раскраска, называется k-раскрашиваемым. Минимальное число k, при котором граф G является k-раскрашиваемым, называется хроматическим числом графа и обозначается (G).

Пример.(G)=3. Меньшим количеством цветов граф правильно раскрасить нельзя из-за наличия треугольников. Рядом с “кружками” - вершинами графа - указаны номера цветов.

Метод получения правильной раскраски. Идея достаточно проста. Закрашиваем очередную вершину в минимально возможный цвет. Введем следующие структуры данных.

Const Nmax=100; {максимальное количество вершин графа}

Type V=0..Nmax;

Ss=Set of V;

My_array=array[1..Nmax] of V;

Var Gr:My_array;{Gr - каждой вершине графа определяется номер цвета}

Для примера, приведенного выше, массив Gr имеет вид: Gr[1]=Gr[3]=Gr[5]=1; Gr[2]=Gr[4]=Gr[7]=2; Gr[6]=3.

Фрагмент основной логики

....

<формирование описания графа>;

for i:=1 to N do Gr[i]:=Color(i,0);

<вывод решения>;

Поиск цвета раскраски для одной вершины можно реализовать с помощью следующей функции:

function Color(i,t:V):integer;{i - номер окрашиваемой вершины, t - номер цвета, с которого следует искать раскраску данной вершины}

{A - матрица смежности, Gr - результирующий массив}

var Ws:Ss;

j:byte;

begin

Ws:=[ ];

for j:=1 to i-1 do {формируем множество цветов, в которые окрашены смежные вершины с меньшими номерами}

if A[j,i]=1 then Ws:=Ws+[Gr[j]];

j:=t;

repeat {поиск минимального номера цвета, в который можно окрасить данную вершину}

Inc(j);

until Not(j in Ws);

Color:=j;

end;

Пример. Получаем правильную раскраску: Gr[1]=1, Gr[2]=Gr[4]=2, Gr[3]=3, Gr[5]=4. Однако минимальной раскраской является: Gr[1]=1, Gr[2]=Gr[5]=2, и Gr[3]=Gr[4]=3, и хроматическое число графа равно трем.

2. Поиск минимальной раскраски вершин графа

Метод основан на простой идее[7], и в некоторых случаях он дает точный результат. Пусть получена правильная раскраска графа, q - количество цветов в этой раскраске. Если существует раскраска, использующая только q-1 цветов, то все вершины, окрашенные в цвет q, должны быть окрашены в цвет g, меньший q. Согласно логике формирования правильной раскраски вершина была окрашена в цвет q, потому что не могла быть окрашена в цвет с меньшим номером. Следовательно, необходимо попробовать изменить цвет у вершин, смежных с рассматриваемой. Но как это сделать? Найдем вершину с минимальным номером, окрашенную в цвет q, и просмотрим вершины, смежные с найденной. Попытаемся окрашивать смежные вершины не в минимально возможный цвет. Для этого находим очередную смежную вершину и стараемся окрасить ее в другой цвет. Если это получается, то перекрашиваем вершины с большими номерами по методу правильной раскраски. При неудаче, когда изменить цвет не удалось или правильная раскраска не уменьшила количества цветов, переходим к следующей вершине. И так, пока не будут просмотрены все смежные вершины.

Опишем логику, используя функцию Color предыдущего параграфа.

var MaxC,MinNum,i:V;

procedure MaxMin(var c,t:V);

begin

...

end;

procedure Change(t:V);

begin

...

end;

begin

<ввод данных, инициализация переменных>;

for i:=1 to N do Gr[i]:=Color(i,0);{первая правильная раскраска}

MaxC:=0;MinNum:=0;

repeat

<найти вершину с минимальным номером(MinNum), имеющую максимальный цвет раскраски(MaxC) - процедура MaxMin(MaxC,MinNum) >;

<изменить цвет раскраски в соответствии с описанной идеей - процедура Change(MinNum)>;

until MaxC=Gr[MinNum];

<вывод минимальной раскраски>;

end.

Если работа процедуры MaxMin достаточно очевидна, то Change требует дальнейшего уточнения.

procedure Change(t:V);

var r,q:V;

Ws:Ss;

function MaxCon(l:V;Rs:Ss):V;{находим смежную с l вершину с наибольшим номером и не принадлежащую множеству Rs}

var i:V;

begin

for i:=l-1 downto 1 do

if (A[l,i]=1) and( not(i in Rs) then begin MaxCon:=i;

exit

end

MaxCon:=0;

end;

begin

Ws:=[];

q:=MaxCon(t,Ws);

while q<>0 do begin

r:=Color(q,Gr[q]);

if r<MaxC then <изменить цвет у вершин с номерами большими t по методу правильной раскраски>

else Ws:=Ws+[q];

q:=MaxCon(t,Ws);

end;

end;

Осталось заметить, что при изменении цвета у вершин с номерами, большими значения t, по методу правильной раскраски следует запоминать в рабочих переменных значения Gr и MaxC, так как при неудаче ( раскраску не улучшим) их необходимо восстанавливать, и на этом закончить уточнение логики.

При любом упорядочении вершин допустимые цвета j для вершины с номером i удовлетворяют условию ji . Это очевидно, так как вершине i предшествует i-1 вершина, и, следовательно, никакой цвет j>i не использовался. Итак, для вершины 1 допустимый цвет 1, для 2 - цвет 1 и 2 и так далее. С точки зрения скорости вычислений вершины следует помечать так, чтобы первые q вершин образовывали наибольшую клику графа G. Это приведет к тому, что каждая из этих вершин имеет один допустимый цвет и процесс возврата в алгоритме можно будет заканчивать при достижении вершины из этого множества.

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



цвета при правильной раскраске, вторая - при минимальной.

Для графов на первом и третьем рисунках алгоритм дает правильный результат. Для графа на втором рисунке необходимо просматривать вершины, не смежные для вершины с номером 6, а для этого необходимо модифицировать алгоритм. Самый интересный случай на последнем рисунке. Мы не можем получить минимальную раскраску с помощью рассмотренного алгоритма, хотя она, конечно, существует и совпадает с предыдущей.

3. Использование задачи о наименьшем покрытии при раскраске вершин графа

При любой правильной раскраске графа G множество вершин, окрашиваемых в один и тот же цвет, является независимым множеством. Поэтому раскраску можно понимать как разбиение вершин графа на независимые множества. Если рассматривать только максимальные независимые множества, то раскраска - это не что иное, как покрытие вершин графа G множествами этого типа. В том случае, когда вершина принадлежит не одному максимальному независимому множеству, допустимы различные раскраски с одним и тем же количеством цветов. Эту вершину можно окрашивать в цвета тех множеств, которым она принадлежит. Исходным положением метода является получение всех максимальных независимых множеств и хранение их в некоторой матрице M (N*W), где W - количество максимальных независимых множеств. Элемент матрицы M[i,j] равен единице, если вершина с номером i принадлежит множеству с номером j, и нулю в противном случае. Если затем каждому столбцу поставить в соответствие единичную стоимость, то задача раскраски не что иное, как поиск минимального количества столбцов в матрице M, покрывающих все ее строки. Каждый столбец соответствует определенному цвету.

1 2 3 4 5

1 1 1 0 0 0

2 1 0 0 1 0

3 0 0 1 0 0

4 0 0 1 1 1

5 0 1 0 0 1

A * * *

B * * *

Пример. Имеем пять максимальных независимых множеств и два варианта решения задачи о покрытии (строки A и B). В обоих случаях вершина 4 может быть окрашена как во второй, так и в третий цвета.

4. Потоки в сетях, паросочетания

4.1 Постановка задачи

Одной из задач теории графов является задача определения максимального потока, протекающего от некоторой вершины s графа (источника) к некоторой вершине t (стоку). При этом каждой дуге (граф ориентированный) (i,j) приписана некоторая пропускная способность С(i,j), определяющая максимальное значение потока, который может протекать по данной дуге. Содержательных интерпретаций задачи достаточно много, и, безусловно, они усилят и сделают более понятными сложные занятия по этой проблематике.

Метод решения задачи о максимальном потоке от s к t был предложен Фордом и Фалкерсоном, и их “техника меток” составляет основу других алгоритмов решения многочисленных задач, являющихся обобщениями или расширениями указанной задачи. Одним из фундаментальных фактов теории потоков в сетях является классическая теорема о максимальном потоке и минимальном разрезе. Разрезом называют множество дуг, удаление которых из сети приводит к “разрыву” всех путей, ведущих из s в t. Пропускная способность разреза - это суммарная пропускная способность дуг, его составляющих. Разрез с минимальной пропускной способностью называют минимальным разрезом. Теорема (Форд и Фалкерсон). Величина каждого потока из s в t не превосходит пропускной способности минимального разреза, разделяющего s и t, причем существует поток, достигающий этого значения. Теорема устанавливает эквивалентность задач нахождения максимального потока и минимального разреза, однако не определяет метода их поиска.



Пример. Показана сеть, источник - вершина 1, сток - вершина 6, в круглых скобках у дуг указаны их пропускные способности. Минимальный разрез - дуги (1, 2) и (3, 4), следовательно, согласно теореме максимальный поток равен 4. Разрез определен путем простого перебора. Логика его “лобового” поиска очевидна. Осуществляем перебор по дугам путем генерации всех возможных подмножеств дуг. Для каждого подмножества дуг проверяем, является ли оно разрезом. Если является, то вычисляем его пропускную способность и сравниваем ее с минимальным значением. При положительном результате сравнения запоминаем разрез и изменяем значение минимума. Удачный выбор данных позволяет сделать программный код компактным, но очевидно, что даже при наличии различных отсечений в переборе метод применим только для небольших сетей. Однако, как найти максимальный поток, то есть его распределение по дугам, по-прежнему открытый вопрос. “Техника меток” Форда и Фалкерсона заключается в последовательном (итерационном) построении максимального потока путем поиска на каждом шаге увеличивающейся цепи, то есть пути (последовательности дуг), поток по которой можно увеличить. При этом узлы (вершины графа) специальным образом помечаются. Отсюда и возник термин “метка”.



Пример из работы [9]. Рядом с пропускными способностями дуг указаны потоки, построенные на этих дугах. На рисунке поток через сеть равен 10 и найдена увеличивающаяся цепочка, выделенная “жирными” линиями. Обратите внимание на ориентацию дуг,

входящих в цепочку. По данной цепочке можно пропустить поток, равный 1, пропускная способность дуги (5, 6). Изменяем суммарный поток, его значение становится равным 11. Поток увеличен, необходимо продолжить поиск увеличивающихся цепочек; если окажется, что построить их нельзя, то результирующий поток максимален. Заметим, что для данного примера это значение потока окончательное. Обратите внимание на то, как изменен поток на дугах сети в зависимости от их ориентации.

4.2 Метод построения максимального потока в сети

Рассмотрим метод на примере. Пусть дана сеть G=(V,E), узлом-источником является вершина 1, узлом-стоком - вершина 6. Построим максимальный поток (F) между этими вершинами. Начальное значение F нулевое. Очевидно, что структурой данных для описания F является матрица того же типа, что и матрица С, в которой определены пропускные способности дуг.

Первая итерация. Присвоим вершине 1 метку [1,@]. Первый шаг. Рассмотрим дуги, началом которых является вершина 1 - дуги (1,2) и (1,3). Вершины 2 и 3 не помечены, поэтому присваиваем им метки, для

2-й - [1,2] и 3-й - [1,6]. Что представляют из себя метки? Первая цифра - номер вершины, из которой идет поток, вторая цифра - численное значение потока, который можно передать по этой дуге. Второй шаг. Выберем помеченную, но не просмотренную вершину. Первой в соответствующей структуре данных записана вершина 2. Рассмотрим дуги, для которых она является началом - дуги (2,4) и (2,5). Вершины 4 и 5 не помечены. Присвоим им метки - [2,2] и [2,2]. Итак, на втором шаге вершина 2 просмотрена, вершины 3, 4, 5 помечены, но не просмотрены, остальные вершины не помечены. Третий шаг. Выбираем вершину 3. Рассмотрим дугу (3,4). Вершина 4 помечена. Переходим к следующей вершине - четвертой, соответствующая дуга - (4,6). Вершина 6 не помечена. Присваиваем ей метку [4,2]. Мы достигли вершины-стока, тем самым найдя путь (последовательность дуг), поток по которым можно увеличить. Информация об этом пути содержат метки вершин. В данном случае путь или увеличивающаяся цепочка 1246. Максимально возможный поток, который можно передать по дугам этого пути, определяется второй цифрой метки вершины стока, то есть 2. Поток в сети стал равным 2.

Вторая итерация. Первый шаг. Присвоим вершине 1 метку [1,@]. Рассмотрим дуги, началом которых является помеченная вершина 1. Это дуги (1,2) и (1,3). Вершина 2 не может быть помечена, так как пропускная способность дуги (1,2) исчерпана. Вершине 3 присваиваем метку [1,6]. Второй шаг. Выберем помеченную, но не просмотренную вершину. Это вершина 3. Повторяем действия. В результате вершина 4 получает метку [3,2]. Третий шаг. Выбираем вершину 4, только она помечена и не просмотрена. Вершине 6 присваиваем метку [4,1]. Почему только одна единица потока? На предыдущей итерации израсходованы две единицы пропускной способности данной дуги, осталась только одна. Вершина-сток достигнута. Найдена увеличивающая поток цепочка, это 1346, по которой можно ”протащить” единичный поток. Результирующий поток в сети равен 3.



Третья итерация. Вершине 1 присваиваем метку [1,@]. Первый шаг. Результат - метка [1,5] у вершины 3. Второй шаг - метка [3,1] у вершины 4. Третий шаг. Пропускная способность дуги(4,6) израсходована полностью. Однако есть обратная дуга (2,4), по которой передается поток, не равный нулю (обратите внимание на текст, выделенный курсивом - “изюминка” метода). Попробуем перераспределить поток. Нам необходимо передать из вершины 4 поток, равный единице (зафиксирован в метке вершины). Задержим единицу потока в вершине 2, то есть вернем единицу потока из вершины 4 в вершину 2. Эту особенность зафиксируем в метке вершины 2 - [-4,1]. Тогда единицу потока из вершины 4 мы передадим по сети вместо той, которая задержана в вершине 2, а единицу потока из вершины 2 попытаемся “протолкнуть” по сети, используя другие дуги. Итак, вершина 4 просмотрена, вершина 2 помечена, вершины 5 и 6 не помечены. Четвертый и пятый шаги очевидны. Передаем единицу потока из вершины 2 в вершину 6 через вершину 5. Вершина-сток достигнута, найдена цепочка 134256, по которой можно передать поток, равный единице. При этом по прямым дугам поток увеличивается на единицу, по обратным - уменьшается. Суммарный поток в сети - 4 единицы.



Четвертая итерация. Вершине 1 присваиваем метку [1,@]. Первый шаг. Помечаем вершину 3 - [1,4]. Второй шаг. Рассматриваем помеченную, но не просмотренную вершину 3. Одна дуга - (3,4). Вершину 4 пометить не можем - пропускная способность дуги исчерпана. Помеченных вершин больше нет, и вершина-сток не достигнута. Увеличивающую поток цепочку построить не можем. Найден максимальный поток в сети. Можно заканчивать работу.

Итак, в чем суть “техники меток” Форда и Фалкерсона? Первое. На каждой итерации вершины сети могут находиться в одном из трех состояний: вершине присвоена метка, и она просмотрена; вершине присвоена метка, и она не просмотрена, то есть не все смежные с ней вершины обработаны; вершина не имеет метки. Второе. На каждой итерации мы выбираем помеченную, но не просмотренную вершину v и пытаемся найти вершину u, смежную с v, которую можно пометить. Помеченные вершины образуют множество вершин сети G, достижимые из вершины-источника. Если среди этих вершин окажется вершина-сток, то это означает успешный результат поиска цепочки, увеличивающей поток, при неизменности этого множества работа заканчивается - поток изменить нельзя.

Алгоритм. Входные данные. Описание сети G=(V,E) матрицей пропускных способностей С[1..N,1..N], где N - количество вершин. Вершина-источник s и вершина-сток t. Выходные данные. Поток, описываемый матрицей F[1..N,1..N]. Рабочие переменные. Структура данных для хранения меток - P[1..N,1..2]. Элемент P[i,1] - номер вершины, из которой можно передать поток, равный P[i,2], в вершину с номером i. Логическая переменная Lg, значение true - есть цепочка, увеличивающая поток, false - нет.

Основная логика.

begin

<ввод данных и инициализация переменных(Lg:=true)>;

while Lg do begin

FillChar(P,SizeOf(P),0);

<процедура расстановки меток(Mark), если вершину t не смогли пометить, то Lg:=false; результат работы - значение P (метки вершин) >;

if Lg then <процедура Stream(t) - изменение потока по дугам найденной цепочки от вершины-стока t до вершины-источника s; входные данные - массив P, результат - измененный массив F>;

end;

<вывод потока F>;

end.{конец обработки}

Уточним логику расстановки меток (нелучший вариант).

procedure Mark;

var M:set of 1..N;i,l:integer;

begin

M:=[1..N]; {непросмотренные вершины}

P[s,1]:=s;P[s,2]:=maxint;{присвоим метку вершине-источнику}

l:=s;

while (P[t,1]=0) and Lg do begin

for i:=1 to N do {поиск непомеченной вершины}

if (P[i,1]=0) and ((C[l,i]<>0) or (C[i,l]<>0)) then

if F[l,i]<C[l,i] then begin{дуга прямая?}

P[i,1]:=l; if P[l,2]<C[l,i]-F[l,i] then P[i,2]:=P[l,2]

else P[i,2]:=C[l,i]-F[l,i];

end

else if F[i,l]>0 then begin{дуга обратная?}

P[i,1]:=-l;

if P[l,2]<F[i,l] then P[i,2]:=P[l,2] else P[i,2]:=F[i,l];

end;

M:=M-[l];{вершина с номером l просмотрена}

l:=1;{находим помеченную и непросмотренную вершину}

repeat Inc(l) until (l>N) or ((P[l,1]<>0) and (l in M));

if l>N then Lg:=false;

end;

end;

Логика изменения потока F имеет вид:

procedure Stream(q:integer);

begin

{определяем тип дуги - прямая или обратная, знак минус у номера вершины - признак обратной дуги}

if P[q,1]>0 then F[P[q,1],q]:=F[P[q,1],q]+P[t,2]

else F[q,abs(P[q,1])]:=F[q,abs(P[q,1])]-P[t,2];

{если не вершина-источник, то переход к предыдущей вершине цепочки}

if abs(P[q,1])<>s then begin

q:=abs(P[q,1]);Stream(q);end;

end;

Итак, рассмотрение метода построения максимального потока в сети завершено.

4.3 Наибольшее паросочетание в двудольном графе

Паросочетанием в неориентированном графе G=(V,E) называется произвольное множество ребер ME, такое, что никакие два ребра из M не инцидентны одной вершине. Вершины в G, не принадлежащие ни одному ребру паросочетания, называют свободными. Граф G называют двудольным, если его множество вершин можно разбить на непересекающиеся множества - V=XY, XY=, причем каждое ребро eE имеет вид e=(x,y), где xX, yY. Двудольный граф будем обозначать G=(X,Y,E).

Задача нахождения наибольшего паросочетания в двудольном графе сводится к построению максимального потока в некоторой сети. Рассмотрим схему сведения. На рисунке показан исходный двудольный граф G. Построим сеть S(G) с источником s и стоком t следующим образом:

источник s соединим дугами с вершинами из множества X;

вершины из множества Y соединим дугами со стоком t;

направление на ребрах исходного графа будет от вершин из X к вершинам из Y;

пропускная способность всех дуг C[i,j]=1.

Найдем максимальный поток из s в t для построенной сети. Он существует[11]. Насыщенные дуги потока (они выделены “жирными” линиями на рисунке соответствуют ребрам наибольшего паросочетания исходного графа. Примечание. Найденное наибольшее паросочетание не единственное. Проверьте, это ли паросочетание получается при помощи алгоритма нахождения максимального потока. Найдите другие паросочетания. Рассмотрим другой метод построения наибольшего паросочетания в двудольном графе. Введем понятие чередующейся цепи из X в Y относительно данного паросочетания M. Произвольное множество дуг PE вида:

P={(x₀,y₁), (y₁,x₁), (x₁,y₂), ..., (y_k,x_k), (x_k,y_k+1)},

где k>0, все вершины различны, x₀ - свободная вершина в X, y_k+1 - свободная вершина в Y, и каждая вторая дуга принадлежит M, то есть

PM={(y₁,x₁), (y₂,x₂), ..., (y_k,x_k)}.

Теорема[3]. Паросочетание M в двудольном графе G наибольшее тогда и только тогда, когда в G не существует чередующейся цепи относительно M.

Теорема подсказывает реальный путь нахождения наибольшего паросочетания. Пусть найдено некоторое паросочетание в графе G, на рисунке оно выделено “жирными” линиями. Ищем чередующуюся цепь - ее дуги выделены линиями со стрелками. Она состоит из “тонких” дуг и “жирных”, причем начинается и заканчивается в свободных вершинах. Длина цепи нечетна. Делаем “тонкие” дуги “жирными” и наоборот. Паросочетание увеличено на единицу.

Общая логика

begin

<ввод и инициализация данных>;

<найти первое паросочетание>;

while <есть чередующаяся цепочка?> do <изменить паросочетание>;

<вывод результата>;

end.

Очередь за определением данных и последовательным уточнением логики. Граф описывается матрицей А[N,M], где N - количество вершин в множестве X, а M в Y. Паросочетание будем хранить в двух одномерных массивах XN и YM. Для рассмотренного примера XN=[0,1,2,4] и YM=[2,3,0,4,0]. Уточнение фрагмента “найти первое паросочетание” не требует разъяснений.

for i:=1 to N do begin {назначение переменных i, j, pp следует очевидно}

j:=1; pp:=true;

while (j<=M) and pp do begin

if (A[i,j]=1) and (YM[j]=0) then begin

XN[i]:=j;YM[j]:=i;

pp:=false;

end;

inc(j);

end;

end;

Как лучше хранить чередующуюся цепочку, учитывая требование изменения паросочетания и продумывая логику её построения? Естественно, массив, пусть это будет Chain:array[1..NMmax] of -NMmax.. NMmax, где NMmax - максимальное число вершин в графе, и его значение для рассмотренного примера равно [1, -4, 4, -2, 3, -3], то есть вершины из множества YM хранятся со знаком минус (вспомните метод построения максимального потока). Итак, поиск чередующейся цепочки.

function FindChain:boolean;

var p,yk,r:word;

begin

<инициализация данных, в частности yk:=1;>;

<нахождение свободной вершины в XN>;

if <вершина не найдена> then begin FindChain:=false;exit;end;

p:=<номер первой свободной вершины>;

Chain[yk]:=p;

repeat

r:=<очередная вершина из Chain>;

for <для всех вершин, связанных с r> do

if <вершина из XN>

then begin if <ребро “тонкое”> then

<включить ребро в цепочку>

end

else begin if <ребро “толстое”> then

<включить ребро в цепочку>

end;

Заключение

При изменении цвета у вершин с номерами, большими значения t, по методу правильной раскраски следует запоминать в рабочих переменных значения Gr и MaxC, так как при неудаче (раскраску не улучшим) их необходимо восстанавливать, и на этом закончить уточнение логики. При любом упорядочении вершин допустимые цвета j для вершины с номером i удовлетворяют условию ji . Это очевидно, так как вершине i предшествует i-1 вершина, и, следовательно, никакой цвет j>i не использовался. Итак, для вершины 1 допустимый цвет 1, для 2 - цвет 1 и 2 и так далее. С точки зрения скорости вычислений вершины следует помечать так, чтобы первые q вершин образовывали наибольшую клику графа G. Это приведет к тому, что каждая из этих вершин имеет один допустимый цвет и процесс возврата в алгоритме можно будет заканчивать при достижении вершины из этого множества.

Литература

Адельсон-Вельский Г.М., Диниц Е.А., Карзанов А.В. Потоковые алгоритмы.- М.:Наука,1975.

Берж К. Теория графов и ее применение. - М.: ИЛ, 1962.

Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. - М.: Наука, 1990.

Зыков А. А. Теория конечных графов.-Новосибирск:Наука; Сиб. отд-ние, 1969.

Йенсен П., Барнес Д. Потоковое программирование.-М.:Радио и связь,1984.

Касьянов В.Н., Сабельфельд В.К. Сборник заданий по практикуму на ЭВМ. - М.: Наука, 1986.

Кристофидес Н. Теория графов. Алгоритмический подход.-М.: Мир, 1978.

Кофман А. Введение в прикладную комбинаторику.-М.:Наука,1975.

Липский В. Комбинаторика для программистов.-М.:Мир, 1988.

Майника Э. Алгоритмы оптимизации на сетях и графах.-М.:Мир,1981.

Нечепуренко М.И., Попков В.К., Майнагашев С.М. и др. Алгоритмы и программы решения задач на графах и сетях.-Новосибирск: Наука; Сиб. отд-ние, 1990.

Окулов С.М.Конспекты занятий по информатике (алгоритмы на графах). Учебное пособие для студентов и учителей школ. - Киров, 1996.

Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация: Алгоритмы и сложность.-М.:Мир,1985.

Свами М., Тхуласираман К. Графы, сети и алгоритмы.- М.:Мир,1984.

Филипс Д., Гарсиа-Диас А. Методы анализа сетей. - М.: Мир, 1984.

Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях.-М.:Мир,1963.

Фрэнк Г., Фриш И. Сети, связь и потоки.-М.:Связь,1978.

Харари Ф. Теория графов.-М.:Мир,1973.

Ху Т. Целочисленное программирование и потоки в сетях.- М.:Мир,1974.