Hasseův diagram - Hasse diagram
v teorie objednávek, a Hasseův diagram (/ˈh…sə/; Němec: [ˈ máə]) je typ matematický diagram slouží k reprezentaci konečné částečně objednaná sada ve formě a výkres jeho přechodná redukce. Konkrétně pro částečně objednanou sadu (S, ≤) jeden představuje každý prvek S jako vrchol v rovině a nakreslí a úsečka nebo křivka, která jde nahoru z X na y kdykoli y kryty X (tj. kdykoli X < y a není z takhle X < z < yTyto křivky se mohou navzájem protínat, ale nesmí se dotýkat žádných jiných vrcholů než jejich koncových bodů. Takový diagram se značenými vrcholy jednoznačně určuje jeho dílčí pořadí.
Schémata jsou pojmenována po Helmut Hasse (1898–1979); podle Garrett Birkhoff (1948 ), nazývají se proto, že je Hasse efektivně využil. Hasse však nebyl první, kdo tyto diagramy použil. Jeden příklad, který předchází Hasse, lze najít v Henri Gustav Vogt (1895 ). Ačkoli Hasseovy diagramy byly původně navrženy jako technika pro ruční kreslení částečně uspořádaných sad, byly nedávno vytvořeny automaticky pomocí kreslení grafu techniky.[1]
Fráze „Hasseův diagram“ může také označovat přechodnou redukci jako abstrakt směrovaný acyklický graf, nezávisle na jakémkoli výkresu daného grafu, ale zde se tomuto použití vyhýbá.[2][3][4]
„Dobrý“ Hasseův diagram
Přestože jsou Hasseovy diagramy jednoduché i intuitivní nástroje pro práci s konečnými posety, se ukazuje jako poměrně obtížné nakreslit „dobré“ diagramy. Důvodem je, že obecně existuje mnoho možných způsobů, jak nakreslit Hasseův diagram pro daný poset. Jednoduchá technika, jak začít s minimální prvky objednávky a následné postupné kreslení větších prvků často přináší docela špatné výsledky: symetrie a vnitřní struktura objednávky se snadno ztratí.
Následující příklad ukazuje problém. Zvažte napájecí sada 4prvkové sady objednané zahrnutím . Níže jsou uvedeny čtyři různé Hasseovy diagramy pro tuto částečnou objednávku. Každá podmnožina má uzel označený binárním kódováním, které ukazuje, zda je určitý prvek v podmnožině (1) nebo ne (0):
První diagram objasňuje, že napájecí sada je a odstupňovaná poset. Druhý diagram má stejnou odstupňovanou strukturu, ale tím, že dělá některé hrany delší než jiné, zdůrazňuje, že 4-rozměrná kostka je kombinatorické spojení dvou trojrozměrných kostek, a to čtyřstěn (abstraktní 3-mnohostěn ) rovněž sloučí dva trojúhelníky (abstraktní 2-polytopy ). Třetí diagram ukazuje část vnitřní symetrie struktury. Ve čtvrtém diagramu jsou vrcholy uspořádány jako prvky 4 × 4 matice.
Vzestupná rovinnost
Pokud lze dílčí pořadí nakreslit jako Hasseho diagram, ve kterém se neprotínají dvě hrany, říká se, že jeho krycí graf je nahoru planární. Je známa řada výsledků o vzestupné rovinnosti a konstrukci Hasseova diagramu bez křížení:
- Pokud je dílčí pořadí, které má být vylosováno, a mříž, pak ji lze nakreslit bez křížení, pouze pokud má dimenze objednávky maximálně dva.[5] V tomto případě lze nalézt nepřekřížený výkres odvozením karteziánských souřadnic pro prvky z jejich pozic ve dvou lineárních řádech realizujících rozměr řádu a následným otočením výkresu proti směru hodinových ručiček o úhel 45 stupňů.
- Pokud má dílčí objednávka maximálně jednu minimální prvek nebo má nejvýše jednu maximální prvek, pak to může být testováno v lineární čas zda má nepřekračující Hasseův diagram.[6]
- to je NP-kompletní k určení, zda lze dílčí pořadí s více zdroji a výlevkami nakreslit jako Hasseův diagram bez křížení.[7] Nalezení přechodového diagramu Hasse však není fixovatelný parametr při parametrizaci počtem artikulační body a tři propojené komponenty přechodné redukce částečné objednávky.[8]
- Pokud y- jsou zadány souřadnice prvků dílčího řádu, pak lze v lineárním čase najít křížový Hasseův diagram respektující tato přiřazení souřadnic, pokud takový diagram existuje.[9] Zejména pokud je vstupní poset a odstupňovaná poset, je možné v lineárním čase určit, zda existuje Hasseův diagram bez křížení, ve kterém je výška každého vrcholu úměrná jeho hodnosti.
Notace UML
Standardní diagram pro řetězec inkluzí je Třída UML, spojující sady podle dědičnosti. Obrázek ukazuje a vnořená sada kolekce, C:
- B = {♠, ♥, ♦, ♣}; B1 = {♠, ♥}; B2 = {♦, ♣}; B3 = {♣};
C = {B, B1, B2, B3}.
Poznámky
- ^ Např. Viz Di Battista & Tamassia (1988) a Freese (2004).
- ^ Christofides, Nicos (1975), Teorie grafů: algoritmický přístup, Academic Press, s. 170–174.
- ^ Thulasiraman, K .; Swamy, M. N. S. (1992), „5,7 Acyclic Directed Graphs“, Grafy: Teorie a algoritmy, John Wiley and Son, str. 118, ISBN 978-0-471-51356-8.
- ^ Bang-Jensen, Jørgen (2008), „2.1 Acyclic Digraphs“, Digrafy: Teorie, algoritmy a aplikaceSpringer Monographs in Mathematics (2. vyd.), Springer-Verlag, s. 32–34, ISBN 978-1-84800-997-4.
- ^ Garg & Tamassia (1995a), Věta 9, s. 118; Baker, Fishburn & Roberts (1971), věta 4.1, strana 18.
- ^ Garg & Tamassia (1995a), Věta 15, s. 125; Bertolazzi a kol. (1993).
- ^ Garg & Tamassia (1995a), Dodatek 1, s. 132; Garg & Tamassia (1995b).
- ^ Chan (2004).
- ^ Jünger & Leipert (1999).
Reference
- Baker, Kirby A .; Fishburn, Peter C.; Roberts, Fred S. (1971), „Částečné objednávky dimenze 2“, Sítě, 2 (1): 11–28, doi:10,1002 / net.3230020103.
- Bertolazzi, R; Di Battista, G .; Mannino, C .; Tamassia, R. (1993), „Optimální testování rovinnosti směrem vzhůru u jednozdrojových digrafů“ (PDF), Proc. 1. evropské symposium o algoritmech (ESA '93), Přednášky z informatiky, 726, Springer-Verlag, str. 37–48, doi:10.1007/3-540-57273-2_42, ISBN 978-3-540-57273-2.
- Birkhoff, Garrett (1948), Teorie mřížky (Přepracované vydání), Americká matematická společnost.
- Chan, Hubert (2004), „Parametrizovaný algoritmus pro testování plošnosti nahoru“, Proc. 12. evropské sympozium o algoritmech (ESA '04), Přednášky v informatice, 3221, Springer-Verlag, str. 157–168, doi:10.1007/978-3-540-30140-0_16.
- Di Battista, G .; Tamassia, R. (1988), "Algoritmy pro rovinnou reprezentaci acyklických digrafů", Teoretická informatika, 61 (2–3): 175–178, doi:10.1016/0304-3975(88)90123-5.
- Freese, Ralph (2004), „Automated lattice drawing“, Concept Lattices, Přednášky v informatice, 2961, Springer-Verlag, str. 589–590. Rozšířený předtisk je k dispozici online: [1].
- Garg, Ashim; Tamassia, Roberto (1995a), „Vzestupné testování rovinnosti“, Objednat, 12 (2): 109–133, doi:10.1007 / BF01108622, S2CID 14183717.
- Garg, Ashim; Tamassia, Roberto (1995b), „O výpočetní složitosti vzestupného a přímočarého testování rovinnosti“, Kreslení grafu (Proc. GD '94) Přednáška Poznámky v informatice, 894, Springer-Verlag, str. 286–297, doi:10.1007/3-540-58950-3_384, ISBN 978-3-540-58950-1.
- Jünger, Michael; Leipert, Sebastian (1999), „Rovinné zakládání rovin v lineárním čase“, Kreslení grafu (Proc. GD '99), Přednášky v informatice, 1731, str. 72–81, doi:10.1007/3-540-46648-7_7, ISBN 978-3-540-66904-3.
- Vogt, Henri Gustav (1895), Leçons sur la résolution algébrique des équations, Nony, str. 91.
externí odkazy
- Související média na Wikimedia Commons:
- Hasseův diagram (Galerie)
- Hasse diagramy (Kategorie)
- Weisstein, Eric W. "Hasseův diagram". MathWorld.