Polytop

Z Wikipedie, otevřené encyklopedie
Skočit na navigaci Skočit na vyhledávání
Posunutím bodu o určitou vzdálenost dostaneme úsečku, posunutím úsečky kolmo na její směr o stejnou vzdálenost dostaneme čtverec, posunutím čtverce o stejnou vzdálenost kolmo na jeho rovinu dostaneme krychli, posunutím krychle o stejnou vzdálenost kolmo na její prostor, dostaneme 4rozměrnou nadkrychli neboli teserakt

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. Chceme-li zdůrazit počet rozměrů d, mluvíme o d-polytopu.

Definice[editovat | editovat zdroj]

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

Terminologie[editovat | editovat zdroj]

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

Dimenze Název d-polytopu
0 Bod
1 Úsečka
2 Mnohoúhelník
3 Mnohostěn
4 Polychor

Pokud mluvíme o polytopu dimenze d, používají se následující názvy:

Dimenze Název části polytopu (anglicky face)
0 Vrchol (anglicky vertex, pl. vertices)
1 Hrana (anglicky edge)
2 Stěna (anglicky side)
3 Buňka (anglicky cell)
d − 3 (anglicky peak)
d − 2 Hřeben (anglicky ridge, subfacet), tj. vrchol pro mnohoúhelníky (d = 2), hrana pro mnohostěny (d = 3), …
d − 1 Nadstěna (anglicky facet), tj. hrana pro mnohoúhelníky (d = 2), stěna pro mnohostěny (d = 3), …
d Nadtěleso (anglicky body) - vlastní polytop

Dimenze polytopu je definována jako rozměr jeho afinnního obalu, tj. nejmenší afinní prostor, který obsahuje polytop . 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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

Konvexní polyedr je průnik konečně mnoha podprostorů prostoru . Polyedr je tedy každá množina tvaru

kde je nějaká matice typu a je vektor [1]

Takto definovaný polyedr je zobecněním konvexního mnohostěnu na libovolný počet rozměrů . 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 je (konvexní) polytop pravě tehdy, když je ohraničený. (Minkowského věta)[2]

Alternativní definice[editovat | editovat zdroj]

Konvexní polytop lze alternativně definovat jako konvexní obal konečné množiny bodů (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ě (tj. 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

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

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

je průnikem celý polytop; naopak pro nerovnici

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

Množina všech stěn polytopu je uspořádána inkluzí. Nadstěna -rozměrného konvexního polytopu je pak -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 polytopu nazýváme degenerovaný, pokud počet nadstěn, které obsahují bod je větší než dimenze . 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[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]

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

  1. Turzík 1999, s. 22.
  2. Turzík 1999, s. 25.

Literatura[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]