Visa källa för Hassediagram

Du har inte behörighet att redigera denna sida, av följande anledning:

Your IP address is in a range that has been blocked on all Wikimedia Foundation wikis.

The block was made by ‪Hasley‬. The reason given is Open proxy/Webhost: See the help page if you are affected: .

Start of block: 18 december 2022 kl. 17.21
Expiry of block: 18 december 2025 kl. 17.21

Your current IP address is 62.210.136.28. The blocked range is 62.210.0.0/16.

Inkludera alla ovanstående detaljer i alla frågor du ställer. If you believe you were blocked by mistake, you can find additional information and instructions in the No open proxies global policy.

Otherwise, to discuss the block please post a request for review on Meta-Wiki. You could also send an email to the stewards VRT queue at stewards@wikimedia.org including all above details.

Du kan se och kopiera denna sidas källtext.

[[File:Inclusion ordering.svg|thumb|[[Potensmängd]]en för en mängd med två element ordnad efter [[inklusion|inklusivitet]].]]
Inom [[ordningsteori]] är ett '''Hassediagram''' ett slags matematiskt diagram som används för att representera en ändlig [[partialordnad mängd]] ("pomängd") som ett [[nätverksdiagram]] över dess [[täckningsrelation]]. För en partiellt ordnad mängd ''(S,&nbsp;≤)'' representeras varje element i ''S'' som ett [[Nod (grafteori)|hörn]] i planet och en [[Kant (grafteori)|kant]] sammanbinder hörnet ''x'' uppåt med alla hörn ''y'' som täcker ''x'', det vill säga närhelst ''x''&nbsp;&lt;&nbsp;''y'' och det inte finns något ''z'' sådant att ''x''&nbsp;&lt;&nbsp;''z''&nbsp;&lt;&nbsp;''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 {{harvtxt|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 {{harvtxt|Vogt|1895}}. Fastän Hassediagram ursprungligen designats för att rita grafer över pomängder för hand, har de på senare tid konstruerats automatiskt.<ref>Se till exempel {{harvtxt|Di Battista|Tamassia|1988}} och {{harvtxt|Freese|2004}}.</ref>

== Ett "bra" Hassediagram ==
Fastän Hassediagram är enkla likväl som intuitiva verktyg för hantering av finita [[pomängd]]er, 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 och 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ängd]]en (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):

{| style="margin: 0 auto;"
| [[File:Hypercubeorder binary.svg|230px|]] ||&nbsp;&nbsp;&nbsp;|| [[File:Hypercubecubes binary.svg|260px|]] ||&nbsp;&nbsp;&nbsp;|| [[File:Hypercubestar binary.svg|240px|]] ||&nbsp;&nbsp;&nbsp;|| [[File:Hypercubematrix binary.svg|180px|]]
|}

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 (andra och tredje positionerna "värderas högre" än första och fjärde) och i det fjärde är hörnen i den tredje arrangerade som en 4×4-matris.

==Exempel==
===Delbarhetsgitter===
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.
[[File:Regular divisibility lattice.svg|center|500px|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===
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''.
{| style="margin: 0 auto;"
| [[File:Lattice of partitions of an order 4 set.svg|thumb|350px|left]] ||&nbsp;&nbsp;&nbsp;|| [[File:Lattice of partitions of an order 4 set redundant.svg|thumb|350px|left]]
|}

== Referenser ==
=== Noter ===
<references/>
=== Källor ===
*{{citation|first1=K. A.|last1=Baker|first2=P.|last2=Fishburn|author2-link=Peter C. Fishburn|first3=F. S.|last3=Roberts|author3-link=Fred S. Roberts|title=Partial orders of dimension 2|journal=Networks|volume=2|pages=11–28|issue=1|doi=10.1002/net.3230020103|year=1971}}.
*{{citation|last1=Bertolazzi|first1=R|last2=Di Battista|first2=G.|last3=Mannino|first3=C.|last4=Tamassia|first4=R.|author4-link=Roberto Tamassia|year=1993|contribution=Optimal upward planarity testing of single-source digraphs|title=[[European Symposium on Algorithms|Proc. 1st European Symposium on Algorithms (ESA '93)]]|volume=726|series=Lecture Notes in Computer Science|publisher=Springer-Verlag|pages=37–48|doi=10.1007/3-540-57273-2_42}}.
*{{citation|first=Garrett|last=Birkhoff|authorlink=Garrett Birkhoff|title=Lattice Theory|edition=Revised|publisher=[[American Mathematical Society]]|year=1948}}.
*{{citation|first=Hubert|last=Chan|contribution=A parameterized algorithm for upward planarity testing|title=[[European Symposium on Algorithms|Proc. 12th European Symposium on Algorithms (ESA '04)]]|year=2004|volume=3221|series=Lecture Notes in Computer Science|publisher=Springer-Verlag|pages=157–168|url=https://link.springer.com/chapter/10.1007/978-3-540-30140-0_16}}.
*{{citation|first1=G.|last1=Di Battista|first2=R.|last2=Tamassia|author2-link=Roberto Tamassia|title=Algorithms for plane representation of acyclic digraphs|journal=Theoretical Computer Science|volume=61|year=1988|pages=175–178|doi=10.1016/0304-3975(88)90123-5|issue=2–3}}.
*{{citation|first=Ralph|last=Freese|contribution=Automated lattice drawing|title=Concept Lattices|publisher=Springer-Verlag|series=Lecture Notes in Computer Science|volume=2961|pages=589–590|year=2004}}. Ett utökat förtryck finns online på: [http://www.math.hawaii.edu/~ralph/Preprints/latdrawing.pdf].
*{{citation|first1=Ashim|last1=Garg|first2=Roberto|last2=Tamassia|author2-link=Roberto Tamassia|title=Upward planarity testing|journal=[[Order (journal)|Order]]|volume=12|pages=109–133|year=1995a|doi=10.1007/BF01108622|issue=2}}.
*{{citation|first1=Ashim|last1=Garg|first2=Roberto|last2=Tamassia|author2-link=Roberto Tamassia|year=1995b|contribution=On the computational complexity of upward and rectilinear planarity testing|title=[[International Symposium on Graph Drawing|Graph Drawing (Proc. GD '94)]]|volume=894|series=LectureNotes in Computer Science|publisher=Springer-Verlag|pages=286–297|doi=10.1007/3-540-58950-3_384}}.
*{{citation|first1=Michael|last1=Jünger|first2=Sebastian|last2=Leipert|contribution=Level planar embedding in linear time|title=[[International Symposium on Graph Drawing|Graph Drawing (Proc. GD '99)]]|year=1999|volume=1731|pages=72–81|doi=10.1007/3-540-46648-7_7|series=Lecture Notes in Computer Science|isbn=978-3-540-66904-3}}.
*{{citation|first=Henri Gustav|last=Vogt|publisher=Nony|year=1895|page=91|title=Leçons sur la résolution algébrique des équations}}.

[[Kategori:Grafteori]]
[[Kategori:Mängdteori]]
[[Kategori:Matematiska relationer]]
[[Kategori:Ordningsteori]]

Mallar som används på den här sidan:

Mall:Citation (redigera)
Mall:Citation/core (visa wikitext) (endast etablerade användare)
Mall:Harvard citation/core (redigera)
Mall:Harvard citation text (redigera)
Mall:Harvtxt (redigera)
Mall:ISBN (visa wikitext) (delvis skyddad)
Mall:Italiclink (visa wikitext) (delvis skyddad)
Mall:Link (visa wikitext) (endast etablerade användare)
Modul:Footnotes (redigera)
Modul:ISBN (visa wikitext) (delvis skyddad)
Modul:String (visa wikitext) (endast etablerade användare)

Tillbaka till Hassediagram.

Hämtad från ”https://sv.wikipedia.org/wiki/Hassediagram”