Hassediagram

Från Wikipedia
Hoppa till: navigering, sök
Potensmängden för en mängd med två element ordnat efter inklusivitet.

Inom ordningsteori är ett Hassediagram ett slags matematiskt diagram som används för att representera en ändlig partiellt ordnad mängd ("pomängd") som ett nätverksdiagram över dess transitiva reduktion. För en partiellt ordnad mängd (S, ≤) representeras varje element i S som ett hörn i planet och en kant sammanbinder hörnet x uppåt med alla hörn y som täcker x, det vill säga närhelst x < y och det inte finns något z sådant att x < z < y. Dessa kanter får korsa varandra men ej passera några andra hörn än sina respektive ändpunkter. Ett sådant diagram med betecknade hörn beskriver mängdens partiella ordning på ett unikt sätt.

Hassediagram är uppkallade efter Helmut Hasse (1898–1979) enligt Birkhoff (1948) och de kallas så på grund av Hasses användning av dem. Det var dock inte Hasse som använde dem först, de förekommer exempelvis i Vogt (1895). Fastän Hassediagram ursprungligen designats för att rita grafer över partiellt ordnade mängder för hand, har de på senare tid konstruerats automatiskt.[1]

Ett "bra" Hassediagram[redigera | redigera wikitext]

Fastän Hassediagram är enkla likväl som intuitiva verktyg för hantering av finita pomängder, visar det sig vara ganska svårt att rita "bra" diagram. Anledningen till detta är att det i allmänhet finns många möjliga sätt att rita ett Hassediagram för en pomängd. Den enkla metoden att bara börja med de minsta elementen soch sedan fortsätta uppåt med större element i ordning ger ofta ganska dåliga resultat: symmetrier och interna strukturer går lätt förlorade.

Nedanstående exempel visar problemet. Betrakta potensmängden (mängden av delmängder) av en mängd med fyra element som ordnas efter inklusivitet (om de är delmängder av en mängd med ett element mer). Varje delmängd har en nod som är fyrställigt betecknad med huruvida ett element ingår i delmängden (1) eller ej (0):

Hypercubeorder binary.svg     Hypercubecubes binary.svg     Hypercubestar binary.svg     Hypercubematrix binary.svg

Det första diagrammet visar tydligt att potensmängden är rangordnad efter hur många element som ingår (antalet ettor). Det andra diagrammet har samma rangordnade struktur, men genom att förlänga vissa kanter förstärker man intrycket av att strukturen är en tesserakt, som är en förening av två tredimensionella kuber. Det tredje visar en del av den inre strukturen och i den fjärde är hörnen arrangerade som en 4×4-matris.

Exempel[redigera | redigera wikitext]

Delbarhetsgitter[redigera | redigera wikitext]

Med Hassediagram kan man framställa sambanden mellan olika faktoriseringar. I diagrammet nedan visas de tal som kan bildas genom multiplikation av två, tre och fem. Med utgångspunkt i hörnet representerande ett längst ner leder kanter uppåt till 1⋅2=2, 1⋅3=3 och 1⋅5=5. Därifrån nya kanter till hörn representerande resultatet av dessa tal multiplicerade med två, tre respektive fem, etcetera. Man kan fylla på med ytterligare primtal (7, 11, 13...), men bilden blir strax ganska gyttrig.

Delbarhetsgitter för "reguljära tal"; tal delbara med 2, 3 och 5. (Notera även att värdena ligger på en höjd över "baslinjen" som är proportionell mot logaritmen på talet.)

Partitioner av mängder[redigera | redigera wikitext]

Hassediagram över partitioner av en mängd med fyra element sorterade efter "finhet". Med "finhet" avses här att en partition P är finare än en partition Q om varje element i P är en delmängd till ett element i Q. Om vi börjar nerifrån i det vänstra diagrammet nedan, så utgår vi från alla de fyra partitionerna av storleken ett: {1},{2},{3},{4}. Slår vi ihop två av dessa partitioner, vilket ju kan göras på sex olika sätt, får vi partitionerna i raden ovanför så att vi nu har tre partitioner. Slå ihop två av dessa tre partitioner, vilket kan göras på tre sätt varför det finns tre kanter uppåt från varje, och vi har två partitioner kvar (som kan se ut på sju olika sätt - 3+1 på fyra sätt och 2+2 på tre - beroende på vilken väg vi hittills valt). Dessa slås till slut ihop till hela {1,2,3,4} i diagrammets topp. I det högra diagrammet visas "redundanta" kanter med rött - kanter som förvisso uppfyller finhetskravet, men där det finns mellanliggande hörn så att kanterna därför ej ingår i Hassediagrammet.

Lattice of partitions of an order 4 set.svg
   
Lattice of partitions of an order 4 set redundant.svg

Noter[redigera | redigera wikitext]

  1. ^ Se till exempel Di Battista & Tamassia (1988) och Freese (2004).

Referenser[redigera | redigera wikitext]