Binary Relations and Graphs

	binrel

Binary Relations

	A binary relation is a set of ordered-pairs, with the elements of each pair drawn from a common set.
	Example: { [1, 2], [2, 3], [1, 3] }

Binary Relations

	(A binary relation is a set of ordered-pairs, with the elements of each pair drawn from a common set, called the domain.)
	A finite set can be implemented as a list.
	An ordered-pair can be represented as a list.
	Therefore, a finite binary relation can be represented as a list of lists of two elements each.

Example Binary Relation Implementation

	Consider the binary relation Òcan be donor forÓ on the domain of blood types: {ÒAÓ, ÒBÓ, ÒABÓ, ÒOÓ}
	As a list, this relation could be represented [[ÒAÓ, ÒAÓ], [ÒAÓ, ÒABÓ],  [ÒBÓ, ÒBÓ], [ÒBÓ, ÒABÓ],  [ÒABÓ, ÒABÓ],  [ÒOÓ, ÒAÓ], [ÒOÓ, ÒABÓ], [ÒOÓ, ÒBÓ], [ÒOÓ, ÒOÓ]]

Another Binary Relation Implementation

	With each first element of some pair, give the list of second elements to which the first element is related:
	[[ÒAÓ,   [ÒAÓ, ÒABÓ]],  [ÒBÓ,    [ÒBÓ, ÒABÓ],  [ÒABÓ, [ÒABÓ]],  [ÒOÓ,   [ÒOÓ, ÒAÓ, ÒBÓ, ÒABÓ]]
	Compare the two representations.

Directed Graphs

	A Directed Graph is a way of presenting a binary relation:
		The nodes (shapes) of a directed graph correspond to the elements in the domain.
		The arcs (arrows) of a directed graph correspond to the pairs that are related.

A Small Directed Graph Example

	For the binary relation can be donor for represented as a list previously [[ÒAÓ, ÒAÓ], [ÒAÓ, ÒABÓ], [ÒBÓ, ÒBÓ], [ÒBÓ, ÒABÓ], [ÒABÓ, ÒABÓ],  [ÒOÓ, ÒAÓ], [ÒOÓ, ÒABÓ], [ÒOÓ, ÒBÓ], [ÒOÓ, ÒOÓ]] the directed graph would be

A Large Directed Graph

	Each page in the world-wide web can be considered a node.
	Each hyper-link from one page to another is an arc.
	cf. graphics.stanford.edu/papers/webviz/

Properties of Binary Relations (1 of 2)

	The previous relation example illustrates two common properties that a binary relation may have:
		transitive property: For every x, y, z in the domain * if x is related to y and y is related to z, then x is related to z.
		reflexive property: For every x in the domain x is related to x.

Properties of Binary Relations (2 of 2)

	The previous example has only the second of the following additional two common properties:
		symmetric property: For every x, y in the domain if x is related to y then y is related to x.
		anti-symmetric property: For every x, y in the domain if x is related to y and y is related to x, then x = y.

Partial Orders

	A relation with the reflexive, anti-symmetric, and transitive properties is called a partial order.
	Example:

Equivalence Relations

	A relation with the reflexive, symmetric, and transitive properties is called an equivalence relation. Such a relation generalizes the notion of equality, since in this case if x is related to z and y is related to z, then x is related to y. In other words, if each of a set of elements is related to a common thing, the elements in the set and the common thing are all related to each other.

Example of an Equivalence Relation

	Consider the relation Òis a homophone ofÓ (Òsounds the same asÓ) on a set of words, such as {ÒairÓ, ÒereÓ, ÒheirÓ, ÒbuyÓ, ÒbyÓ, ÒbyeÓ, ÒdewÓ, ÒdoÓ, ÒdueÓ, ÒeweÓ, ÒyouÓ, ÒyewÓ}
		Reflexive: Every x is a homophone of x.
		Symmetric: If x is a homophone of y then y is a homophone of x.
		Transitive: If x is a homophone of y and y is a homophone of z, then x is a homophone of z.
	Therefore this is an equivalence relation.

Example of not an Equivalence Relation

	Consider the relation Òis a synonym forÓ (Òmeans the same asÓ)
		Reflexive: Every x is a synomym for x.
		Symmetric: If x is a synomym of y then y is a synomym of x.
		Transitive: NOT: If x is a synomym of y and y is a synomym of z, then x is a synomym of z. (Example: ÒangryÓ is a synonym for ÒmadÓ, and ÒmadÓ is a synonym for ÒinsaneÓ, but ÒangryÓ is not a synonym for ÒinsaneÓ.)
	Therefore this is a not an equivalence relation.

Undirected Graphs

	An undirected graph is a way of presenting a symmetric binary relation: Since whenever x is related to y also y is related to x, we donÕt have to show direction with arcs. Instead of calling them arcs then, it is common to call them edges.

Undirected Graph Example

	An example of a symmetric relation and its undirected graph is Òcan be a synonym ofÓ:

More Information Structures?

	There is a lot more to be said, and our next topic in this thread will be trees.
	But for now, we will discuss some ways to work with these representations in an actual language.