<<
>>

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

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

Существуют алгоритмы определения паросочетаний в графе, основанные на использовании потоков в сетях [12.1, 12.2], имитационного моделирования [12.3], генетического по­иска [12.4] и других эвристиках. В работе предлагается новый метод определения максимального паросочетания в графе, осно­ванный на идеях поисковой адаптации.

2. Одной из широко востребованных задач целочисленного программирования является задача о паросочетании максималь­ной мощности, рассматриваемой в комбинаторном направлении теории графов. Паросочетанием графа G = (X, U) называет под­множество таких ребер U'∈U, что любые два ребра uk, uι∈U'не имеют общих вершин, т. е. не смежны. Паросочетание макси­мальной мощности определяется как паросочетание, состоящее из максимального числа ребер [12.1].

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

требования к качеству и времени решения задачи нахождения максимального паросочетания.

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

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

Пусть дан граф G = (X, U) (рис. 12.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, двойственный граф Gdимеет вид, представленный на рис. 12.2.

Множество Xo вершин графа G = (X, U) называется внут­ренне устойчивым, если любые две вершины xi∈Xo и Xj∈Xo не являются смежными. Максимальное число вершин во внут­ренне устойчивом множестве графа G называется числом внут­ренней устойчивости и обозначается как α(G).Иногда число внутренней устойчивости называют также числом независимости графа G [12.7].

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

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

Построим для двойственного графа Gdматрицу смежности R (рис. 12.3). Переставим все столбцы и строки, помеченные эле­ментами некоторого внутренне устойчивого подмножества Pта­ким образом, чтобы они располагались рядом друг с другом, начиная с левой (верхней) стороны матрицы. Для нашего при­мера модифицированная матрица R имеет вид, представленный на рис. 12.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).

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

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

Рис. 12.3. Исходная матрица смежности

с построенной ^-областью

Таким образом, если в результате некоторой перестанов­ки строк и столбцов матрицы смежности образуется ^-область 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) [12.8].

Будем считать, что ^-область Pi(l, m)покрывает строки и столбцы матрицы смежности R с номерами от lдо (l + m — 1). Назовем две ^-области Pi(li, mi)и Pj(lj, mj∙) смежными друг к другу, если lj∙ = li+ mi.Пересечение двух смежных ^-областей равно 0. Если в результате перестановок столбцов и строк мат­рицы R образуется цепочка из sпоследовательно прилегающих друг к другу, т. е. смежных ^-областей, объединение которых покрывает все столбцы и строки матрицы R, то можно считать, что в графе G выделено sвнутренне-устойчивых подмножеств вершин и, следовательно, граф можно раскрасить в s цветов.

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

с минимальным числом ^-областей соответствует раскраске в минимальное число цветов.

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

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

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

12.2.

<< | >>
Источник: Курейчик В. В., Лебедев Б. К., Лебедев О. Б.. Поиско­вая адаптация: теория и практика. — M.: ФИЗМАТЛИТ,2006. — 272 с.. 2006

Еще по теме Основные положения:

  1. ОБЩИЕ ПОЛОЖЕНИЯ
  2. 3. Правовое положение образовательных учреждений
  3. 4. Правовое положение обучающихся в образовательных учреждениях.
  4. ОБЩИЕ ПОЛОЖЕНИЯ АДМИНИСТРАТИВНОГО ПРАВА
  5. 1. Понятие и правовое положение органа исполнительной власти
  6. 33. Правовое положения членов (бывших членов) семьи нанимателя жилого помещения.
  7. Гиссин Егор Маркович. ПРАВОВОЕ ПОЛОЖЕНИЕ БАНКА КАК ОСОБОГО УЧАСТНИКА НАЛОГОВЫХ ПРАВООТНОШЕНИЙ. Диссертация на соискание ученой степени кандидата юридических наук. Москва - 2003, 2003
  8. ОСНОВНОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ
  9. ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ
  10. 4.4 Основные выводы по главе 4
  11. 3.11 Основные выводы по главе 3
  12. ОСНОВНОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ
  13. ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ
  14. ОСНОВНЫЕ ВЫВОДЫ ПО ГЛАВЕ 2
  15. ОСНОВНЫЕ ВЫВОДЫ ПО ГЛАВЕ 1
  16. 1. Правовое регулирование в области безопасности. Основные понятия
  17. Основные обозначения и соотношения, используемые в работе
  18. ОСНОВНЫЕ ВЫВОДЫ ПО ГЛАВЕ 3
  19. ОСНОВНЫЕ ВЫВОДЫ ПО ГЛАВЕ 4