Relation properties in graphs

Reflexive relation All nodes have loops ReflexiveNot reflexiveReflexive

Symmetric relation If nodes are connected, they are connected in both directions Not symmetric Symmetric

Transitive relation Triangles, and not only Transitive ((a,b), (b,a), (a,a) R, (b,a), (a,b), (b,b) R) TransitiveNot transitive, ((a,b), (b,c) R, (a,c) R)

Relation properties in matrices

Reflexive relation Main diagonal has only 1 no 0 ReflexiveNot reflexiveReflexive

Symmetric relation Symmetric to main diagonal Not symmetric Symmetric

Transitive relation Almost impossible to see Transitive ((a,b), (b,a), (a,a) R, (b,a), (a,b), (b,b) R) TransitiveNot transitive, ((a,b), (b,c) R, (a,c) R)

Special types of relations

1: Equivalence relation and equivalence classes Definition. A relation R that is reflexive, symmetric and transitive is called an equivalence relation. Two elements that are related by an equivalence relation are called equivalent. An equivalence relation divides the given set into equivalence classes. Definition. 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. The equivalence class of a with respect to R is denoted by [a] R or [a]. 10

How to determine equivalence? (if relation is represented with matrix) 1) Marked all points on the main diagonal reflexivity 2) If a point is marked, there must be a symmetric point to this according to main diagonal symmetry Is this equivalence? 3) Matrix consists from squares which do not intersect by themselves and are grouped along main diagonal, each square correspond to one equivalence class No, because is not transitive (2,1) and (1,3) R, but (2,3) R 11

Example: Determine whether the relations represented by the following zero-one matrices are equivalence relations R R2R3 R1 is not equivalence relation is not reflexive, (3,3) R1 is not symmetric, (4,1) R1, but (1,4) R1 is not transitive, (3,1) and (1,2) R1, but (3,2) R1 Solution: R2 is equivalence relation is reflexive is symmetric is transitive R3 is not equivalence relation is reflexive is symmetric is not transitive, (1,2) and (2,4) R3, but (1,4) R3 12

Possible equivalence relations

Partial orderings

A relation R on a set S is called a partial ordering or partial order if it is reflexive, antisymmetric,and transitive. A set S together with a partial ordering R is called a partially ordered set (or poset), and is denoted by (S,R). Members of S are called elements of the poset.

Example: greater than or equal ( ) on integer set Solution: -Since a a for every integer a, is reflexive. -If a b and b a, then a = b. Hence, is antisymmetric. -Finally, is transitive since a b and b c imply that a c.

- total order

- Lexicographical order Is obtained by comparing two vectors. Comparison is established by components Fundamentals of dictionary When applied to subsets, two subsets are ordered by their smallest elements. For example, the subsets of {1, 2, 3} in lexicographic order are {}, {1}, {1,2}, {1,2,3}, {1,3}, {2},{2,3}, {3} A special case of an ordering of strings on a set constructed from a partial ordering on the set.