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

d (x ' ,y ' )

= d ( x i

z') + d ( z /, y').

'

Это соотношение имеет место не только во

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

R n,

но

и в

RK (так как

x'ty'fz'e R K

и

Е.к = П пП RK

)

. Из

включения

x

l, y l<=.Ji'K ( C ) - d - c o n v K 'J?'K (N )

следует,

что z ' ^ d -

- convK (d ~ c o n v KdRK ( N ) ) - d - c o n y K ^K (С)<=-С ,

а

потому и г е С.

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

а/-сопѵп С<^С,

чем и доказана

с і -выпуклость

множества

С.

N ^ C ,

Так

как,

очевидно,

то из

доказанного

вытекает

включение

d ~ c o rtv n N<^C.

d~convn NczDt где D =

Аналогично доказывается

включение

(d - c o n V i % \ ( N ) ) .

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

d - c o n v n N с-СПЪ

.

Но

пересечение

СПТ)

как

раз

совпадает

о

множеством

( d - c o n v KdPK ( N ) ) ^ ( d - c o n v i ^ ' ( ( N ) ) t откуда

и вытекает

требуе­

мое

включение.

Д

о

к а

з

а т е л ь

с т

в о

теоремы 2 ,1 .

Пусть

- семейство d -выпуклых

множеств

в

каждые

h (R n} h

+1 из которых имеют непустое пересечение. В силу леммы 2 .2

лег­

ко

заметить,

что мнояеотво &К(МУ)

являетоя

Я'-выпуклым

в

про­

странстве

R K.

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

всех

множеств ^ [/с(Мх),^Л

предотавляет собой некоторое семейство o '-выпуклых

множеств

в

R * , каждые

/i(R n) + f

ив которых имеют непуотоѳ

пересечение.

А так как, по предположению, размерность

Хѳлли

h ( R nY

ранна

наибольшему ив

чиовл

h ( R K)

и

h ( R i ) ,

го

существует

точка

ае . R K, общая для

всех

множеств

(M^ ), А е А.

Аналогично,

существует

точка

i ^ R * ,

общая для всех

мно­

жеств

( М / ) , А е А ,

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

с

такую точку

про­

странства

Rn

, что

YRK ( c ) - a , ^

( с ) - Ь .

Так

как в оилу

леммы

2 . 2

М * = # к ( М л ) * # і ( М ь ) .

ТО

С&Мд

ДЛЯ

любого

AÉ Л .

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

что

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

h ( R n)

про-

отранства R n

не превосходит

наибольшее

из

чисел

h ( R K)

и

Л ( Rt ) ■

обратного

неравенства

к

I I

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

m a x { h ( R K),h ( R l ) \ ^

£ h ( R n)

проверяется

непосредственным образом.

В

самом

деле,

пусть

Яі

-

конечное

семейству

тУ-выпуклых

множеств

в R \ каж­

дые

h ( R n) + 1

из которых имеют непустое пересечение.

Множества

семейства М

являются

d -выпуклыми

и

в

про­

странстве

R n

(в силу леммы 2 .2 ) ,

и потому

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

се­

мейства М

имеют общую точку. Но это и означает,

что

размер­

ность

Хелли

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

R K

не

превосходит

h ( R n).

Аналогич­

ное

рассуждение

применимо

к подпространству

R * .

Следователь­

но,

теорема

2 .1

доказана.

Теперь сформулируем несколько предложений, легко

вытекаю­

щих кв теоремы 2 .1 .

шар Цп пространства R n

ЦТ е о р е

м а

2 .2 . Если единичный

(п

± 2

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

т

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

над шаром

некоторого

{ п - т )-мерного

подпростран-

Цства

R n ~m с R n (п >т ) }

то

верно

соотношение

/7 ( R n ) = h ( R n ~m ).

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

теоремы

2 .2

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

ме­

тодом

индукции

по числу

dim RK с

применением

теоремы 2 .1 .

Т е о р е м а

2 .3 . Пусть

F

- произвольное

семейство d -

выпуклых

множеств пространства Rn , содержащее

не

менее

ң (Rn)+2

элементов,

причем

либо

F

конечно,

либо же каж­

дое

множество лз F

замкнуто и хотя

бы одно

из

них

ком­

пактно. Тогда,

если

каждые

h ( R n)+ 1

из

множеств

семейст­

ва

F

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

пересечение,

существует

точка,

общая

для

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

F.

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

теоремы

2 .3 , осуществляется

обычной'техникой доказательства

теоремы

Хелли

(см..например,[4 ])

следующее

специальное

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

о нормой ЦхЦ-

С л е

д .о

т в и е

2 .2 . Для

=

| # |

размерность Хелли h (R? )

равна

единице, а

оледовательво, любая

система

компактных

d - выпуклых мно­

жеств обладает

непустым пересечением, как только любые два

множества этой

системы имеют непуотое пересечение.

3 . Рассмотрим

совокупность точек x 0 , x f ... ,xr

прост-

ранотва

Рп, обладающих свойством,

что векторы

х 0~х, , х й ~х2 ,

х 0 ~ х г

линейно независимые.

ХйіХ,,

О п р е д е л е н и е

2 . 5 . Выпуклая

оболочка точек

. . . , х г

называется

г-ыернын симплексом

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

Р п.

О п р е д е л е н и е

2 . 6 . Конечная

совокупность

Р

сим­

плексов

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

R n называется

симплициальным

комплексом,

если

выполнены условия:

Р

1 ° . Каждые два

симплекса

из

либо

не

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

либо

их пересечение является гранью (может быть,несобственной)

каж­

дого

из

них.

2 ° . Вместе

с каждым симплексом

множеству Р

принадлежат и

все

грани этого

симплекса.

Теоретико-множеотвенная

сумма

всех симплексов комплекса Р

ca

Р и обозначается через

Р

. Множество,

являющееся

телом

некоторого

комплекса

Р

,

называется полиэдром.

О п р е д е л е н и е

2 . 7 . Пусть

К

-

некоторый

полиэдр.

Разбиение

К

множества

к “ на конечное

число

попарно не

пере­

секающихся

множеств

7^ ,

I

= 1 , 2 , . . . , V

,

называется

клеточ­

ным комплексом, если

выполнены следующие

условия:

1°. Каждое из множеств

гомеоморфно

[з] открытому ша­

ру

некоторой

размерности

г

. Под шаром нулевой размерности бу­

дем

понимать

точку.. Множество

наэываетоя

клеткой, а

чиоло

2 ° .

Если

есть

г-мерная

клетка

комплекса

К

,

то

ее

граница

целиком расположена в

комплексе,

образованном

из

всех

клеток

размерности

4 г - / .

3 ° .

Существует такой

криволинейный

симплициальный і

комп-

леко Р

, полиэдр которого 7? совпадает с

К ,

что каждое

из

мно-

яе

гв

целиком соотавлѳнс из симплексов комплекоа

Р.

Пусть имеется некоторый клеточный комплекс

К

. г

-мерным

остовом комплекса

К

называется

комплекс,

состоящий

из

всех

клеток размерности

^ п

комплекоа

К

. Размерностью

клеточно­

го

комплекоа К называется наибольшая

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

входящих

в

комплеко клеток.

Полиэдр

Р*- R n называется

односвязным,

если он

является

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

любую проотую замкнутую кривую,

лежащую в

Р,

мож­

но

с помощью непрерывной деформации в

Р

стянуть

в точку.

3 .

Далее

докажем один факт,

существенно используемый в до­

1 °,

Множества

X , U

и

Ф

являются конечными.

2 ° .

Для любых

F^, /у , і ф /

выполнены

соотношения

Ь П Р у

=

{ х е *

J

[ и е і / .

3 ° .

Каждая клетка

F

Ф

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

собой некоторый че­

тов клетки

F состоит в

точности из

четырех одномерных

и че­

тырех нульмерных клеток. Имеет место

Т е о р е м а

2 . 4 .

Пусть

S 2 -

двухмерная сфера

евкли­

дова

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

Е3, а

( Х, 1/ , Ф)

- комплекс,

удов­

летворяющий

условиям І° -3 °

и полиэдр которого есть S 2,

тог­

да в X существует элемент

х , которому инцидентны в точно-

оти

три

элемента

множества

U.

Д о

к а

з а

т е л

ь с т в о

. Для удобства изложения

и с

ные,

одномерные

и двухмерные

клетки

комплекса

будем

называть

соответственно вершинами, ребрами и гранями комплекса.

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

т . е . предположим,

что

каждой верши­

не

х & Х

инцидентны более

трех

ребер. Следуя

[ і ] ,

образуй*

новый комплекс

(Х 'і/^ ф ') , вершинами которого являются все

вер­

шины комплекса

( Х, ( / , Ф) и

"середины" ребер комплекса (Х,и,Ф ).

Ребрами нового комплекса будут все "половинки" ребер

комплекса

(Х,и,Ф). Множество Ф' определяется

теми

же

элементами

множест­

ва Ф ; во только

каждая

грань из

Ф' будет

иметь

в

два

раза

больше ребер, чем соответствующая

ей грань из Ф.

Очевидно,jU'l-

- 2 I UI . Каждой вершине множества

X

,

по предположению,

инци­

дентны по крайней мере четыре различных ребра из множества U

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

)Xj4

.

Для

оценки

чиола граней

в множестве

Ф

рассмотрим

комп­

лекс

(Хн, U", Ф"),

множество

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

X" образовано

се ­

рединами

ребер

множества

U

и "центрами" граней множества

Ф.

Две

вершины множества X"

окаа^утся смежными,

если

соответствую-'