page1
Chapter 12 Relations – Directed Graphs
A relation R on set A is reflexive if (a,a)  R for every a  A.
A relation R on set A is anti-rreflexive if (a,a)  R for every a  A.
A relation R on set A is symmetric if (b,a)  R whenever (a,b)  R, for all a, b  A.
A relation R on set A is antisymmetric if whenever (b,a)  R and (a,b)  R, then a = b, for all a, b  A.
A relation R on set A is transitive if whenever (a,b)  R and (b,c)  R, then (a,c)  R , for all a, b  A.
The composition of relations R and S on set A is another relation on A, denoted S ο R. The pair (a, c) ∈ S ο R if and only if there is a b ∈ A such that (a, b) ∈ R and (b, c) ∈ S.
Let R be a relation on set A. The powers Rn , n=1,2,3,...
are defined recursively by R1 = R
Rn+1 = Rn ◦ R
Let R be a relation on a finite domain with n elements. Then R+ = R1 ∪ R2 ∪ R3 ∪....∪ Rn
is called the transitive closure of R and is the smallest relation that is both transitive and includes all the pairs from R.
If G is a directed graph, then G+ is called the transitive closure of G.
[Theorem] The Graph Power Theorem.
Let G be a directed graph. Let u and v be any two vertices in G. There is an edge from u to v in Gk iff there is a walk of length k from u to v in G.
A relation on a set A is called an equivalence relation if it is reflexive, symmetric and transitive.
Let R be an equivalence relation on a set A. The set of all elements that are related to an element a of A is called the equivalence class of a. denotation: [a]R equivalence class of a , or [a]
A relation R on a set S is called a partial ordering or partial order if it is reflexive, antisymmetric, and transitive. (S,R) is called a partially ordered set or poset.
The elements a and b of the poset (S,R) are called comparable if either aRb or bRa.
Otherwise they are called incomparable.
If (S,R) is a poset, and every two elements of S are comparable, then S is called a totally ordered or linearly ordered set, and R is called a total order or a linear order.
A totally ordered set is called a chain.
A relation R is a strict order if R is transitive and anti-reflexive. A strict order is a total order if every pair of elements is comparable.
a is maximal in the poset (S, R) if there is no b Î S such that a R b.
a is minimal in the poset (S, R) if there is no b Î S such that b R a.
The definition of the minimal/maximal elements for the strict order is similar.