Polytop

Polytop (ze starořeckého πολύς [polýs] – mnoho, a τόπος [tópos] – místo) je v geometrii zobecněním mnohoúhelníku nebo mnohostěnu v libovolněrozměrném prostoru. Je-li třeba zdůrazit počet rozměrů d, mluví se o d-polytopu.

Definice

0-polytop je tvořen jediným bodem (vrchol); 1-polytop se skládá ze dvou vrcholů spojených hranou (úsečka); 2-polytop se skládá z několika 1-polytopů, vždy po dvou spojených ve společném vrcholu, takže vznikne cyklus, který tvoří mnohoúhelník; 3-polytop se skládá z několika 2-polytopů (mnohoúhelníků), z nichž některé dvojice jsou spojeny hranou, a dohromady tvoří mnohostěn; atd.

Obecně je ${\displaystyle (d\!+\!1)}$-polytop tvořen několika ${\displaystyle d}$-polytopy, které mají po dvou společné ${\displaystyle (d\!\!-\!\!1)}$-podpolytopy (jako mají dvě hrany společný vrchol nebo dvě plochy společnou hranu). Všechny ${\displaystyle (d\!\!-\!\!1)}$-podpolytopy musí být průnikem dvou ${\displaystyle d}$-polytopů, které spolu sousedí. Dále musí mezi dvěma ${\displaystyle d}$-polytopy existovat řetěz ${\displaystyle d}$-polytopů, takže každé dva členy jsou spojeny stejným způsobem jedním ${\displaystyle (d\!\!-\!\!1)}$-podpolytopem – například několik nesousedících mnohoúhelníků netvoří 3-polytop.

Terminologie

V určitých dimenzích dostaly polytopy zvláštní názvy, které jsou uvedeny v následující tabulce:

U polytopů dimenze d se používají následující názvy:

Dimenze polytopu ${\displaystyle P}$ je definována jako rozměr jeho afinního obalu, tedy nejmenší afinní prostor, který obsahuje polytop ${\displaystyle P}$. Krychle je tedy trojrozměrná, protože nejmenší prostor, který ji obsahuje, je trojrozměrný. Polytop plné dimenze je polytop, které neleží ve vlastním podprostoru, tedy jehož dimenze je stejná jako prostor, v němž je umístěn.

Konvexní polytop

V matematice a v lineárním programování mají zvláštní význam konvexní polytopy, tedy takové polytopy, u nichž úsečka spojující libovolné dva body leží celá uvnitř polytopu. Jde o zobecnění pojmu konvexního mnohostěnu.

Konvexní polyedr

Konvexní polyedr je průnik konečně mnoha podprostorů prostoru ${\displaystyle \mathbb {R} ^{d}}$. Polyedr ${\displaystyle P\subset \mathbb {R} ^{d}}$ je tedy každá množina tvaru

${\displaystyle P=\{x\in \mathbb {R} ^{d}|Ax\leq b\},}$

kde ${\displaystyle A}$ je nějaká matice typu ${\displaystyle (m,d)}$ a ${\displaystyle b}$ je vektor ${\displaystyle b\in \mathbb {R} ^{m}.}$^[1]

Takto definovaný polyedr je zobecněním konvexního mnohostěnu na libovolný počet rozměrů ${\displaystyle d}$. Navíc oproti běžné představě mnohostěnu může být neohraničený; doplněním podmínky ohraničenosti dostáváme jiný způsobe zavedení polytopu:

Konvexní polyedr ${\displaystyle P}$ je (konvexní) polytop pravě tehdy, když je ohraničený. (Minkowského věta)^[2]

Alternativní definice

Konvexní polytop lze alternativně definovat jako konvexní obal konečné množiny bodů ${\displaystyle \mathbb {R} ^{d}}$ (vrcholů).

Každý polytop plné dimenze rozděluje prostor své dimenze na svůj vnitřek, vnějšek a hranici. Každá úsečka, která spojuje nějaký vnitřní a nějaký vnější bod, protíná nadstěnu polytopu právě v jednom bodě. Průnik dvou polytopů plné dimenze se společným vnitřním bodem je opět polytopem plné dimenze. Matematickou indukcí lze dokázat, že totéž platí pro konečný počet polytopů plné dimenze se společným vnitřním bodem.

Každé nadstěně (tedy koncovému bodu pro úsečky, hraně pro mnohoúhelníky atd.) polytopu lze přiřadit poloprostor, na jehož hranici nadstěna leží, a která polytop obsahuje. Chceme-li to provést, představíme si část prostoru, která leží na straně hraniční plochy obrácené k polytopu. Takový poloprostor lze chápat jako množinu bodů, které ve svých kartézských souřadnicích vyhovují nějaké lineární nerovnosti. Průnik všech poloprostorů s každou z ploch je opět polytop. Každý konvexní polytop lze tedy popsat jako množinu řešení soustavy lineárních nerovnic s konečně mnoha proměnnými. Pokud je množina řešení lineárního systému nerovnic omezená (tj. vzdálenost mezi všemi body je omezená), platí i obrácené tvrzení.

Jestliže

${\displaystyle a^{T}x\leq b}$

je lineární nerovnice, kterou splňují všechny body polytopu, pak průnik polytopu s množinou, pro kterou je splněna rovnost

${\displaystyle \{x|a^{T}x=b\}}$

označované jako stěna. Každá stěna může být reprezentována nějakou takovou nerovnicí. Pro speciální případ nerovnice

${\displaystyle 0^{T}x\leq 0}$

je průnikem celý polytop; naopak pro nerovnici

${\displaystyle 0^{T}x\leq 1}$

je průnikem prázdná množina:

${\displaystyle \{x|0^{T}x=1\}\cap P=\{x|0^{T}x=1\}=\varnothing }$

Množina všech stěn polytopu je uspořádána inkluzí. Nadstěna ${\displaystyle n}$-rozměrného konvexního polytopu je pak ${\displaystyle (n-1)}$-rozměrná nadstěna. Například u trojrozměrné krychle jsou všechny vrcholy, hrany a stěny krychle „hraničními plochami“, ale hraničními plochami jsou také prázdná množina a celá krychle. Ale pouze dvourozměrné hraniční plochy jsou stěnami krychle.

Vrchol konvexního polytopu je takový bod polytopu, který není konvexní kombinací jiných bodů polytopu, což znamená, že neleží na úsečce mezi dvěma jinými body polytopu. To odpovídá grafické představě vrcholu. Není například možné sestrojit úsečku mezi dvěma body krychle, jejímž vnitřním bodem je vrchol krychle. Vrchol ${\displaystyle x}$ polytopu ${\displaystyle P}$ nazýváme degenerovaný, pokud počet nadstěn, které obsahují bod ${\displaystyle x}$ je větší než dimenze ${\displaystyle P}$. Například vrchol trojrozměrné pyramidy se čtvercovou základnou je degenerovaný, protože je obsažen ve čtyřech stěnách. Konvexní polytop nazýváme celočíselný, pokud jsou všechny jeho vrcholy popsány celočíselnými souřadnicemi. Tyto pojmy jsou důležité mimo jiné v lineárním programování a celočíselném programování, protože optima lineární funkce je dosaženo vždy alespoň v jednom vrcholu.

Odkazy

Reference

V tomto článku byly použity překlady textů z článků Polytop (geometrie) na německé Wikipedii a Polytope na anglické Wikipedii.

Literatura

• COXETER, Harold Scott MacDonald. Regular polytopes. 3. vyd. [s.l.]: Dover Publications, 1973. ISBN 0-486-61480-8. 
• ZIEGLER, Günter M. Lectures on polytopes. [s.l.]: Springer Verlag, 1995. ISBN 0-387-94365-X. 
• GRÜNBAUM, Branko. Convex polytopes. Příprava vydání Volker Kaibel, Victor Klee, Günter M. Ziegler. 2. vyd. [s.l.]: Springer-Verlag, 2003. ISBN 0-387-00424-6. 
• TURZÍK, Daniel. Matematika III: základy optimalizace. 3. vyd. Praha: Vysoká škola chemicko-technologická v Praze, 1999. ISBN 80-7080-363-0. 

Související články

• Nadkrychle (hyperkrychle)

Externí odkazy

• Obrázky, zvuky či videa k tématu mnohostěn na Wikimedia Commons