Diagram Hasse

Dalam teori order, diagram Hasse (/ˈhæsə/; Jerman: [ˈhasə]) adalah sebuah tipe diagram matematika yang digunakan untuk menyatakan sebuah himpunan terurut parsial berhingga, dalam bentuk gambar reduksi transitifnya. Lebih spesifik, untuk sebuah himpunan terurut parsial $(S,\,\leq )$ , setiap elemen dari $S$ akan merepresentasikan sebuah simpul; dan segmen garis/kurva yang naik dari $x$ dan $y$ digambarkan ketika $x\neq y$ dan $y$ menutupi (covers) $x$ (tidak ada $z$ sehingga $x\leq z\leq y$ ). Kurva-kurva ini dapat saling bersilangan, namun tidak boleh menyentuh simpul-simpul apapun selain titik-titik ujungnya. Diagram yang dibuat dengan cara tersebut, dengan simpul-simpul berlabel, secara unik menentukan urutan parsial himpunan.

Diagram-diagram ini dinamai Helmut Hasse (1898-1979). Menurut Garrett Birkhoff (1948), diagram-diagram ini dinamakan demikian karena Hasse menggunakannya dengan efektif. Walaupun demikian, Hasse bukanlah yang pertama menggunakan diagram ini. Salah satu contoh yang mendahului Hasse dapat ditemukan pada Henri Gustav Vogt (1895). Meskipun diagram Hasse pada awalnya dirancang sebagai teknik untuk membuat gambar himpunan terurut parsial dengan tangan, namun baru-baru ini dapat dibuat secara otomatis dengan menggunakan teknik penggambaran graf.^[1]

Istilah "diagram Hasse" juga dapat merujuk kepada reduksi transitif sebagai sebuah graf asiklik terarah yang abstrak, terlepas dari penggambaran apapun dari graf tersebut; penggunaan istilah tersebut dihindari di artikel ini.^[2]^[3]^[4]

Desain diagram

Meskipun diagram Hasse adalah alat yang sederhana dan juga intuitif untuk berurusan dengan poset berhingga, secara implementasi agak sulit untuk dapat menggambar diagram Hasse yang "baik". Secara umum, hal ini akibatkan oleh banyaknya cara yang mungkin untuk menggambar diagram untuk poset yang diberikan. Teknik menggambar sederhana yang dimulai dari elemen-elemen minimal suatu urutan, dan kemudian menggambar elemen-elemen yang lebih besar secara bertahap, sering kali menghasilkan hasil yang sangat buruk: simetri dan struktur internal urutan mudah hilang.

Contoh berikut ini menunjukkan masalah tersebut. Pertimbangkan himpunan kuasa dari himpunan 4-elemen yang diurutkan berdasarkan inklusi $\subseteq$ . Di bawah ini adalah empat diagram Hasse yang berbeda untuk urutan parsial ini. Setiap himpunan bagian memiliki simpul yang diberi label dengan pengkodean biner yang menunjukkan apakah elemen tertentu ada di dalam subset (1) atau tidak (0):

Diagram pertama memperjelas bahwa himpunan kuasa adalah graded poset. Diagram kedua memiliki struktur graded yang sama, tetapi dengan membuat beberapa sisi lebih panjang dari yang lain, diagram ini menekankan bahwa kubus 4-dimensi adalah gabungan kombinatorial dari dua kubus 3-dimensi. Diagram ketiga menunjukkan beberapa simetri internal dari struktur. Pada diagram keempat, simpul-simpul disusun seperti elemen-elemen dari matriks 4×4.

Catatan kaki

^ E.g., see (Di Battista & Tamassia 1988) and (Freese 2004).
^ Christofides, Nicos (1975), Graph theory: an algorithmic approach, Academic Press, hlm. 170–174 .
^ Bang-Jensen, Jørgen (2008), "2.1 Acyclic Digraphs", Digraphs: Theory, Algorithms and Applications, Springer Monographs in Mathematics (edisi ke-2nd), Springer-Verlag, hlm. 32–34, ISBN 978-1-84800-997-4 .
^ Thulasiraman, K.; Swamy, M. N. S. (1992), "5.7 Acyclic Directed Graphs", Graphs: Theory and Algorithms, John Wiley and Son, hlm. 118, ISBN 978-0-471-51356-8 .

Referensi

Baker, Kirby A.; Fishburn, Peter C.; Roberts, Fred S. (1971), "Partial orders of dimension 2", Networks, 2 (1): 11–28, doi:10.1002/net.3230020103 .
Bertolazzi, R; Di Battista, G.; Mannino, C.; Tamassia, R. (1993), "Optimal upward planarity testing of single-source digraphs" (PDF), Proc. 1st European Symposium on Algorithms (ESA '93), Lecture Notes in Computer Science, 726, Springer-Verlag, hlm. 37–48, doi:10.1007/3-540-57273-2_42, ISBN 978-3-540-57273-2 .
Birkhoff, Garrett (1948), Lattice Theory (edisi ke-Revised), American Mathematical Society .
Chan, Hubert (2004), "A parameterized algorithm for upward planarity testing", Proc. 12th European Symposium on Algorithms (ESA '04), Lecture Notes in Computer Science, 3221, Springer-Verlag, hlm. 157–168, doi:10.1007/978-3-540-30140-0_16 .
Di Battista, G.; Tamassia, R. (1988), "Algorithms for plane representation of acyclic digraphs", Theoretical Computer Science, 61 (2–3): 175–178, doi:10.1016/0304-3975(88)90123-5  .
Freese, Ralph (2004), "Automated lattice drawing", Concept Lattices, Lecture Notes in Computer Science, 2961, Springer-Verlag, hlm. 589–590 . An extended preprint is available online: .
Garg, Ashim; Tamassia, Roberto (1995a), "Upward planarity testing", Order, 12 (2): 109–133, doi:10.1007/BF01108622 .
Garg, Ashim; Tamassia, Roberto (1995b), "On the computational complexity of upward and rectilinear planarity testing", Graph Drawing (Proc. GD '94), LectureNotes in Computer Science, 894, Springer-Verlag, hlm. 286–297, doi:10.1007/3-540-58950-3_384  , ISBN 978-3-540-58950-1 .
Jünger, Michael; Leipert, Sebastian (1999), "Level planar embedding in linear time", Graph Drawing (Proc. GD '99), Lecture Notes in Computer Science, 1731, hlm. 72–81, doi:10.1007/3-540-46648-7_7  , ISBN 978-3-540-66904-3 .
Vogt, Henri Gustav (1895), Leçons sur la résolution algébrique des équations, Nony, hlm. 91 .

Pranala luar

Media terkait di Wikimedia Commons:
- Hasse diagram (Gallery)
- Hasse diagrams (Category)
Weisstein, Eric W. "Hasse Diagram". MathWorld.

[1] E.g., see (Di Battista & Tamassia 1988) and (Freese 2004).

[2] Christofides, Nicos (1975), Graph theory: an algorithmic approach, Academic Press, hlm. 170–174 .

[3] Bang-Jensen, Jørgen (2008), "2.1 Acyclic Digraphs", Digraphs: Theory, Algorithms and Applications, Springer Monographs in Mathematics (edisi ke-2nd), Springer-Verlag, hlm. 32–34, ISBN 978-1-84800-997-4 .

[4] Thulasiraman, K.; Swamy, M. N. S. (1992), "5.7 Acyclic Directed Graphs", Graphs: Theory and Algorithms, John Wiley and Son, hlm. 118, ISBN 978-0-471-51356-8 .

[1]

[2]

[3]

[4]