ELEN500 Homework 2 Solution

2a. Draw the graph with vertices V = {A,B,C,D,E,F,G,H} and edges E ={(A,B), (A,C), (B,H), (C,B), (C,F), (D,B), (D,E), (F,H), (G,A), (G,F)}.

2b. Is the graph a DAG? Yes the graph is a Directed Acyclic Graph (DAG) since it contains no cycles.
2c. What, if any, are the source vertices? D and G are source vertices since they only have edges leading out of the vertex and no edges leading into them.
2d. What, if any are the sink vertices? E and H are sink vertices since they only have edges leading into them and no edges leading out.
2e. What is the longest path?

G - A - C - F - H and G - A - C - B - H 
each have 5 vertices and 4 edges and 
are the longest in this graph.

3. Problem 9 Page 111. A = {a, b, c} R = {(a,a), (b,b), (c,c), (a,b), (b,a)} The equivalence class of a, denoted by the symbol [a], consists of all the elements in A which are related to a by the relation R. [a] = {a,b}

4. Problem 12 Page 111. For x and y positive integers, P, define a relationship R such that x?? y iff x.y=60.
4a. Is R reflexive. NO R is reflexive if xRx for every x in P. That means xx = 60 for every x in P. We can show that this is NOT true by one counterexample. Let x = 5, then xx=25.
4b. Is R symmetric? YES. R is symmetric if xRy implies that yRx for every (x,y) in R. Since the positive integers are commutative, ie xy = yx for every x,y in P, we have xy = 60 which implies that yx = 60 for every x,y in P. Therefore R is symmetric.
4c. Is R antisymmetric? NO. R is antisymmetric if xRy and yRx implies x = y. We can show that R is not antisymmetric by counterexample. Let x = 3 and y = 20. Then xy = yx = 60 but x is not equal to y.
4d. Is R transitive? NO R is transitive if xRy and yRz implies that xRz. We can show that R is not transitive by counterexample. Let x = 3, y=20, and z=3. xy = 60 and yz=60, but xz = 9 not 60.
4e. Is R a partial order? NO. R is a partial order if it is reflexive, antisymmetric, and transitive. From parts a, c, and d we have shown that these properties do not hold true.
4f. Is R an equivalence relation? NO R is a equivalence relation if R is reflexive, symmetric and transitive. Since it is not reflexive or transitive it cannot be an equivalence relation.
4g. Is R a function?

 YES

R = {(1,60), (2,30), (3,20), (4,15), (5,12), (6,10), (10,6), (12,5), (15,4), (20,3), (30,2) (60,1)}

A function is a special type of relatiion in which the second member of an ordered pair is uniquely
determined by the first member.  The enumeration above of all elements of R allows us to conclude
that R is a function by inspection of all ordered pairs.

The Domain and Range of the function R = {1,2,3,4,5,6,10,12,15,20,30,60}
--- OR 
NO it is not a function if we consider the Domain and Range all integers,
because there are some values (eg 7) in the Domain that have no associated values
in the range!!!!

5. Definition a=b (mod5) if (a-b) = 5k for some integer k.

5a. Show that congruence mod5 is an equivalence relation over the set of integers.

i.  reflexive:  a = a (mod 5) if there exists an integer k such that a - a = 5k.  Solving the
integer equation for k, we get k=0.

ii.  symmetric:  a = b (mod 5) implies that a-b = 5k.  Since we are dealing with integers, multiply
both sides of this equation by -1 to obtain b-a = 5 (-k).  Hence b=a (mod 5).

iii.  transitive:  a = b (mod 5) implies that a-b=5k for some integer k.
                   b = c (mod 5) implies that b-c=5n for some integer n.
                   a-b+b-c = (a-b) + (b-c) = 5k + 5n = 5(k+n)  k+n is an integer since the 
integers are closed under addition, hence a=c(mod5).

5b. There are 5 equivalence classes. They form a partition on the set of integers.

[0] = {...-15, -10, -5, 0, 5, 10, 15, ...}
[1] = {...-14,  -9, -4, 1, 6, 11, 16, ...}
[2] = {...-13,  -8, -3, 2, 7, 12, 17, ...}
[3] = {...-12,  -7, -2, 3, 8, 13, 18, ...}
[4] = {...-11,  -6, -1, 4, 9, 14, 19, ...}