For each of the following relations R on the set A = {1,2,3,4}, find the matrix representing R and draw the directed graph corresponding to R.
(i) R = {(1,2), (2,3), (2,4), (3,1), (3,2), (4,1), (4,4)}
(ii) R = {(a,b): a2 + b2 > 10}
(iii) R = {(a,b): a - b < 0}
2. Given the following relations R on the set of non-negative integers, test whether R satisfies each of the properties of an equivalence relation.
(i) R = {(a,b): a -b is divisible by 4}
(ii) R = {(a,b): a + 2b is divisible by 3}
3. Find the equivalence classes for each of the following equivalence relations R on the given sets A:
(i) R = {(a,b): a≡b mod 5}, where A is the set of non-negative integers;
(ii) R = {(1,1), (1,3), (1,5), (3,3), (3,1), (3,5), (5,1), (5,3), (5,5), (2,2),
(2,6), (6,2), (6,6), (4,4)}, where A = {1,2,3,4,5,6}
4. The draw for the next soccer season has just been released. There are 6 teams in the competition and in the first 3 rounds the following teams have been drawn to play each other.
Team A plays Team C (home), Team F (away) and Team D (home).
Team B plays Team F (away), Team E (home) and Team C (away).
Team C plays Team A (away), Team D (home) and Team B (home).
Team D plays Team E (home), Team C (away) and Team A (away).
Team E plays Team D (away), Team B (away) and Team F (home).
Team F plays Team B (home), Team A (home) and Team E (away).Construct an adjacency matrix and draw a directed graph to represent the first three rounds of the draw. Use the directions on the graph to indicate which team is playing at home.
5. (i) Draw the following graphs:
K6 K3,3 C4 W4
(ii) Verify that the Handshaking Theorem holds for K3,3.
6. Draw the graphs on 4 vertices a,b,c,d whose adjacency matrices are:
(i) A =
0 0 0 1
1 1 1 0
1 0 1 0
0 1 1 0
(ii) B =
1 0 1 1
2 0 1 3
0 0 3 1
2 1 2 1
7. Find the number of paths of length 2 and length 3 from vertex c to vertex c for each of the graphs in Question 6.
8. Given the undirected graph G:
(i) Construct a simple path of length 9 from a to i;
(ii) Draw the subgraph of G containing only the vertices {b,d,e,h} and determine whether this subgraph is isomorphic to any of K4, K2,2 or K1,3.