Notes/Discrete Structures/Relations and Digraphs.md

---
type: theoretical
---

## Partitions and Cartesian Products

### Cartesian Product

The *Cartesian product* of two sets $A$ and $B$ is the set of all ordered pairs where the first element is from $A$ and the second is from $B$:

$$
A \times B = \{ (a, b) \mid a \in A, \, b \in B \}
$$

- If $A = \{1, 2\}$ and $B = \{x, y\}$, then:

$$
A \times B = \{ (1, x), (1, y), (2, x), (2, y) \}
$$

[^1]: The Cartesian product creates pairs from all possible combinations of elements from two sets.

### Partitions

A partition of a set $S$ is a collection of non-empty, disjoint subsets $\{S_1, S_2, \dots, S_n\}$ such that:

- $S = S_1 \cup S_2 \cup \dots \cup S_n$
- $S_i \neq \emptyset$ for all $i$
- $S_i \cap S_j = \emptyset$ for all $i \neq j$

[^2]: Partitions divide a set into disjoint subsets that cover the entire set.

- A partition of $S = \{1, 2, 3, 4\}$ could be $\{\{1, 2\}, \{3, 4\}\}$.

---

## Binary Relations

A binary relation $R$ from set $A$ to set $B$ is a subset of the Cartesian product $A \times B$:

$$
R \subseteq A \times B
$$

- When $A = B$, $R$ is a relation on $A$.

### Representations of Relations

#### As [Sets](Mathematical%20Data%20Structures.md)

A relation can be represented as a set of ordered pairs.

-  $R = \{ (1, 2), (2, 3), (3, 1) \}$

#### As [Matrices](Matrices.md)

For a finite set $A = \{a_1, a_2, \dots, a_n\}$, the relation matrix $M_R$ is an $n \times n$ matrix where:

$$
(M_R)_{ij} =
\begin{cases}
1, & \text{if } (a_i, a_j) \in R \\
0, & \text{otherwise}
\end{cases}
$$

#### As [Graphs](Graphs.md)

A digraph (directed graph) represents elements as vertices and relations as directed edges.

- For $R = \{ (1, 2), (2, 3) \}$, draw vertices for 1, 2, 3, with edges from 1 to 2 and 2 to 3.

---

## Properties of Relations

### Reflexive

A relation $R$ on set $A$ is *reflexive* if every element is related to itself:

$$
\forall a \in A, \, (a, a) \in R
$$

### Symmetric

$R$ is *symmetric* if:

$$
\forall a, b \in A, \, (a, b) \in R \implies (b, a) \in R
$$

### Antisymmetric

$R$ is *antisymmetric* if:

$$
\forall a, b \in A, \, (a, b) \in R \land (b, a) \in R \implies a = b
$$

### Transitive

$R$ is *transitive* if:

$$
\forall a, b, c \in A, \, (a, b) \in R \land (b, c) \in R \implies (a, c) \in R
$$

### Equivalence Relations

A relation that is *reflexive*, *symmetric*, and *transitive* is an ***equivalence*** relation.

- An equivalence relation partitions the set into equivalence classes.

[^3]: Equivalence relations naturally partition a set into equivalence classes, grouping related elements.

- For $a \in A$, **the equivalence class** $[a]$ is:

$$
[a] = \{ x \in A \mid (a, x) \in R \}
$$

- The set of all equivalence classes forms a partition of $A$.

---

## Operations on Relations

### Union

The union of two relations $R$ and $S$ on $A$:

$$
R \cup S = \{ (a, b) \mid (a, b) \in R \text{ or } (a, b) \in S \}
$$
Unions are used in [Kruskall Algorithm's Union-Find](Graph%20Algorithms.md)
### Intersection

The intersection of $R$ and $S$:

$$
R \cap S = \{ (a, b) \mid (a, b) \in R \text{ and } (a, b) \in S \}
$$

### Composition

The composition of relations $R$ and $S$ is:

$$
R \circ S = \{ (a, c) \mid \exists b \in A, \, (a, b) \in R \text{ and } (b, c) \in S \}
$$

---

## Algorithms

### Warshall's Algorithm

computes the transitive closure of a relation on a finite set.

- The smallest transitive relation $R^+$ that contains $R$ is called a **Transitive Closure**.
	- Determines reachability in graphs; whether there is a path from one vertex to another.

#### Steps of Warshall's Algorithm

Given the adjacency matrix $M$ of a relation $R$ on set $A = \{a_1, a_2, \dots, a_n\}$:

1. Initialize $T^{(0)} = M$.
2. For $k = 1$ to $n$:
   - For $i = 1$ to $n$:
     - For $j = 1$ to $n$:
       $$
       T_{ij}^{(k)} = T_{ij}^{(k-1)} \lor (T_{ik}^{(k-1)} \land T_{kj}^{(k-1)})
       $$
3. After $n$ iterations, $T^{(n)}$ is the transitive closure matrix.

---

[^1]: The Cartesian product creates pairs from all possible combinations of elements from two sets.

[^2]: Partitions divide a set into disjoint subsets that cover the entire set.

[^3]: Equivalence relations naturally partition a set into equivalence classes, grouping related elements.