Hassen kaavio

Hasse-diagrammi on kaavio , jota käytetään esittämään äärellinen osittain järjestetty joukko piirustuksena sen transitiivisesta supistumisesta . Tarkemmin sanottuna osittain järjestetylle joukolle kaavio esittää jokaisen elementin tason kärkeinä ja segmentteinä tai käyrinä, jotka nousevat elementistä elementtiin, jos ei ole elementtiä , jolle . Nämä käyrät voivat leikkiä, mutta ne eivät saa kulkea kärkien läpi, elleivät ne ole viivan päitä. Tällainen kaavio, jossa on merkittyjä pisteitä, määrittelee yksiselitteisesti osittaisen järjestyksen. $(S,\leq )$ $S$ $x$ $y$ $x\leq y$ $z$ $x<z<y$

Birkhoff kuvasi ensimmäistä kertaa systemaattisesti tällaista visualisointia vuonna 1948 [1] , hän antoi myös nimen Helmut Hassen kunniaksi, joka käytti vastaavia kaavioita , mutta tällaisia piirroksia löytyy myös aikaisemmista teoksista, mm. ranskalaisen matemaatikon Henri Vogtin oppikirja ( saksaksi: Henri Vogt ) 1895 painos [2] .

Kaavioiden käyttömukavuus

Vaikka Hasse-kaaviot ovat yksinkertainen ja intuitiivinen työkalu rajallisen osittain järjestetyn sarjan kanssa työskentelyyn , on erittäin vaikea piirtää "hyvää", visuaalisesti kätevää kaaviota melko ei-triviaalille joukolle mahdollisten näyttövaihtoehtojen suuren määrän vuoksi. Yksinkertainen tekniikka aloittaa pienimmistä elementeistä ja piirtää päällekkäiset elementit peräkkäin tuottaa usein huonoja tuloksia - symmetriaa ja sisäisiä rakenteita on helppo menettää.

Esimerkiksi neljän elementin joukon Boolen arvo, joka on järjestetty sisällyttämisoperaation mukaan , voidaan esittää millä tahansa alla olevista neljästä kaaviosta (jokainen osajoukko on varustettu binäärikoodatulla tunnisteella, joka osoittaa, sisältyykö vastaava elementti osajoukkoon - 1 tai ei - 0): $\subseteq$

Ensimmäinen kaavio näyttää tasorakenteen. Toisessa kaaviossa on sama tasorakenne, mutta joitain reunoja on pidennetty korostaen, että 4D-kuutio on kahden 3D-kuution liitto. Kolmas kaavio näyttää jonkin verran sisäistä symmetriaa. Neljännessä kaaviossa kärjet on järjestetty 4×4 matriisin tavoin.

Tasoisuus

Jotkut osittaisten järjestysten ominaisuudet, jotka koskevat niiden Hasse-kaavion tasomaisuutta (eli kykyä piirtää se ylittämättä reunoja):

Jos osajärjestys on hila , niin se voidaan piirtää ilman leikkauspisteitä silloin ja vain, jos järjestyksen mitta on vähintään kaksi [3] [4] .
Jos osittaisessa tilauksessa on vähintään yksi minimi- tai maksimielementti, voidaan lineaarisessa ajassa tarkistaa, onko olemassa kaaviota ilman leikkauspisteitä [5] .
Selvitä, voidaanko osittaista järjestystä esittää tasomaisella Hasse-kaaviolla, yleisessä tapauksessa - NP-täydellinen tehtävä [6] .
Jos annetaan osittaisen järjestyksen elementtien -koordinaatit, niin sen Hasse-kaavio löytyy lineaarisessa ajassa annetut koordinaatit säilyttäen, jos vain sellainen kaavio on olemassa [7] . Erityisesti, jos osittaisella järjestyksellä on tasoja, voidaan lineaarisessa ajassa määrittää, onko olemassa Hasse-kaaviota ilman leikkauspisteitä, jossa kunkin kärjen korkeus on verrannollinen sen järjestykseen. $y$

Muistiinpanot

↑ Birkhoff, 1948 .
↑ Focht, 1895 .
↑ Garg, Tamassia, 1995 , Lause 9, s. 118.
↑ Baker, Fishburne, Roberts 1971 , Lause 4.1, s. kahdeksantoista.
↑ Garg, Tamassia, 1995 , Lause 15, s. 125.
↑ Garg, Tamassia, 1995 , Seuraus 1, s. 132.
↑ Junger, Lipert, 1999 .

Kirjallisuus

K.A. Baker, P. Fishburn, F.S. Roberts. Dimension 2 osittaiset tilaukset // Verkot. - 1971. - V. 2 , nro 1 . — S. 11–28 . - doi : 10.1002/net.3230020103 . .
G. Birkhoff. Hilan teoria. – 2. - American Mathematical Society , 1948. Käännös venäjäksi: G. Birkhoff . Rakenteiden teoria / Per. M. I. Graeva. - 2. painos - M . : Ulkomainen kirjallisuus, 1952. - 408 s.
A. Garg, R. Tamassia. Ylöspäin tasomaisuuden testaus // Järjestys. - 1995. - T. 12 , nro 2 . — S. 109–133 . - doi : 10.1007/BF01108622 . .
R. Freese. Automatisoitu hilapiirustus // Concept Lattice. - Springer-Verlag, 2004. - T. 2961 . — S. 589–590 . .
M. Junger, S. Leipert. Tasomainen upotus lineaarisessa ajassa // Proc. kansainvälisen symposiumin graafisen piirtämisestä 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 resoluutio algebrique des equations. - Nony, 1895. - S. 91.

Linkit

Weisstein, Eric W. Hasse Diagram (englanniksi) Wolfram MathWorld -verkkosivustolla .