Hasseův diagram

Hasseův diagram  je typ diagramu používaný k reprezentaci konečné částečně uspořádané množiny jako kresby její tranzitivní kontrakce . Konkrétně pro částečně uspořádanou množinu představuje diagram každý prvek jako vrcholy v rovině a segmenty nebo křivky stoupající od prvku k prvku , pokud neexistuje žádný prvek , pro který by . Tyto křivky se mohou protínat, ale nesmí procházet vrcholy, pokud to nejsou konce čar. Takový diagram s označenými vrcholy jednoznačně definuje částečné pořadí.

Poprvé systematicky tento druh vizualizace popsal Birkhoff v roce 1948 [1] , jméno dal také na počest Helmuta Hasse , který používal podobná schémata , nicméně takové kresby se nacházejí i v dřívějších dílech, např. učebnice francouzského matematika Henriho Vogta ( německy  Henri Vogt ) vydání z roku 1895 [2] .

Pohodlí diagramů

Přestože jsou Hasseovy diagramy jednoduchým a intuitivním nástrojem pro práci s konečnou částečně uspořádanou množinou , je velmi obtížné nakreslit „dobrý“, vizuálně vhodný diagram pro poměrně netriviální množinu kvůli velkému množství možných možností zobrazení. Jednoduchá technika, kdy se začíná s nejmenšími prvky a postupně se kreslí nad nimi ležící prvky, často dává špatné výsledky – symetrie a vnitřní struktury se snadno ztratí.

Například Boolean množiny čtyř prvků, uspořádaných operací zahrnutí , může být reprezentován kterýmkoli ze čtyř níže uvedených diagramů (každá podmnožina je opatřena binárně kódovaným štítkem označujícím, zda je odpovídající prvek obsažen v podmnožině - 1 nebo ne - 0):

První diagram ukazuje strukturu úrovní. Druhý diagram má stejnou strukturu úrovní, ale některé hrany jsou prodlouženy, aby se zdůraznilo, že 4D krychle je spojením dvou 3D krychlí. Třetí diagram ukazuje určitou vnitřní symetrii. Ve čtvrtém diagramu jsou vrcholy uspořádány jako matice 4×4.

Rovinnost

Některé vlastnosti dílčích řádů týkající se rovinnosti jejich Hasseova diagramu (tj. schopnosti nakreslit jej bez křížení hran):

• Je-li dílčí zakázka mřížkou , pak ji lze kreslit bez průsečíků právě tehdy, je-li rozměr zakázky alespoň dva [3] [4] .
• Pokud má dílčí zakázka alespoň jeden minimální nebo maximální prvek, pak je možné lineárně ověřit, zda existuje diagram bez průniků [5] .
• Určete, zda může být dílčí řád reprezentován rovinným Hasseovým diagramem, v obecném případě - NP-úplný problém [6] .
• Jsou-li uvedeny -souřadnice prvků dílčího řádu, pak jeho Hasseův diagram lze nalézt v lineárním čase , při zachování daných souřadnic, pokud pouze takový diagram existuje [7] . Zejména, pokud má dílčí řád úrovně, je možné v lineárním čase určit, zda existuje Hasseův diagram bez průniků, ve kterém je výška každého vrcholu úměrná jeho pozici.

Poznámky

1. ↑ Birkhoff, 1948 .
2. ↑ Focht, 1895 .
3. ↑ Garg, Tamassia, 1995 , věta 9, str. 118.
4. ↑ Baker, Fishburne, Roberts 1971 , věta 4.1, str. osmnáct.
5. ↑ Garg, Tamassia, 1995 , věta 15, str. 125.
6. ↑ Garg, Tamassia, 1995 , důsledek 1, str. 132.
7. ↑ Junger, Lipert, 1999 .

Literatura

• K. A. Baker, P. Fishburn, F. S. Roberts. Dílčí objednávky dimenze 2 // Sítě. - 1971. - V. 2 , č. 1 . — S. 11–28 . - doi : 10.1002/net.3230020103 . .
• G. Birkhoff. Teorie mřížky. — 2. — American Mathematical Society , 1948. Překlad do ruštiny: G. Birkhoff . Teorie struktur / Per. M. I. Graeva. - 2. vyd. - M . : Zahraniční literatura, 1952. - 408 s.
• A. Garg, R. Tamassia. Testování rovinnosti směrem nahoru // Objednávka. - 1995. - T. 12 , č. 2 . — S. 109–133 . - doi : 10.1007/BF01108622 . .
• R. Freese. Automatizované kreslení mřížek  // Concept Lattice. - Springer-Verlag, 2004. - T. 2961 . — S. 589–590 . .
• M. Junger, S. Leipert. Level planar embedding in linear time // Proc. mezinárodního sympozia o grafové kresbě GD '99. - 1999. - T. 1731 . — S. 72–81 . — ISBN 978-3-540-66904-3 . - doi : 10.1007/3-540-46648-7_7 .
• HG Vogt. Lecons sur la resolution algebrique des équations. - Nony, 1895. - S. 91.

Odkazy

• Weisstein, Eric W. Hasse Diagram  (anglicky) na webu Wolfram MathWorld .