Recitation 11: 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.
Change the engine from “dot” to “circo” to help with displaying these graphs
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.