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 the matrix $M$ below, what does the directed graph with adjacency matrix $M$ look like?

$M=\begin{pmatrix} 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{pmatrix}.$

Let $G$ be the graph pictured below.

The code for drawing this graph in graphviz is:

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

Given the graph $G$ , is its adjacency matrix?
What is the in-degree and out-degree of $e$ ?
What is the longest cycle in $G$ , give your answer as a sequence of vertices?
Draw $G^2$ , $G^3$ , and the transitive closure $G^+$ of $G$ .