Информационный сайт

 

Реклама
bulletinsite.net -> Книги на сайте -> Программисту -> Сигал И.Х. -> "Введение в прикладное дискретное программирование " -> 24

Введение в прикладное дискретное программирование - Сигал И.Х.

Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование — М.: ФИЗМАТЛИТ, 2003. — 240 c.
ISBN 5-9221-0377-6
Скачать (прямая ссылка): vvedenievprikladnoeprogrammirovanie2003.djvu
Предыдущая << 1 .. 18 19 20 21 22 23 < 24 > 25 26 27 28 29 30 .. 84 >> Следующая


T-1AiT = A2. (2.3.11)

Условие (2.3.11) перепишем в виде

AiT = TA2, (2.3.12)

что равносильно следующим условиям:

aik tkj — tik'

г(2) kj ’

hi = 1,2,...,ш.

(2.3.13)

fc=i

fc=i

Задача о поиске матрицы T сводится к минимизации функции

га га / га

i=l j=l Xfe=I

при условиях

= 1’ j = 1,2, ...,то,

г=1

га

Ytij = 1, г = 1,2, ...,то,

J = I

Є {0,1}, г,і = 1,2, ...,ш.

(2.3.14)

(2.3.15)

(2.3.16)

(2.3.17)

Если графы Gi и G2 изоморфны, то минимальное значение функции Fi(T) равно нулю и матрица T определяется через подстановку t (2.3.10) следующим образом:

tij. =1, і = I, 2,..., m, а все оставшиеся ее элементы равны нулю. В нашем примере матрица T имеет вид

1 2 3 4 5
1 0 0 0 0 1
2 0 1 0 0 0
3 0 0 0 1 0
4 1 0 0 0 0
5 0 0 1 0 0

Рассмотрим некоторые другие целевые функции в задаче об изоморфизме графов:

т т

вд = ЕЕ

i=lJ=I к=1

га

Y (°?*** - **а<$)

(2.3.18)

5*
68 Разд. I. Предмет и модели дискретного программирования

Эта целевая функция, в отличие от Fi(T)1 не является дифференцируемой.

Обратим внимание на то, что

Нулевые минимальные значения нелинейных целевых функций Fi(T)1 F2(T) и F^(T) достигаются для изоморфных графов и только для них.

Как известно, матрицы А\ и A2, удовлетворяющие условию (2.3.11), называются подобными *). Разработаны алгебраические методы, позволяющие решить вопрос о подобии матриц А\ ж A2. Предоставляется целесообразной попытка соединения алгебраических методов и описанных здесь подходов.

2.3.3. Задачи о раскрасках графов.

Задача о вершинной раскраске. Каждой вершине і Є I графа поставим В СООТВеТСТВИе ЦВЄТ 0{.

Определение. Вершинная раскраска графа называется правильной, если для любого ребра (i,j) Є U имеем

Правильно раскрашенный граф с некоторой фиксированной раскраской a = (cFi 1 G2l... 1 (Jm) обозначим G(I, С/; сг); E — множество всех правильных раскрасок. Каждой правильной раскраске поставим в соответствие число цветов 7(G(/, U1G)).

Определение. Хроматическим числом графа G называется

поэтому

к=1

TYl

1,

О,

-1.

Целевую функцию Fs(T) рассмотрим в виде

TYl

F3(T) = max ^ {°Чк^з ~ t^k]) min- (2.3.19)

^•,3

к=1

Очевидно, что

(Ti Ф •

70 = (G (I1 f/; (T0)) = min 7 (G (I1 E/; а)) .

<т?2]

*)Мишина А. П., Проскуряков И. В. Высшая алгебра. — М.: Наука, 1962. (Серия «Справочная математическая библиотека».)
Гл. 2. Модели дискретного программирования

69

Хроматическому числу 70 соответствует правильная раскраска сто. Немецкий математик Мёбиус (1790-1868) высказал в 1840 г. предположение, что для плоских графов 70 < 4; это предположение получило название гипотезы о четырех красках. Для плоских графов доказано, что 7о < 5 (см., например, [9]), для деревьев 70 = 2. Гипотеза

о четырех красках в течение длительного времени оставалась недоказанной, она стала одной из самых знаменитых нерешенных задач математики. В 1976 г. эту гипотезу удалось доказать с применением ЭВМ. Было показано, что если 70 < 4 для некоторых специальных классов графов, то это условие выполняется всегда. Если же хотя бы для одного графа из этих специальных классов 70 > 4, то гипотеза неверна. Все эти специальные классы графов были проанализированы К. Аппелем и В. Хайкеном на ЭВМ, для этого потребовалось около 2000 ч машинного времени одной из наиболее мощных ЭВМ того времени; гипотеза была подтверждена*).

Сформулируем задачу о вершинной раскраске на языке целочисленного линейного программирования.

Пусть Xj — номер цвета, в который окрашена вершина j (j = 1,2, ...,m; I < Xj < m), такая раскраска является правильной, если, например, Xj = j. Если (г, j) Є U1 то Х{ ф Xj1 что можно записать в одном из следующих видов:

(Xi - Xjf > 1

или

\Хг ~Xj \ > 1.

Целевая функция имеет вид

max Xj —> min.

I <j<m

Итак, модель описывается соотношениями

max Xj —>• min, (2.3.20)

I <j<m

(Xi-Xj)2> I, (i,j) Є U, (2.3.21)

I < Xj < т. (2.3.22)

Рассмотрим другую модель. Введем булевы переменные

{1, если вершина j имеет цвет г,

0 в других случаях.

Каждая вершина имеет один цвет, что можно записать в виде

т

YtXij = I, І = 1,2, ...,т.

*)Емеличев В. А., Мельников А. И., Сарванов В. ИТышкевич Р. И. Лекции по теории графов. — М.: Наука, 1990. — С. 263, 264.
70 Разд. I. Предмет и модели дискретного программирования

Если (р, q) Є Uj то

Xip jTXiq < 1, і =

Если цвет с номером і входит в раскраску, то у І = sign Xij j = I, если цвет % в раскраску не входит, то у і = 0. Поэтому модель имеет

ВИД ш

^Уі-Япіп, (2.3.23)

т

YxIj = J = 1)2,...,ш, (2.3.24)

1=1

Xip + Xiq <1, (р, q) Є U, і = 1,2,..., то. (2.3.25)

В самом деле, если ни одна из двух смежных вершин р и q не окрашена в цвет г, то

Xip Xiq = 0,

если одна из них (например, р) окрашена в цвет г, то вторая из них q окрашена в другой цвет, поэтому

Xip ~\~ Xiq — 1.

Итак, модель описывается соотношениями (2.3.23)-(2.3.25). Задача о реберной раскраске.
Предыдущая << 1 .. 18 19 20 21 22 23 < 24 > 25 26 27 28 29 30 .. 84 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100