Arunkumar Khannur's Software Testing Knowledge Center

11.7 Graph, Relations and Properties of Relations

A graph is a set of nodes and links connecting some (possibly empty) subset of those nodes. Notationally it is represented as aRb where a, b are nodes andRis link representing a relation if a with b. It is also possible to associate one or more properties with relations which are termed as link weights. The following sections explain some properties of relations which are useful.

11.7.1 Transitive Property
A relation R, is said to be transitive if aRb and bRc then aRc.
For example, if Ram 'is the brother of' Laxman and Laxman 'is the brother of' Bharat then Ram 'is the brother of' Bharat.

11.7.2 Reflexive Property

A relation R is said to be reflexive if every node a is related to itself, that is,
aRa. Reflexive relation is equivalent to self-loop at every node.
For example, 3 is a multiple of' 3.

11.7.3 Symmetric Property

A relation R is symmetric if for every node a and node b, aRb implies bRa For example, if Mary 'is the sister of' Lucy, then Lucy 'is the sister of' Mary.

11.7.4 Equivalence Relation

If a relation is (i) reflexive, (ii) transitive and, (iii) symmetric, then it is called an equivalence relation.

11.7.5 Antisymmetric Relation

A relation R is Antisymmetric if for every a and b, if aRb and bRa, then a=b, or they are the same elements.

11.7.6 Partial Ordering Relation
If a relation is (i) reflexive, (ii) transitive and, (iii) antisymmetric, then it is called as partial ordering relation.
Khannur's Book
Arunkumar Khannur, Software Testing - Techniques and Applications, Published by Pearson Publications, 2011 (ISBN:978-81-317-5836-6; Pages:341 + xxii)
Follow Khannur
Khannur's Company
ISQT Process & Consulting Services Pvt. Ltd., Bangalore, INDIA
Khannur's Software Testing Forum
 Contact Khannur
ISQT Process & Consulting Services Pvt. Ltd.
#732, 1st Floor, 12th Main,
3rd Block, Rajajinagar,
Bangalore - 560010, INDIA
Phone: +91 80 23012511
Skype: arun.isqt