Recitation 13: Relations and Directed Graphs

Part 1: Relations

Consider the set of students $S = \{\text{Jim}, \text{John}, \text{Mary}, \text{Beth}\}$
and the set of colors $C = \{\text{Red}, \text{Blue}, \text{Green}, \text{Purple}, \text{Black}\}$
Say that Jim is wearing a Red shirt, John is wearing a Black shirt, Mary is wearing a Purple shirt and Beth is wearing a Red shirt. Let $R$ be the relation between the students and the color of shirt they are wearing.
What would the matrix representation of $R$ be?
Is R transitive? What are some examples of transitive relations?

Part 2: Directed Graphs

Use this website to create images of graphs online.
Given this matrix representation, what would the directed graph look like?

$\begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 & 1 \end{bmatrix}$

The code for this graph is:

digraph G {
    a -> b
    b -> c
    b -> e
    e -> f
    f -> a
    c -> d
    c -> g
    e -> g
    e -> h
    f -> h
}

Given this graph, what would the matrix representation be?
What is the in-degree and out-degree of $e$ ?
What is the longest cycle in this graph?
Draw $G^2$ , $G^3$ , and the transitive closure of this graph.