| << Chapter < Page | Chapter >> Page > |
1, 3, 5, 2, 1 is a simple elementary cycle but not directed, and
2, 4, 5, 2 is a simple elementary directed cycle.
This digraph is connected.
Sometimes we need to refer to part of a given digraph. A partial digraph of a digraph is a digraph consisting of arbitrary numbers of vertices and arcs of the given digraph, while a subdigraph is a digraph consisting of an arbitrary number of vertices and all the arcs between them of the given digraph. Formally they are defined as follows: Definition (subdigraph, partial digraph): Let G = (V, A ) be a digraph. Then a digraph ( V', A' ) is a partial digraph of G , if V' ⊆V , and A' ⊆A ∩( V' ×V' ) . It is a subdigraph of G , if V' ⊆V , and A' = A ∩ ( V'×V' )
A partial digraph and a subdigraph of G3 given above are shown in Figure 4.
Certain important types of binary relation can be characterized by properties they have. Here we are going to learn some of those properties binary relations may have. The relations we are interested in here are binary relations on a set.
Definition(reflexive relation): A relation R on a set A is called reflexive if and only if<a, a>∈R for every element a of A.
Example 1: The relation ≤ on the set of integers {1, 2, 3} is {<1, 1>,<1, 2>,<1, 3>,<2, 2>,<2, 3>,<3, 3>} and it is reflexive because<1, 1>,<2, 2>,<3, 3>are in this relation. As a matter of fact ≤ on any set of numbers is also reflexive. Similarly ≥ and = on any set of numbers are reflexive. However,<(or>) on any set of numbers is not reflexive.
Example 2: The relation ⊆on the set of subsets of {1, 2} is {<∅, ∅>,<∅, {1}>,<∅, {2}>,<∅, {1, 2}>,<{1} , {1}>,<{1} , {1, 2}>,<{2} , {2}>,<{2} , {1, 2}>,<{1, 2} , {1, 2}>} and it is reflexive. In fact relation ⊆ on any collection of sets is reflexive.
Definition(irreflexive relation): A relation R on a set A is called irreflexive if and only if<a, a>∉ R for every element a of A.
Example 3: The relation>(or<) on the set of integers {1, 2, 3} is irreflexive. In fact it is irreflexive for any set of numbers.
Example 4: The relation {<1, 1>,<1, 2>,<1, 3>,<2, 3>,<3, 3>} on the set of integers {1, 2, 3} is neither reflexive nor irreflexive.
Definition(symmetric relation): A relation R on a set A is called symmetric if and only if for any a, and b in A, whenever<a, b>∈R ,<b, a>∈R .
Example 5: The relation = on the set of integers {1, 2, 3} is {<1, 1>,<2, 2><3, 3>} and it is symmetric. Similarly = on any set of numbers is symmetric. However,<(or>), ≤ (or ≥ on any set of numbers is not symmetric.
Example 6: The relation "being acquainted with" on a set of people is symmetric.
Definition (antisymmetric relation): A relation R on a set A is called antisymmetric if and only if for any a, and b in A, whenever<a, b>∈R , and<b, a>∈R , a = b must hold. Equivalently, R is antisymmetric if and only if whenever<a, b>∈R , and a ≠ b ,<b, a>∉ R . Thus in an antisymmetric relation no pair of elements are related to each other.
Example 7: The relation<(or>) on any set of numbers is antisymmetric. So is the equality relation on any set of numbers.
Notification Switch
Would you like to follow the 'Discrete structures' conversation and receive update notifications?
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|