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

При L = п -

1

опорная

плоскость

R n~1 .тела

к

в точке

ж е

еЬЫ К

называется

опорной

гиперплоскостью тела

К в точке ж и

обозначается

через

Гх . Выпуклое

тело

Rc= R n

называется

стро­

го выпуклым, если для любой точки

х е

bet К

пересечение

ГХ ПК

состоит

из единственной точки х.

2 .

Из

определения

І . І

d -выпуклого множества

легко

полу­

чаем

М — { М л

, л еУІ j

С л е д с т в и е

2 ,1 .

Если

-

се­

мейство

et -выпуклых множеств метрического

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

то

множество

М =

Q

М .

является

d -выпуклым.

О п р е д е л е н и е

2 .3 .

Пусть

N

-

некоторое

множе­

ство Iточек

метрического

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

X

, а

М — [ М ^ , \ е Л \

-

семейство

всех

d

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

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

,

содержа­

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

N

. Множество

П М

называется

*

сі -выпуклой

оболочкой

множества

N .

d

-выпуклую оболочку

множества NeX

будем

обозначать

через

d - соплг Л/.

Пусть

теперь

R n -

банахово

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

размерности

п

о

нормой

IIX II

и метрикой

d ( x , , х 2 )=Цхг - х г Ц. В таком случае в

R n можно рассматривать

как выпуклые

(в

обычном

смысле

слова),

так и

d -выпуклое множества. Очевидно,

что

d

-выпуклое мно­

жество

M e R n

является

выпуклым. Обратное,

вообще

говоря,

не­

верно.

Например,

на

плоскости

R 2 с

нормой

//.*://=/х '/

+ | х г | ,

единичный шар

£ 2

не

является

d

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

точки

(1 ,0 ) и

(0 ,1 )

принадлежат

множеству Z 2, а для

точки (1 ,1 )

вы­

полняется соотношение 2) из определения І . І .

d

-выпуклого мно­

жества,

но

она

не

принадлежит £ 2. d -выпуклая

оболочка множест­

ва И г является,

очевидно,параллелограммом,описанным

шару

(рис .2 ) .

d

-выпуклость

совпадает

с

вы­

пуклостью в том и только в том

слу­

чае, когда единичный шар в

R n явля­

ется строго

выпуклым. Например,

на

плоскости

R г

с

нормой

к X к

=

= \І(х,) 2- + ( х г)г ' с/-выпуклость

совпада­

ет с выпуклостью. Отметим еще,что мно­

жество

М <=

R n

тогда и

только

тог­

да является

d

-выпуклым,

когда

для

любых X

, х г

е

м

каждая

простая

ду­

Р и

о .

2

га , соединяющая

x f

и

xz

и

имеющая

длину II х г

-

х г

/I

,

содержится

в

М .

Зак.665

О п р е д е л е н и е

2 .4 .

Размерностью Хелли

h ( X)

мет­

рического

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

X

назовем

такое

минимальное

число

г

,

что

любое

конечное

семейство У

d

-выцуклых множеств из

X

о

c a r d

i f ъ-

г

+ 2

имеет непустое

пересечение, как только в нем

имеет

непустое пересечение

каждое

подсемейство

^

с

c arddE

—г + 1 .

Если

для

X

такого

числа

не

существует,

то

полагаем

h ( X ) -

.

h ( R n)

Ясно,

что размерность

Хелли

нормированного

прост­

ранства

R n

всегда

существует

и не

превооходит

d i m

Rn —

п.

Докажем теорему, дающую точную оценку

размѳрнооти

Хелли

h ( R n)

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

R n.

Формулировке

теоремы

предпошлем неко­

торые рассмотрения.

Пусть

R k

и

R t > k + Z = n

-

подпространства,прямая

сум­

ма

которых совпадает

с

R n . Пусть,

далее,

Т к

и

£

*

-

выпук­

лые множества соответственно в пространствах

R k и

/^ .содер ж а­

щие начало

координат

О

в

качестве

своей

внутренней

точки.

Обозначим

через

Т.п

вылукдую оболочку множеств

Ц к и

Л 1 ,т .ѳ .

ц " = сотг„ (

Л * U

£

1) .

_ ■

доказывается,

что

точка

х е

_ п

в том и

только

в

том

Легко

5_

случае является граничной точкой множества

Л ” когда

х

принад­

лежит

либо

множеству

И *

U

Л г ,

либо

отрезку

[ а

, Ь ]

, концы

которого

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

являются

граничными

точками

множеств

Л *

и

Z 2

относительно их несущих плоскостей. В случае

1 - 1

множество

Л"

называется

н а д с т р о й к о й

над множе­

ством

Л п

1 и обозначается

через Е Е "

1

(см. [ 3]

) .

Множест­

во

E t £

n~t = E ( E t

, £ " ~ t )

называется

t

-кратной

надстрой­

кой над

Е п~ь. Заметим,

что

п

-мерный октаэдр

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

R n

представляет собой (л - 1 )-кратную

надстройку Е п~1 Л 1

над от­

резком

Л

. Заметим

еще, что

выпуклая

болочка

множества

Л

с

czR t'

и

I -мерного

октаэдра

г * с

R 1

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

ообой

I

-

кратную надстройку

Е 1И п ~ 1

над

£ п~1.

Т е о р е м а

2 .1 . Пуоть X

,

Л

-

единичные

шарг

банаховых пространств

R n ,

R k , R i , причем

Rn=

и

!Ln = comri ( Z nu Л

) .

Тогда

размерность Хелли h(Rn) про­

странства Rn удовлетворяет

соотношению

h ( Rn) =

max. [ h ( R k)

, h { R i )} .

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

теоремы 2 .1

нам понадобятся

следующие

две

леммы.

Л е м м а

2 .1 . В условиях

теоремы

2 .1

для

любых трех

то­

чек .я,4і2, обладающих

тем свойством.что

[,г т у] | Rk,

[ y ,z ]

ЦR1,

справедливо

соотнесение

сі(ѵ ,г . ) = d ( 3 c , y )

+ d ( y f z ) .

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

о .

Положим

а =

у -

х

, Ъ = г

-

у .

Тогда

ае R k ,

b e R 1

и доказываемое соотношение

имеет вид

Ца + І Ц Ч а Ц + II Ъ Ц .

Рассмотрим

лучи

р г у.

,

г

,

исходящие

из

начала

координат

О

и проходящие через

точки

a t bf a + i

.

Точки

пересечения этих

лу­

чей с границей единичного шара

обозначим через а' , Ъ' , с ' .

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

a-t-Ь = kc' t

а - к ' а '

,

Ъ =

к" Ь'

,

где

числа

к, к ' , к" неотрицательные. При

этом

Ца'Ц

-

II б'Ц= |) с'Ц

=

7

я

поэтому

1а II =

к

' Ы І = к п

,

На у-ЫІ

- к

;

Заметим,

что так

как

а 1

Ъ'

яв­

ляются граничными точками выпуклых мно­

жеств Е к , Z

,

то весь

отрезок [а',Ъ']

расположен

на границе

единичного

шара

Z . А так как отрезок

[ а ',

6']

и

луч

г

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

именно

в

плоскости,

содержащей

точки

О, а , Ъ ) f го

точка пересечения

отрезка

[of\ Ь' }

и

луча

г

существует

и

явля­

ется граничной

точкой

тела

£

. Это

оз­

начает,

что

отрезок

\ а'

,

&]

и

луч

г

пересекаются в

точке

с'

(р и с .З ).

—с

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

a f = j ~a

/

~ дг Ъ

гак

что

«г

+ bt

(р и с .З ). Тогда

имеем

b'=llall =

llka7\l = k l l a t i l = k - $ r

=

к ~ г

~

г

к "= U II =ЦккгЦ= к II Ь7Ц = к

= к

с

-

а

Ъ'

6 ' - а '

и потому

к ’+ к" =

к

,

а

это

и

есть

требуемое

соотношение

II а ((+ II Ь Ц= IIсг + ЫІ . Лемма

2 .1

доказана.

Теперь

обозначим

через

згк

проекцию пространства

R n на под­

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

параллельно подпространству

R l , a

через

Я~г

проекцию пространства

R n

ва

R 1

параллельно

R k . Далее

через

d - conirn , d-conirk ; d - c o n v ^

обозначим

операцию образования

d -выпуклой оболочки соответственно в пространствах

R n,

R k, R l-

Л е м м а

2 .

2 , Для любого множества

N банахова

прост­

ранства

R n ,

удовлетворяющего условиям теоремы

2 . 1 ,спра­

ведливо соотношение

d-contrn Л/ = (d -

con ѵк

(л/))x ( d - con irt

( N) ) ,

где

прямое произведение соответствует прямому

разложению

Rn =

R k

®

R l .

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

. Без ограничения общности мож­

но

очитать

(применив,

если

нужно, параллельный пѳрѳноо),

что

О

е N .

Пусть

x e N

и у

е

( N ) . Тогда y e R k ,

х - у

е R i

и потому

в

силу

леммы 2.1

d ( o , х ) = d ( о , у ) + d ( у , ж) .

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

ye

d - сопггп А/ .

Этим доказано включение

(N)<=

«= d - con гг N . Но

тогда

п

Аналогичным образом

подучаем включение

d - con гг St (а/)

«=

d

-

-COntrn N.

Пусть теперь z e ( d - сопітк ТА (л/))х(d - c o n I^ ^ CA/)),

т .ѳ .

z = a + b ,

где area''- conirk

Ы) ,

Ьtd-contrj-^N). Тогда,

в

си­

ду леммы 2 .1 ,

имеем

d ( a , 6 ) = d ( a , z ) t c U z ^ b )

и потому z w d -

con ггп ( of-con

isk Jtk (.A/)Udcon v~t

( N ) )

c

c d - c o n irn (d - c o n

er

N) =

d -

c o n q N

.

Этим, очевидно,

дока­

зано включение

d - c o n

ггп M => {d-con irk 3tk {N ))x(d - c on dl fit

(N)) .

Для доказательства обратного включения рассмотрим

множест­

во С =Sffk \ d -

сопггк Жк ( а/ ) ) .

Оно предотавляет собой

цилиндр,

образованный

всеми плоскостями,

параллельными

R { и

проходящи­

ми через

точки множества d - c o n ігк ^ ( п ) .

Покажем,

что

этот

ци­

линдр является

d

-выпуклым

множеством

в

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

R " ,

Пусть z e d - c o n ѵп

С

. Тогда,

очевидно,

z ' = &k (z)e d - c o n

гп/г с .

Иначе говоря,

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

точки

х , у

е С ,

что

d ( x

,

у )

=

~ d ( x , z ’)

у- d

( z ' , y )

■ Положим

x ' =

%^ (х),у'=%к(у).Ъ

силу

лем­

мы' 2.1

d(x,z') = d i x . x ' j + d ^ z ' ) ,

d u ' , y ) = d { z ' , y ' ) + d ( y ' , у )

■