Lattice

A Lattice is a partially ordered set/directed graph in which any two elements have a unique supremum (top element) and an infimum (bottom element).

• Example(s):
  • a Tree Graph.
  • a Viterbi Lattice.
  • …
• Counter-Example(s):
  • an Undirected Graph.
  • a Cyclic Graph.
• See: Lattice Theory, Monotone Function, Viterbi Algorithm.

---

---

References

• Google Image Search: http://www.google.com/search?q=lattice+graph+edge+vertex&um=1&tbm=isch

2009

• http://en.wikipedia.org/wiki/Lattice_(order)
  • In mathematics, a lattice is a partially ordered set (also called a poset) in which any two elements have a unique supremum (the elements' least upper bound; called their join) and an infimum (greatest lower bound; called their meet). Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities. Since the two definitions are equivalent, lattice theory draws on both order theory and universal algebra. Semilattices include lattices, which in turn include Heyting and Boolean algebras. These "lattice-like" structures all admit order-theoretic as well as algebraic descriptions.

---