1629289598

3. Wierzchołki i krawędzie 3.1. Wierzchołki i krawędzie

Definicja 3.1. Niech T E R” będzie niepustym podzbiorem. Relatywnym wnętrzem zbioru T nazywamy podzbiór rint(T) = {p £ T | 3_e>o K{p,s) fi af(T) C T}.

Pojęcie relatywnego wnętrza jest praktyczniejsze przy badaniu wielościanów niż zwykłe wnętrze. Np. relatywnym wnętrzem odcinka w przestrzeni trójwymiarowej jest odcinek otwarty mimo, że cały odcinek jest brzegiem.

Stwierdzenie 3.1. Jeżeli T jest niepustym podzbiorem wypukłym w Rⁿ to rint(T) ^ 0. Dowód zostawiamy czytelnikowi.

Zajmijmy się kluczowym lematem przy opisie ścian wielościanu. Lemat 3.1. Niech p będzie punktem wielościanu

W = {x E Rⁿ \c*i • x ś: bi, 1 < i < t} = P| Hi,

gdzie Hi = {x £ RP \ ai • x < bi} S są pólprzestrzeniami. Dodatkowo zakładamy, że nierówności są tak ustawione by:

cti»p =bi dla 1 < i < s; ai • p < bi dla s < i < t;

Oznaczmy literą j liczbę n — rzA_p czyli wymiar przestrzeni rozwiązań układu jednorodnego opisanego macierzą A_p, ai

gdzie A_p =

, jest podmacierzą macierzy opisującej W złożoną z pierwszych s wierszy

a_s

macierzy opisującej W.

Wówczas:

1)    S = W fi fj Hf jest ścianą wymiaru j, zaś punkt p należy do jej relatywnego wnętrza.

2)    Punkt p jest środkiem pewnej j - wymiarowej kuli zawartej w W.

3)    Punkt p nie jest środkiem żadnej kuli j + 1 - wymiarowej zawartej w W.

Dowód. Niech V będzie zbiorem rozwiązań układu V = {x £ Rⁿ \ ai • x — bi, 1 < i < s} . Ponieważ p £ V i V jest zbiorem rozwiązań układu równań liniowych więc na mocy twierdzenia Kroneckera - Capelli’ego V jest przestrzenią afiniczną wymiaru n — rz(A_p) = j. Zauważmy dodatkowo V — fj Hi fi fj H~.

Niech Si— WndHi. Wówczas dla 1 < * < s Si są ścianami W zawierającymi punkt p zatem na mocy lematu 2.1 S jest ścianą wielościanu W. Ponadto 5 = WD fj Hf = fj Hi C\ fj Hf C

i^t

fj Hi fi fj Hf = V więc dim S < j.

i^s    i^s

Optymalizacja I © A.Strojnowski, Uniwersytet Warszawski, 2012.