Файл: Солтан, П. С. Экстремальные задачи на графах и алгоритмы их решения.pdf

где

d. ( х , х . )

= ті п L - Ыи)

по всем цепям

с

графа

G у сое-

•

X

‘

ь

иес

x L .

вопрос,

нельзя

ли

подобрать

такой

Естественно

возникает

ЛИНЯЮЩИМ

И

пункт

х 0

для

размещения

производства,

что

оба функционала F(x),

Е (х)

достигают своего

минимума

при

х ~ х 0 .

В случае

про­

извольного

графа

G = (X,U)

решения

этой

задачи,

вообще

говоря,

не

существует;

мнолество

X

всех

точек

і е Х

,

в

которых

ми­

нимизируется

функционал

Г ( л ) ,

может

оказаться

непересекаго-

щимся с множеством

всех

точек,

минимизирующих Е (х).

В данном параграфе

укажем

условия,

накладываемые

на

граф

6

= (Х , Ü)

и функции

а ( и ),

b ( u ) , p ( x ) , q ( x ) ,

участвующие в

постановке задачи, при выполнении которых указанные задачи

за­

ведомо имеют Совместное решение, т .е .

XF л Х£

¥

<р

,

причем

нахождение решения осуществляется без использования

чисел

а (и)

в

Ь(и) .Более

того,

рассмотрим

совместную постановку к

задач

рассматриваемого

типа

на графе

и покажем,

при

каких условиях все

к задач имеют общее решение.

2 ,

Итак,

пусть на

конечном,

связном

и

неориентирован

графе

6 « * (X ,tf)

заданы: I) положительные функции

а ѵ

•

U

д,

V = f ,2.......... ж ,

( 3)

которые определяют

к

метрик

d , , d z , . . . , d K ,

введенных

соот­

ветственно

при

помощи

соотношения

(2)

§ I ;

2)

неотрицательные

функции

3)

фувкционали

=

Рѵ (Хс) с (у ( х , Х ; )

'

(5 >

4)

множество М<= X ,

являющееся

замкнутым

d -выпуклым

множест­

вом относительно

каждой

метрики d ^ ,

V = 1,2, ... , к .

Напомним,

что

множество

М с к

называется

d -выпуклым от­

носительно

на

X ,

если

из

соотношений

х г

х г

е М,

d )l(xf, x 2)=-

=

d i ( x f , x J ) ^ d / X j , x 2 )

следует

х э

^М-

Теперь может быть сформулирована

З а д а ч а

1 6 .2 . Найти

такую точку

х 0 е М ,

в

которой

функционалы

(5)

одновременно

достигают

минимума,

т.е.такую

точку'

х 0 е

М ,

что

выполнены

соотношения

т

к.

(6)

Под этой задачей

будем понимать

совместную

постановку

нескольких задач Штейнера на графе. Покажем, что если

граф

6

принадлежит классу К

, описанному в §

4, а функции

(3)

и

(4)

окажется,

что

нахождение искомой

точки

х д

может

быть

осущест­

влено при помощи алгоритма, не использующего

значений

функдар

«у (и).

Переходам к описанию интересующего нас класса

графов

6

*

приведем

условия, которые накладываются

на функции

(3) и (4 ) .

3 .

Будем

предполагать,

что рассматриваемый граф 6 =(х,и)

реализован

на

плоскости. Пусть

<р

-

множество всех

ограничен­

ных граней,

определяемых графом G

на

плоскости

(см .§

4 ) .

Па

граф

G

и функции

a v (u),pt (x)

наложим следующие

условия:

1 ° .

Для

любых

Ff ,F2 *

ЯР,

F1

* Fz

пересечение

Ff nFt

исчерпывается

одним из

случаев: Ft n

Fz

= 0 , F , n Fz

= и •

U .

2 ° .

Каждая грань

Fe ф

является

(вообще говоря,

криволи­

нейным) простым

четырехугольником,

3 ° . Если

вершина

х е /

не

принадлежит

неограниченной

об­

ласти

F0 , то X

инцидентна

более

чем трем ребрам графа G.

4 ° .

Если

и,, и2 6

U

-

противоположные стороны

некото­

рой грани

F e < P ,

то

а і

(и,)

*

а ѵ (uz ) ,

/,2,

Пусть Ut , U2 ,

,

Uп

-

классы эквивалентности

множе­

ства

U

(определение

4 . 1 . ) . Как

показано в § 5 (следствие 5 .1 .)

каждый класс

эквивалентности

V) ,

j

= /,2 ,

. . . , п

является

раз­

резом

в смысле

теории

графов

[ I ] ,

[10] ,

причем

граф

Gj

=

= ( X

, U \ U j

) состоит из двух компонент связности

[10]

: Gj

и

G / . Далее,

если

£'■=

( K ' , U ‘ )

-

подграф графа

G = ( X , U )

с

функцией

Р

, то через

Pv (G')

понимается

число

Щ , р

( х ) .

п

каждого фиксированного

/

хе*' ■У

5 °. Для

= 1, 2, . ■■, п

оправедлив.0

соотношение

(7)

Обозначим этот класс графов через

К ѵ,

V = 1 , 2

, . . . ,, к .

4 . В первую очередь заметим,

что

справедлива

Зак.665

73

Л е м м а

І 6 Д . Боли граф

6 = ( X , U ) ,

и функции

удовлетворяют условиям 1° -

4 °,

а М<^ X

являетоя d

-

выпуклым множеством относительно

некоторой

метрикиdy}го

И

являетоя

d -выпуклым и относительно любой другой метрики

d 9

, V =

/,2 ,

Доказательство проводится непосредственным образом при по­

мощи теоремы 6 .1 ,

о использованием

клаооов

эквивалентности .

. Ut , Ѵ ,

Un

и условия 4°.

Т е о р е

м а

1 6 .1 . Если граф

G =( X, U)

и

функции

Q ѵ (и), Pf (X),

V = f , 2 ,

л

удовлетворяют условиям 1 ° -

5 °,

а

Нс--X

-

заданное

d -выпуклое

множество

относи­

тельно некоторой метрики dy , то существует вершина

гра­

фа

G

,

которая

минимизирует функционалы

(5 ),

т .е .

сущест­

вует

решение

задачи. 1 6 .2 .

Д о к а з а т

е л ь с т

в

о .

В силу

леммы 1 6 .1

множество

М является

o'-выпуклым относительно

каждой метрики

V =

= І,2,

Пуоть

Yy -

множество

всех вершин графа

G

, для

ко­

торых функция

ру

принимает

положительные

значения. Тогда можем

рассматривать

к

задач

ХМУѴ, т .е .

к

задач Штейнера на

графе

6

класса

К\

Обозначим через

Хѵ

множество

всех решений

за­

дачи

XMYy,

V = / ,

2 ,

. . к,

причем в силу

теоремы

9.1

будем

по­

лагать,

что

ХУ= Х ,

а также

для

упрощения

записей

р ѵ = р)

, где

Ру

-

функция, определенная

на

X

при помощи функции

ру

и

оценки

£

(см.§

9 ) . Теперь

вернемся к рассмотрению отображения

<*-ѵ •' G

—-

I

=

(Ід , If ) ,

переводящего

граф

G

в граф

I ,

представляющий одномерный ос­

тов

клеточного

комплекса

І п с

R^

(см .§

7 ).

х і

G

Очевидно,

что

если

для

некоторой

вершины

графа

вер­

ны равенства

оС, ( x t ) - oi2

(xL) = ... =<х?(х('),то имеем: d.f(G)=dz (G) =

=..,= сИк (G) . В дальнейшем будем

полагать,

что

это

условие

выпол-

вяѳтся,

а следовательно,

можно пользоваться обозначением о(=ос,=

.= otg = . . .

= оСк .

Тогда в

пространстве

R"

можем рассматри­

вать

к

задач

R "

N ы. ( Yy ).

( Х у )

Теперь

заметим,

что

множество

представляет

собой

множество всех вершин некоторой -грани

Туѵ,

о « ? ^ 2

,

точки

которой

составляют

множество всех

решений задачи R" N

(Yv) ,

где ! t = d - c o n v <х.

(,М)с

R ^

.

Далее,

на

основе леммы из

§

3

множества

I**,

у = 1 , 2

, . . . , к

являются

-выпуклыми

множе­

ствами пространства ffn . Следовательно, для выполнения условия

Л І*ѵѵ Ф 0

,

достаточно

в

силу

следствия

2 .2 ,

чтобы имело

место

соотношение

ІІ*

П і

/‘

1

ф ,

V,

Ѵ'=

1 , 2

,

/с.

(8 >

Покажем,

что

условие

(8)

выполняется. Рассмотрим

условие

5° пункта 3 настоящего параграфа. Из соотношения (7) .очевидным

образом

следует,

что верно

равенство

sign (Pt (Gj ) - p f ( G j ) ) * sign (pt .(G j) - fy (G j)

для

каждых

V,V‘ =

f,2,

• ■■,

к.

Применяя

к

6j

и G*

отображе­

ние o t , получим соотношение:

sig n (p v ( ^ ( G -‘ ) ) - P V(OC(6 /) ) ) =

sign(pr (^ (G j)) -р ѵ. (k (G*))) .

Откуда

в силу

теоремы

3.1

и леммы § 3

немедленно

приходим

в

тому, что каждые две задачи

/ ?*/ V

f

)

и

А*”

N <<

( У ѵ>)

имеют

общее

решение, а

это

значит,

что условие

(8)

выполнено.

Отсюда

уже

легко

получить доказательство

теоремы І 6 . І .Дей­

ствительно,

пусть

z g~

некоторая вершина множества

І і = ф І * ѵ *

j*

0

.

Тогда

при

помощи отображения

находим

вершину

х 0 =>

=

( z 0)

графа

G.

В силу

теорем 7 .2 ,

9.1

и

1 0 .1 .

верши-'

на

х 0

является

решением каждой из

задач

ХМУѴ,

V“

f,2

, -

,к.

Таким образом,

теорема

1 6 .I

доказана.

В силу

следствий

свойств

а?-выпуклости и леммы

настоя­

щего параграфа

немедленно

получаем

С л е д с т в и е

1 6 .1 . Множество всех

решений рассмат­

риваемой задачи 16.2 для

графа

G,

удовлетворяющего

усло­

виям 1°

-

5 °,

является

o’ -выпуклым множеством

относи­

тельно

любой

метрит®

d y

,

у =

1 , 2

, ■. . , к .

5.

Приступим,

наконец,

к изложению основных шагов

алго­

ритма

решения

задачи

1 6 ,2 ,

сделав

предварительно

следующие

рассмотрения,

Обозначим,

как и раньше,

через

Хѵ

-

множество

решений

за­

дачи

ХМYy ,

Ѵ= 1

,2

,

Предположим,

что задача

16,2

имеет

решение, т . е . полагаем,

что Q Аѵ

д

0 .

Покажем,

каким

обра­

зом их можно

найти. Через

I

обозначим множество

о с ( Хѵ) ,

а

через

I

-

их объединение.

Пусть

q ( z ) , z . e l

означает число множеств

из

набора

I,

, І 2

, . . . І К ,

которым принадлежит

точка

z

. Рассмотрим

функцию

q.

<x(Yv ) - ~

1)

и

пусть

І 0

-

множество

вершин

грани

куба

пространства

R " t составляющих множество решений

задачи R * R ”l.

Справедлива

(10)

Т

е

о

р

е

м а

1 6 .2 .

Элементы множества

ос"

пред­

ставляют

собой

решения

задачи 1 6 .2 ,

Д

о

к

а

з а т е л ь с т в о

. Рассмотрим

задачу

R ” R 1' 1 .

Пусть

теперь

J

= { Э

-

множество

всех подмножеств

из

І,д л я

которых имеем

П

сг ( г ) >~2 ~ Z Z а ( z ) .

Тогда

в

силу

следствия 3 .2 , получаем, что множество решений за­

дачи

R* R ” 1

совпадает

с

множеством

Q

d-convJx ■С другой

стороны,

множество

П

d-cony'J,

совпадает

с

d-conv (<<.(/! X„))

=

=

Q

J /

? 0

. Далее#множество

Q І ѵ ѵ

представляет

собой

не­

которую грань

I *

куба I n<=R” ,

множество

вершин которой

суть

множество

Ір

образов

при "отображении

оС

множества

решений

/7 Х ѵ

* ф ,

представляющих

решения задачи

1 6 .2 . Таким образом,

теорема доказана. Теперь нахождение вершин грани

1*

может быть

осуществлено

в силу теоремы 3 .3 .

при помощи алгоритма

из

§

3.

Применяя к найденным вершинам отображение

об"'

найдем

решения

поставленной

задачи

1 6 .2 ,

Таким образом,

приходам к следующему

алгоритму

решения

задачи

1 6 .2 ,

Алгоритм

I)

Проверяется

выполнимость

условий

( 7 ) ,Если условия

(7)

выполнены для

каждого

V =

1,2, ....к, то

в силу

теоремы

1 6 .1

ре­

шение

задачи

1 6 .2

существует. Следовательно, можно приступить

К

очередному

шагу»

дачи

XMYV , V = 1 , 2 ч .

. , к .

к

_________

3)

Рассмотрим множество

Х ^ ~ 0

Х ѵ

и введем

функцию

Я*

D

подобно тому,

как

была введена

функция

q : ос ( Y v ) — D.

С помощью алгоритма из

§

8

находим решение задачи А*Л*Я.* .

В силу проведенных

рассмотрений,

решения этой задачи

и яв­

ляются решениями задачи

1

6 .2 .

З а м е ч а н и е

.

Уоловия

(7)

выражают,

очевидно,

что