Hasse diagram

Ett Hasse-diagram  är en typ av diagram som används för att representera en ändlig , delvis ordnad uppsättning som en ritning av dess transitiva sammandragning . Specifikt för en delvis ordnad uppsättning representerar diagrammet varje element som hörn i planet och segment eller kurvor som går upp från element till element om och det inte finns något element för vilket . Dessa kurvor kan skära varandra, men får inte passera genom hörn om de inte är linjeändar. Ett sådant diagram med märkta hörn definierar unikt en delordning.

För första gången systematiskt beskrevs denna typ av visualisering av Birkhoff 1948 [ 1] , han gav också namnet för att hedra Helmut Hasse , som använde liknande diagram , men sådana ritningar finns också i tidigare verk, t.ex. läroboken för den franske matematikern Henri Vogt ( tyska:  Henri Vogt ) 1895 års upplaga [2] .

Bekvämlighet med diagram

Även om Hasse-diagram är ett enkelt och intuitivt verktyg för att arbeta med en ändlig , delvis ordnad uppsättning , är det mycket svårt att rita ett "bra", visuellt bekvämt diagram för en ganska icke-trivial uppsättning på grund av det stora antalet möjliga visningsalternativ. Den enkla tekniken att börja med de minsta elementen och rita de överliggande elementen sekventiellt ger ofta dåliga resultat - symmetrier och inre strukturer är lätta att förlora.

Till exempel kan en boolean av en uppsättning av fyra element, ordnad efter inkluderingsoperationen , representeras av något av de fyra diagrammen nedan (varje delmängd är försedd med en binärkodad etikett som anger om motsvarande element finns i delmängden - 1, eller inte - 0):

Det första diagrammet visar nivåstrukturen. Det andra diagrammet har samma nivåstruktur, men några av kanterna är förlängda för att understryka att 4D-kuben är föreningen av två 3D-kuber. Det tredje diagrammet visar viss intern symmetri. I det fjärde diagrammet är hörnen ordnade som en 4×4-matris.

Planaritet

Vissa egenskaper hos partiella ordningar angående planheten hos deras Hasse-diagram (det vill säga förmågan att rita det utan att korsa kanter):

Anteckningar

  1. ↑ Birkhoff, 1948 .
  2. ↑ Focht, 1895 .
  3. ↑ Garg, Tamassia, 1995 , Theorem 9, sid. 118.
  4. ↑ Baker, Fishburne, Roberts 1971 , Theorem 4.1, sid. arton.
  5. ↑ Garg, Tamassia, 1995 , Theorem 15, sid. 125.
  6. ↑ Garg, Tamassia, 1995 , Corollary 1, sid. 132.
  7. ↑ Junger, Lipert, 1999 .

Litteratur

Länkar