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

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 31.10.2024

Просмотров: 38

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

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

 

 

 

 

/'

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°

-

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

( 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 , . . ■, к .

 

 

 

 

 

 

.xiK.t-U;

81


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

вытекает из

 

оледствия § 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 °,

является

 

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

дли

него

условия І и -

выполняются

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

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

шения

0 .

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

только для

дерева

усло­

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

и 17.2

остаются

справедли­

выми без

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

на функции а

у (и),

 

Ьѵ

(и),

р =

=(конечно, за исключением остальных, фигурирующих в фор­

мулировках задач І7.І_,. 1 7 ,2 . и 1 7 . 3 . ) .

 

 

 

§

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

а

у к

е. Н'к

.

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

(Нк )

и

будем обозначать суммы "весов" вершин этих подграфов. Рассмотрим вариацию Л п ( х к , у к ) функции f n ( х ) при пе­

реходе от вершины Х к к вершине у к . Имеем:

82


 

 

Ап ( х к ,Ук )

= /„ ( 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 )

<

О .

 

Лемма

 

доказана.

 

 

 

 

 

83


 

Л е м м а

 

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 ) .

Но

тогда

из

84


леммы 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)

\ ( ^ - ^ ( У к )

 

Дель следующего пункта - изложить алгоритм нахождения цент­ ров тяжести дерева Н .

2 . Вершины дерева И будут характеризоваться еще и "по­ тенциалами" А (■%) , первоначально® значение которых равно нулю.

О п р е д е л е н и е 1 8 .1«, Операцией присвоения висячим вершинам дерева И новых потенциалов называется увеличевие "потенциалов" висячих вершин соответственно на величину,равную по­ лупроизведению "весов" висячих вершив: на "длину" инцидентных им ребер с соблюдением следующих правил:

 

а)

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

дере­

ва

Н,

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

даё” вершины

о

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

 

 

 

 

 

 

б)

если среди

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

Н

окажется

только

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

то

этой

вершине

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

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

 

 

 

 

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

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

А -усечения

де­

рева Н .

 

 

 

 

 

 

 

 

О п р е д е л е н и е

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

дере­

ва

Н

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

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

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

"весов"

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

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

"весов"

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

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

к

"весу"

и

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

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

 

 

 

 

 

 

 

 

а)

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

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

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

 

 

 

 

 

 

85