Recitation 11: Relations and Directed Graphs
Part 1: Relations
- Consider the set of students
![S = \{\text{Jim}, \text{John}, \text{Mary}, \text{Beth}\} S = \{\text{Jim}, \text{John}, \text{Mary}, \text{Beth}\}](https://latex.codecogs.com/png.latex?S%20%3D%20%5C%7B%5Ctext%7BJim%7D%2C%20%5Ctext%7BJohn%7D%2C%20%5Ctext%7BMary%7D%2C%20%5Ctext%7BBeth%7D%5C%7D)
- and the set of colors
![C = \{\text{Red}, \text{Blue}, \text{Green}, \text{Purple}, \text{Black}\} C = \{\text{Red}, \text{Blue}, \text{Green}, \text{Purple}, \text{Black}\}](https://latex.codecogs.com/png.latex?C%20%3D%20%5C%7B%5Ctext%7BRed%7D%2C%20%5Ctext%7BBlue%7D%2C%20%5Ctext%7BGreen%7D%2C%20%5Ctext%7BPurple%7D%2C%20%5Ctext%7BBlack%7D%5C%7D)
- 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
be the relation between the students and the color of shirt they are wearing.
- What would the matrix representation of
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} \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}](https://latex.codecogs.com/png.latex?%5Cbegin%7Bbmatrix%7D%201%20%26%200%20%26%200%20%26%200%20%26%200%20%26%200%20%5C%5C%201%20%26%201%20%26%201%20%26%201%20%26%201%20%26%200%20%5C%5C%200%20%26%200%20%26%200%20%26%200%20%26%200%20%26%201%20%5C%5C%200%20%26%201%20%26%200%20%26%201%20%26%200%20%26%201%20%5C%5C%200%20%26%200%20%26%200%20%26%201%20%26%200%20%26%200%20%5C%5C%201%20%26%201%20%26%200%20%26%201%20%26%201%20%26%201%20%5Cend%7Bbmatrix%7D)
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
?
- What is the longest cycle in this graph?
- Draw
,
, and the transitive closure of this graph.