Saturday, April 7, 2012

Binary relations

The reachability condition on a directed graph is reflexive and transitive so it produces a preorder. Symmetric preorders are equivalence relations and antisymmetric preorders are partial orders. Equivalence relations are partially ordered in terms of fineness and coarseness.

Parthood relations form a partial order. In particular, parthood relations are often hierarchical in nature so they can be modelled by undirected trees or polytrees.

Many to one relations:
Many to one relations induce an equivalence relation whose equivalence classes are the many part of the relation. Many to one relations are strong simplification rules for equivalence relations.

No comments:

Post a Comment