Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Hasse diagram
(section)
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
{{Short description|Visual depiction of a partially ordered set}} {{confuse|Hess diagram}} [[File:Lattice of the divisibility of 60.svg|thumb|A Hasse diagram of the [[divisor|factor]]s of 60 ordered by the ''is-a-[[divisor]]-of'' relation]] In [[order theory]], a '''Hasse diagram''' ({{IPAc-en|Λ|h|Γ¦|s|Ι}}; {{IPA|de|ΛhasΙ|lang}}) is a type of [[mathematical diagram]] used to represent a finite [[partially ordered set]], in the form of a [[Graph drawing|drawing]] of its [[transitive reduction]]. Concretely, for a partially ordered set <math>(S,\le)</math> one represents each element of <math>S</math> as a [[vertex (graph theory)|vertex]] in the plane and draws a [[line segment]] or curve that goes ''upward'' from one vertex <math>x</math> to another vertex <math>y</math> whenever <math>y</math> [[Covering relation|covers]] <math>x</math> (that is, whenever <math>x\ne y</math>, <math>x\le y</math> and there is no <math>z</math> distinct from <math>x</math> and <math>y</math> with <math>x\le z\le y</math>). These curves may cross each other but must not touch any vertices other than their endpoints. Such a diagram, with labeled vertices, uniquely determines its partial order. Hasse diagrams are named after [[Helmut Hasse]] (1898β1979); according to [[Garrett Birkhoff]], they are so called because of the effective use Hasse made of them.{{sfnp|Birkhoff|1948}} However, Hasse was not the first to use these diagrams. One example that predates Hasse can be found in an 1895 work by Henri Gustave Vogt.{{sfnp|Vogt|1895}}{{sfnp|Rival|1985|p=110}} Although Hasse diagrams were originally devised as a technique for making drawings of partially ordered sets by hand, they have more recently been created automatically using [[graph drawing]] techniques.<ref>E.g., see {{harvtxt|Di Battista|Tamassia|1988}} and {{harvtxt|Freese|2004}}.</ref> In some sources, the phrase "Hasse diagram" has a different meaning: the [[directed acyclic graph]] obtained from the covering relation of a partially ordered set, independently of any drawing of that graph.<ref>For examples of this alternative meaning of Hasse diagrams, see {{harvtxt|Christofides|1975|pp=170β174}}; {{harvtxt|Thulasiraman|Swamy|1992}}; {{harvtxt|Bang-Jensen|2008}}</ref>
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)