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 ${\displaystyle (S,\,\leq )}$, setiap elemen dari ${\displaystyle S}$ akan merepresentasikan sebuah simpul; dan segmen garis/kurva yang naik dari ${\displaystyle x}$ dan ${\displaystyle y}$ digambarkan ketika ${\displaystyle x\neq y}$ dan ${\displaystyle y}$ menutupi (covers) ${\displaystyle x}$ (tidak ada ${\displaystyle z}$ sehingga ${\displaystyle 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]

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 .