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

/'

i x )

=

-

і у

д

[ х )

,

Ѵ =

1 , 2 , . . .

, /г.

(10)

Л е м м а

1 7 ,2 .

Если множество /Ѵ<=-Х графа G=(X, U)

.удов ­

летворяющего условиям 1°

-

4 °,

является

^-выпуклым

отно­

сительно

некоторой

функции

,

то

оно является ju -выпук­

лым и относительно любой функции

, V = 1 , 2 , ..

. к .

Доказательство

очевидным

образом

следует

из

преобразова­

ния

(10) и леммы 1 6 .I .

Л е м м а

1 7 .3 .

Если множество R<=X графа

G -

(Xr U ) , удов­

летворяющего условиям 1°

-

4 °,

является

/г-выпуклым

отно­

сительно

некоторой

функцииjU у

,

то

оно является

и

Д -вы­

пуклым и относительно любой Функции

, V = ? , 2 , .■■,к .

Доказательство следует непосредственно из леммы 17.2

и пре­

образования

(1 0 ).

ЦТ е о р е

м а

1 7 .Г.

Если

граф G=(X/U) и функции

й'у ( и ) ,

Ьѵ(и) , р ѵ(х) f ^ ( х ) ,

Ѵ= / , 2 , . . . , А

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

условиям

І 0 - 5 ° ,

а д 1 с х

-

заданное

я -выпуклое

множество

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

од­

ной из

Функций

Я у

,

t,2

, ...,

к

,то

существует такая вер­

шина графа G

,

что

она является

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

17 .3

и

может

быть найдена

без

использования

значений

Функций ау (и/,

\ ( и ) ,

V =1,2,

. . . , к .

Д о к а з а т е л ь с т в о .

В

§ 1 5

показано,

что

если

граф

G удовлетворяет

условиям 1°

-

4°

и соотношению

( 7 ) ,то

за­

дача

1 7 .1

при

а ѵ (и) >ѵ = !1 2 г ..) к

обладает

таким решением,что

ее нахождение

не используют

числа а у (и), У = 1,2, . . . , к

.Очевидно,

замена условия

а у ( и )

>

0

на условие

а^(и ) » 0

может только

рас­

ширитъ множество решений задачи 17 . I .

Далее,

в

силу условий

І ° ~

4 °,

соотношения (Ѳ)

и лемм

17 .2,

17 .3

имеем на

основе

той

же

теоремы § 16, что задача 17.2 уже как

некоторая

задача

1 7 .I

об­

ладает таким же решением. Следовательно,

в силу леммы

1 7 .I

и

условий (7)

-

(9) получаем,

что

задача

17.3

обладает

искомым

решением.

т е о р е

м а

1 7 .2 .

Ери условиях

теоремы

1 7 .I

множества

всех решений Х ^ х " ,

Х0

,

соответственно,

задач

1 7 .1,

17.2

|и 17. 3 являются

1

-выпуклыми и

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

!каждой

из

Функций

д ѵ ,

,

V = 1 ,

2 , . . ■, к .

Доказательство непосредственно

вытекает из

оледствия § 16

и леммы

1 7 .2 .

и

1 7 .3 .

Заметим,

что для

нахождения решения

задачи

1 6 .3 .

может

быть использован

следующий

алгоритм.

1)

Проверяется выполнимость условий (7) -

( 9 ) .Бели

они вы­

полнены,

то приступим

к

следующему

шагу.

2)

Алгоритмом из

§ 16 находится решение задачи 17.3^ . как

некоторой задачи 17Д„. о удвоенным множеством условий.

___ З а м е ч а н и е

17 .2, Относительно проверки выполнения

условий

( 7) - ( 9)

см. замечание § 16.

З а м е ч а н и е

1 7 .3 . Важным графом

G~(X,U),

удовлетво -

ряющим

условиям 1° -

5 °,

является

дерево, причем

дли

него

условия І и -

4°

выполняются

тривиальным образом,

ввиду соотно­

шения

0 .

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

только для

дерева

усло­

вие 5° выполнено, то теоремы 17 . I .

и 17.2

остаются

справедли­

выми без

всяких ограничений

на функции а

у (и),

Ьѵ

(и),

р =

§

18 . Центр

тяжести дерева и алгоритм

его

нахождения

I .. Пусть задано дерево

Н = ( Х ,

V)

порядка N

. Каждой

вершине х

е X

припишем "вѳо" р ( х )

> 0

,

а каждому ребру

у «а V -

"длину" I ('. ')>О .

Так как

Н - дерево, то между любыми

вер­

шинами ~Х

я

~у

дерева

Н

существует

единственная

цепь

С(Х,у)~ѵк соединяющая. Длина

этой цепи принимается за расстояние

d ( x , y )

между

вершинами

х

и

у ,

т .ѳ . d

( х , у ) ~ ZZ

і (у)-

У

v e c f a y j

Рассмотрим функционал

f n

( * )

=

РСу)

<ІП( * ’У)>

(І)

y e *

где

Л -

натуральное

чиоло.

Н ,

З а д а ч а

. Требуетоя

найти

множеотво вершин дерева

которые минимизируют фуякдаонѳл ( I ) .

Пусть

Нк

и

Н'к

-

соответотвенно

подграфы графа Н, на

ко­

торые распадается

граф

Н

при удалении ребра

ѵк = (х к ,у к ),

при­

чем

ос е

Нк

f

а

у к

е. Н'к

.

Соответственно через р

(Нк )

и

Ап ( х к ,Ук )

= /„ ( x K ) - f n (yK) = L Z

p ( y ) d . n (xK , y )

+

УеНк

+ L

p (y )\d (x K,y K> d ( y K , у

) у

- Г . ,

P ( y ) d n( ук , у ) ~

- H

p ( y ) \ d ( x K,yK) + d ( x K , y ) ] n=

L

p ( y ) d n ( x K, y )

+

yeHK

L

J

y £HK

+ C

C

C ‘

p ( f ) d n-l( ^ . ! , , ) d l( y „ y ) - t g ,p (y)d " (!,K, y j -

-

С

C

C‘n p

( y j d n‘‘ (X

, a , ) d ‘ ( x K, u )

-

у ел

<-o

п-1

LZ

CLn p(y) d n~L‘fa>yK)dl(*K,y)-

d (XK 1 Ук)

LZ

n-t

V*HK 1=0

~ ]гн ѣ ъ

C"

p (y ) d n L /

( x *'y « } d l

(Ук,У)

И

Обозначим соответственноAJxr )=LZ ZZZ c ‘ p ( y ) d n 1

(xf

у

)d l(x

y)

An

Уе “к 1

-о

y*HKi- ”

0

)

*

( y K )

c ‘

p

( y ) d

n ' L 4 (-** , y K

d

L

( y K

, у

) .

Тогда

= L

ET

(*К’Ук )= ~ і ( ѵк ) [*п (Хк ) ~ Ап(Ук)

J

•

(2)

Будем говорить, что на простой цепи

с ( х , у )

дерева

И

■>

ребро

V,

предшествует

ребру

Ѵ2 ,

если

у

#

у£

,

и,

следуя

из

вершины

X

в

у

,

встречаем ребро

ѵ, , а

затем

ребро

Ѵ2 . Это от­

ношение порядка у

г~

ѵ2

будем

обозначать

следующим образом:

Н_

Л е м м а

1 8 .1 . Пусть на

простой

цепи

с f a ,у )

дерева

верно

соотношение

V, r=*

V?

.

Тогда

если

^ Ö,

*

то

* п (х2 ,уа) < 0 -

Д

о

к а з а т е л ь с т в

о .

Так

как

на

простой

цепи 1

С ( а

. у )

дерева

И ( x f , у ,) > { х 2

,у 2 j ,

то

любая

вершина

под­

графа Н'г

принадлежит и подграфу

н'іѣ

Вместе

с

тем

вершина

сг2

принадлежит подграфу / / ' , но не

принадлежит

подграфу

Н2 , Ыо

так

как

V у

6

X ,

"вес" р ( у ) ^

0

и

V ѵ & V

,

"длина" і(м)

> 0

,

следует,

что

Ап (х2)> Ап

(х,)

и

Ап (у2) < Ап (у,),

т.е. А „(х2) ~

~~Ап (уг ) > Ап ( x t )~

Ап (у ) ЪО

и тем самым из равенства

(2) сле­

дует

неравенство Дп (хг , у 2 )

<

О .

Лемма

доказана.

Л е м м а

1 8 .2 .

Множество вершин дерева

Н ,

минимизирую­

щих функционал

( I ) ,

состоит

не

более

чем из

двух

вершин.

Если существуют две вершины, минимизирующие функционал (I),

то они

смежные.

Д о к а з а т е л ь с т

в

о

.

Так

как

дерево //является

конечным,

то

существование

вершины,

минимизирующей

функционал

( I ) ,

очевидно. Предположим теперь,

что

существуют

две

несмежные

вершины х °

и

х°

дерева

Н , минимизирующие функционал

( I ) .

Рассмотрим простую цепь

с ( х ° , х ° )

с

первым ребром

=

а (я*

, У°)

И

последним

ребром

ѵ° = (у°2

, а:“)

,

ч . е . ( х ° , у ° )

і>

t>(у ° ,

х®

) .

того,

что

х °

и

х°

минимизируют

функционал

Но из

( I ) , следует,

что &п ( х ° , у ° ) $ 0

я Л п ( у ° ,

х"

) » ö .

Последнее

противоречит

лемме 1 8 .I .

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

наше предположение

не­

верно

и,

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

если

существуют

две

вершины

дерева

Н,

минимизирующие функционал ( I ) ,

то

они

смежные. Отсюда

следует,

что

на дереве

Н

множество

вершин,

минимизирующее

функционал

( I ) , состоит

не

более

чем из

двух

вершин.

Заметим, что две смежные вершины х° и

х®

будут

минимизи­

ровать функционал

(I)

тогда

и

только

тогда,

когда

для

соответ­

ствующих подграфов Н°

и

Н°2

имеет место равенство Ап ( х ° )

=

= Ап ( х ° )

•

Пусть О ( х ) -

множество

вершин,

смежных с

верши­

ной

X

. Справедлива

х °

Н

Т'ѳ

о

р

ѳ м а

. Вершина

дерева

минимизирует функ­

ционал

(I)

тогда

и

только

тогда,

когда

выполнено

условие

у е'о /х /)

( * п ( ХЦ

) ' Ап ( У * ^

(3)

Д о к а з а т е л ь с т

в

о

.

Достаточность. Пусть

х°к

-

вершина дерева

Н,

для

которой

выполняется условие (3) . Отсюда

имеем,

что

Ап [ х °

) —Ап (ук ) > 0

для

любого ук &0

( -х°к )

и

то-

гда

вариация Л а

(х°к

,

у к ) $

О

для

любого Ук *=О ( х® ) .

Но

тогда

на

основаншГ“леммы

І 8 .І

получим,

что f n ( х

° ) =

= х е # / п

(*") •■

Необходимость. Пусть

х®

-

вершина дерева

Н

,

для

которой

/ п ( х к ) = хйХ

• Тѳк

как

минимизирует функ­

ционал ( I ) ,

то

вариация

&п ( х ° ,

у к )$ О

для

любого Ук е О ( х ° ) ,

Т*е *У?еО(х°к)

(Ап (х к) -

Ап

(Ук ) ) > ° -

Ф х °

,

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

что

существует

вершина

z

для

которой

z'7eo(z')(An (z )''Ап (х к )) ^ 0 .

На основе доказанного

вы-

ше вершина* z

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

( I ) .

Но

тогда

из

леммы 18.2

следует,

что наше

предиоложение возможно лишь в од­

ной вершине

2 ,

смежной

о

и

чат® это

соответствует

случаю,

KOr«a г $ 0 (г )

( An ( z ) - An (Z K))

№

~ Ап К

) = 0 '

З а м е ч а н и е

1 8 .1 .

Когда п = / ,

имеем задачу

Штейне­

ра на дереве

Н . В этом

случае

вариация л ( х к , ук)=

— і м [ р ( ю - р ( м; ) ] .

Ксигда:

имеем задачу

о

на­

З а м е ч а н и е

1 8 .2 .

хождении центров тяжести

[15]

дерева

Н ■ -В атом случае

вариа­

ция функции / г

(х)

равна Az(xK,yky - Z t( v K)j

Fl p ( y ) d ( x K, у)

-t

ІуеИк

=-2L(vK)

\ ( ^ - ^ ( У к )

а)

увеличиваются "потенциалы!"’ всем висячим вершинам

дере­

ва

Н,

если среди них окажутся по> крайней мере

даё” вершины

о

одинаковыми полученными "потенциалами";

б)

если среди

висячих вершин: дерева

Н

окажется

только

одна вершина с максимальным получением "потенциалов",

то

этой

вершине

восстанавливается

предыдущий "потенщал".

Следуя работе

[5] , вводим понятие операций

А -усечения

де­

рева Н .

О п р е д е л е н и е

18.2:. Операцией А -усечения

дере­

ва

Н

называется удаление его висячих вершин вместе с инцидент­

ными им ребрами и с

одновременным’ црибавлевиемсоответственно

"весов"

и "потенциалов" удаляемых вершив плюс

полупроизведѳние

"весов"

висячих вершин на

"длину" инцидентных им ребер

к

"весу"

и

"потенциалу" соответствующих смежных им вершин, соблюдая сле­

дующие правила:

а)

операция А -усечения применяется

лишь к деревьям,имею­

щим более двух вершин;