Hasse diagrams
If we know that a relation is a partial order, then we can use a simplified representation rather than using a directed graph.
Example Diagram
For example, take the ‘divisibility’ relation on the set .
digraph G {
{
a [label="1"]
b [label="2"]
c [label="3"]
d [label="5"]
e [label="10"]
f [label="11"]
g [label="15"]
h [label="25"]
}
a->a
a->b
a->c
a->d
a->e
a->f
a->h
b->b
b->e
c->c
c->g
d->d
d->e
d->g
d->h
e->e
f->f
g->g
h->h
}As partial orders are always reflexive, a loop is always present at every point, so we can remove these loops without losing information:
digraph G {
{
a [label="1"]
b [label="2"]
c [label="3"]
d [label="5"]
e [label="10"]
f [label="11"]
g [label="15"]
h [label="25"]
}
a->b
a->c
a->d
a->e
a->f
a->h
b->e
c->g
d->e
d->g
d->h
}Partial orders are always transitive, so we don’t lose any information by only indicating ‘one-step’ arrows.
digraph G {
{
a [label="1"]
b [label="2"]
c [label="3"]
d [label="5"]
e [label="10"]
f [label="11"]
g [label="15"]
h [label="25"]
}
a->b
a->c
a->d
a->f
b->e
c->g
d->e
d->g
d->h
}Partial orders are also antisymmetric, which means that between any two points there can only be an arrow one way, not both. We can remove the arrows and ensure everything stems from bottom to top.
graph G {
rankdir = BT
{
a [label="1"]
b [label="2"]
c [label="3"]
d [label="5"]
e [label="10"]
f [label="11"]
g [label="15"]
h [label="25"]
}
a--b
a--c
a--d
a--f
b--e
c--g
d--e
d--g
d--h
} Example 2
The Hasse diagram of on the power set of :
graph G {
{
e [label="0"]
x [label="{x}"]
y [label="{y}"]
z [label="{z}"]
a [label="{x,y}"]
s [label="{y,z}"]
d [label="{x,z}"]
f [label="{x,y,z}"]
}
x,y,z--e
a--x,y
s--y,z
d--x,z
f--a,s,d
}