Otoczka wypukła

Z Wikipedii, wolnej encyklopedii
(Przekierowano z Wypukła otoczka)
Skocz do: nawigacja, szukaj

Otoczka wypukła, powłoka wypukła a. uwypuklenie podzbioru przestrzeni liniowej – najmniejszy (w sensie inkluzji) zbiór wypukły zawierający ten podzbiór. Otoczkę wypukłą podzbioru A oznacza się zwykle jako \operatorname{conv} A.

Przekrój dowolnej ilości zbiorów wypukłych jest zbiorem wypukłym, więc najmniejszy zbiór wypukły zawierający A możemy zdefiniować jako przekrój wszystkich zbiorów wypukłych zawierających A. Zapisujemy to za pomocą formuły:

\operatorname{conv} A = \bigcap\{M: A\subset M \; \and\; M~~ \mbox{jest wypukły} \}.

Przykłady[edytuj | edytuj kod]

  • Powłoką wypukłą zbioru wypukłego jest ten sam zbiór.
  • Dla dowolnego skończonego zbioru punktów płaszczyzny {P1, P2, ..., Pn}, gdzie n>2\; powłoka wypukła tego zbioru jest wielokątem wypukłym (ewentualnie zdegenerowanym do odcinka) o wierzchołkach należących do zbioru \{P_1,P_2,...,P_n\}. Analogicznie w przestrzeni 3-wymiarowej powłoka wypukła skończonego zbioru punktów jest wielościanem wypukłym (ewentualnie zdegenerowanym do wielokąta lub odcinka).
  • Powłoką wypukłą zbioru trzech punktów niewspółliniowych (takich, które nie leżą na wspólnej prostej) jest trójkąt o wierzchołkach w tych punktach.
  • Otoczką wypukłą zbioru dwupunktowego {A, B} jest odcinek AB.
  • W n-wymiarowej przestrzeni euklidesowej E^n\; uwypukleniem zbioru punktów (1,0,0,\dots), (0,1,0,\dots),\dots, (0,\dots,1) jest zbiór punktów o współrzędnych dodatnich, których suma jest równa 1. Zbiór taki nazywamy sympleksem. W przestrzeni 2-wymiarowej jest to odcinek, 3-wymiarowej trójkąt równoboczny, 4-wymiarowej czworościan foremny.

Alternatywne przedstawienie[edytuj | edytuj kod]

Otoczkę wypukłą można scharakteryzować jako zbiór wszystkich wypukłych kombinacji liniowych elementów zbioru A:

\operatorname{conv} A = \left\{ x : \; x=\sum_{i=1}^{n}\beta_i a_i, \;\;\; \mbox{gdzie} \;\;\; a_i\in A, \;\; \beta_i \in\mathbb{R}_{+}\cup\{0\}, \;\sum_{i=1}^{n}\beta_i = 1, \; n\in\mathbb{N} \right\}

Dowód[edytuj | edytuj kod]

Oznaczmy operację tworzenia wszystkich wypukłych kombinacji liniowych elementów zbioru A przez f(A). Udowodnimy, że :(*)\qquad\operatorname{conv} A = f(A). Zauważmy, że A\subseteq f(A) (wystarczy wziąć w definicji n=1\, i \beta_1=1\,).

Wykażemy teraz, że f(A) jest zbiorem wypukłym: niech x,y\in f(A). Zatem, dla pewnych a_1,\ldots,a_n,b_1,\ldots,b_m \in A oraz dodatnich \alpha_1,\ldots,\alpha_n,\beta_1,\ldots,\beta_m mamy

x=\sum_{i=1}^{n}\alpha_i a_i, y=\sum_{i=1}^{m}\beta_i b_i oraz \alpha_1+\ldots+\alpha_n=1=\beta_1+\ldots+\beta_m.

Niech \alpha,\beta\geq 0 będą takie, że \alpha+\beta=1. Wówczas

1=\alpha\sum_{i=1}^{n}\alpha_i+\beta\sum_{i=1}^{m}\beta_i=\sum_{i=1}^{n}(\alpha\alpha_i)+\sum_{i=1}^{m}(\beta\beta_i)

i stąd

\alpha x+\beta y= \sum_{i=1}^{n}(\alpha\alpha_i) a_i+\sum_{i=1}^{m}(\beta\beta_i) b_i\in f(A).

Aby wykazać równość zbiorów postulowaną w (*) udowodnimy dwie inkluzje. Najpierw:

\operatorname{conv} A = \bigcap\{M : A \subset M \; \mbox{gdzie} \; M-\mbox{wypukły}\} \subset f(A)

Inkluzja zachodzi ponieważ w szczególności jednym ze zbiorów M zawierających zbiór A jest f(A) zatem cześć wspólna wszystkich zbiorów wypukłych zawierających A musi się zawierać w f(A). Zatem \operatorname{conv} A \subset f(A).

Teraz inkluzja w druga stronę:

Przypuśćmy, że M jest zbiorem wypukłym takim, że A\subseteq M. Teraz z obu stron inkluzji wykonujemy operację f otrzymując:

f(A) \subset f(M) = M

Ponieważ tak jest dla każdego zbioru M wiec także dla części wspólnej wszystkich zbiorów wypukłych M zawierających A zatem:

f(A) \subset\bigcap\{M:A\subset M, M-\mbox{wypukły} \} = \operatorname{conv} A

Stąd f(A) \subset \operatorname{conv}A, a więc f(A)=\operatorname{conv} A.

Zobacz też[edytuj | edytuj kod]