ICS 6B
Fall 2013
Homework 5

Due: Wednesday, Nov 6

Covers Sections 3.1-3.2

1. Draw the arrow diagram and the matrix representation for the following relation on the set {1, 2, 3, 4}: R = { (1, 2), (3, 4), (2, 3), (2, 1), (3, 1) }.


2. For each of the relations below, answer the following three questions:
   1. Is the relation reflexive, anit-reflexive or neither?
   2. Is the relation symmetric, anti-symmetric or neither?
   3. Is the relation transitive?
   If the relation does not have one of the properties, give and example illustrating this.
   1. The domain is a set of people. (x, y) is in the relation if person x is taller than person y.
   2. The domain is a set of people. (x, y) is in the relation if person x is a first cousin of person y (i.e., a parent of person x is a sibling of a parent of person y.
   3. The domain is a set of UCI students. (x, y) is in the relation if person x knows the student ID number for person y. You can assume that every student knows his or her own student ID number.
   4. The domain is the set of real numbers. (x, y) is in the relation if x + y = 0.
   5. The domain is the set of real numbers. (x, y) is in the relation if x = 2y.
   6. The domain is the set of real numbers. (x, y) is in the relation if x - y is a rational number.
   7. The domain is the set of real numbers. (x, y) is in the relation if x ≠ y.
   8. The domain is A = {a, b, c, d}. The relation is {(a,b), (a, a), (b, b), (b, a), (c, d), (d, c) }


3. Give an example of a relation on the set {1, 2, 3} that is neither reflexive nor anti-reflexive.


4. Is it possible to have a relation on a set that is symmetric and anti-symmetric? If so, give an example.


5. Here are two relations on the set {a, b, c, d}:
   • S = { (a, b), (a, c), (c, d), (c, a) }
   • R = { (b, c), (c, b), (a, d), (d, b) }
   Write down the set of pairs in S ο R.


6. Define the following relations on the set R:
   • R₁ = { (x, y): x ≤ y }
   • R₂ = { (x, y): x > y }
   • R₃ = { (x, y): x < y }
   • R₄ = { (x, y): x = y }
   Use mathematical notation to describe the following relations:
   1. R₁ ο R₂
   2. R₄ ο R₂
   3. R₃ ο R₄
   4. R₃ ο R₂


7. The diagram below shows a directed graph G:
   
   
   1. Is (a, b) in G²?
   2. Is (b, e) in G³?
   3. Is (g, g) in G³?
   4. Is (g, g) in G⁴?
   5. Is (b, b) in G³?
   6. Is (b, d) in G⁵?


8. Draw a picture of G+ for each of the digraphs below:
   
   


9. Consider a digraph G in which each vertex has in-degree at least one. Suppose that the relation defined by the edges of G is symmetric. Is G⁺ reflexive? Why or why not?