Введение, Основные положения - Эволюционные процедуры решения комбинаторных задач на графах

Среди набора комбинаторно-логических задач на графах важное место занимает проблема определения паросочетаний, раскраски графа, выделения в графе внутренне устойчивого множеств вершин и клик. Эвристические алгоритмы решения данных задач применяются при проектировании инженерных сетей, коммуникаций, построения систем поддержки принятия решений в неопределенных условиях, проектировании СБИС и т. п. Задачи такого типа относятся к переборным задачам с экспоненциальной временной сложностью. В этой связи разрабатывают различные эвристики для построения алгоритмов с полиномиальной временной сложностью. Существуют алгоритмы определения паросочетаний в графе, основанные на использовании потоков в сетях [Андерсон, 2003], [Кормен и др., 2000], имитационного моделирования [Свами и др., 1984], генетического поиска [Курейчик и др., 2003] И других эвристиках. В работе предлагается новый метод определения максимального паросочетания в графе, основанный на идеях поисковой адаптации.

Основные положения

Одной из широко востребованных задач целочисленного программирования является задача о паросочетании максимальной мощности, рассматриваемой в комбинаторном направлении теории графов. Паросочетанием графа G=(X, U) называет подмножество таких ребер U'U, что любые два ребра UK,uL U 'не имеют общих вершин, т. е. не смежны. Паросочетание максимальной мощности определяется как паросочетание, состоящее из максимального числа ребер [Андерсон, 2003].

Процедура нахождения максимального паросочетания в графе входит в состав большого числа алгоритмов, решающих различные задачи, [Макконнел, 2004]. Часто эта процедура используется в итерационных структурах. Это предъявляет повышенные требования к качеству и времени решения задачи нахождения максимального паросочетания.

Существующее в настоящее время большее количество алгоритмов нахождения максимального паросочетания обеспечивают приемлемые результаты при решении задач малой и средней сложности. Возникшие потребности в решении задач большой и очень большой размерности является побудительным мотивом исследований и разработок новых эффективных алгоритмов. Анализ литературы показывает, что наиболее успешными в этих условиях являются методы, основанные на моделировании эволюционных процессов [Лебедев и др., 2005].

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

Пусть дан граф G=(X, U) (рис. 1). U={uI| i=1,2,...,9}. Паросочетание такого графа определяется как множество ребер, не имеющих общих вершин. Например: паросочетание P={u1, u4, u7, u9}. Построим граф GD=(U, V) - двойственный для графа G. Вершины графа GD - соответствуют ребрам графа G. Пара вершин (uI, uJ) в графе GD связаны ребром в том и только в том случае, если в графе G пара ребер (uI, uJ) смежны, т. е. инциденты одной вершине.

пример графа

Рис. 1. Пример графа

Для примера, представленного на рис. 1, двойственный граф GD имеет вид, представленный на рис. 2.

двойственный граф g

Рис. 2. Двойственный граф GD

Множество X0 вершин графа G=(X, U) называется внутренне устойчивым, если любые две вершины XI X0 и XJ X0 не являются смежными. Максимальное число вершин во внутренне устойчивом множестве графа G называется числом внутренней устойчивости и обозначается как Б(G). Иногда число внутренней устойчивости называют также числом независимости графа G.

Подмножество вершин P={u1, u4, u7, u9} Является внутренне-устойчивым, т. к. любые две вершины подмножества P не смежны. Таким образом, паросочетанию графа G соответствует внутренне-устойчивое подмножество двойственного графа GD.

Максимальному по мощности паросочетанию графа G соответствует предельное внутренне-устойчивое подмножество (содержащее наибольшее число вершин) двойственного графа GD.

Построим для двойственного графа GD матрицу смежности R (Рис. 3). Переставим все столбцы и строки помеченные элементами некоторого внутренне-устойчивого подмножества P таким образом, чтобы они располагались рядом друг с другом начиная с левой (верхней) стороны матрицы. Для нашего примера модифицированная матрица R имеет вид, представленный на рис. 4. Анализ состояния матрицы смежности показывает что если столбцы матрицы с номерами от L до L+m помечены элементами, образующими внутренне-устойчивое подмножество, то симметрично относительно главной диагонали матрицы R на пересечении столбцов и строк матрицы с номерами от L до (L+m -1) формируется область PI Квадратной формы размером M*m, элементы которой имеют нулевое значение. Назовем такую область - областью. В приведенном примере - область - это область, образованная при пересечении 1-4 столбца с 1-4 строкой. Столбцы и строки помечены элементами 1,4,7,9. PI=PI(l, m), где L - номер первого столбца (и первой строки), с которого начинается - область PI, M - число столбцов и строк, на пересечении которых образована - область PI. Для нашего примера P1=P1(1,4).

Матрица смежность граф комбинаторный

исходная матрица смежности рис.4. матрица смежности с построенной -областью

Рис. 3. Исходная матрица смежности Рис.4. Матрица смежности с построенной - областью

Таким образом, если в результате некоторой перестановки строк и столбцов матрицы смежности образуется - область PI(l, m), то это значит, что элементы, которыми помечены столбцы и строки с номерами от L до (l+m-1), образуют внутренне-устойчивое подмножество UI. И если операция производилась на графе GD, двойственном к G, то подмножеству UI Соответствует паросочетание в G. Отсюда схема нахождения в графе G паросочетания максимальной мощности выглядит так.

Строится граф GD , двойственный к графу G. Путем перестановок строк и столбцов матрицы смежности R графа GD формируется - область PI(l, m) с максимально возможным значением параметра M. Множество элементов UI, которыми в матрице смежности R помечены столбцы с номерами от L до (l+m-1), будут составлять максимальное паросочетание в графе G.

Раскраской графа называется такое приписывание цветов его вершинам, что никакие две смежные вершины не получают одинакового цвета. Минимальное число цветов, в которое можно раскрасить граф G, называется хроматическим числом и обозначается ч(G) [Курейчик, 1990].

Будем считать, что - область PI(l, m) покрывает строки и столбцы матрицы смежности R с номерами от L до (l+m-1). Назовем две - области PI(lI,mI) и PJ(lJ,mJ) смежными друг к другу, если LJ=lI+mI. Пересечение двух смежных - областей равно. Если в результате перестановок столбцов и строк матрицы R образуется цепочка из S последовательно прилегающих друг к другу, то есть смежных - областей, объединение которых покрывает все столбцы и строки матрицы R, то можно считать, что в графе G выделено S внутренне-устойчивых подмножеств вершин и, следовательно, граф можно раскрасить в S цветов.

Таким образом задача раскраски графа сводится к задаче формирования в матрице смежности графа цепочки - областей с вышеперечисленными свойствами. Формирование цепочки с минимальным числом - областей соответствует раскраске в минимальное число цветов.

На рис. 4 в матрице R сформирована цепочка из 3-х областей. Следовательно, граф раскрашивается в 3 цвета. {u1, u4, u7, u9} - 1 цвет, {u5, u2, u8} - 2 цвет, {u3, u6} - 3 цвет.

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

Таким образом в основе процедур построения максимального паросочетания, раскраски графа, выделения в графе внутренне устойчивого множеств вершин и клик лежит одна общая процедура формирования З-областей в матрице смежности графа.

Похожие статьи




Введение, Основные положения - Эволюционные процедуры решения комбинаторных задач на графах

Предыдущая | Следующая