Module I Automata Theory and Formal Languages - Lesson 2: Relations and Graphs

A binary relation is categorized as a set of pairs.
The structure of a relation involves two primary components:
- Domain: This is the set from which the first component of each pair in the relation is chosen.
- Range: This is the set from which the second component of each pair in the relation is chosen.
Formal Definition:
- Let $A$ and $B$ be non-empty sets.
- A relation $R$ from $A$ to $B$ is defined as a subset of the Cartesian product $A \times B$ .
- This is mathematically expressed as $R \subseteq A \times B$ .
- In this specific context, $A$ serves as the domain and $B$ serves as the range.
Notation of Membership:
- If $R \subseteq A \times B$ and the pair $(a, b)$ is an element of $R$ ( $(a, b) \in R$ ), the relationship is written as $aRb$ .
- If the pair is not an element of the relation, it is noted that $a$ is not related to $b$ .
Relations on a Single Set:
- It is frequent for the sets $A$ and $B$ to be equal ( $A = B$ ).
- When $R \subseteq A \times A$ , it is referred to as a relation on $A$ .

Example 1: The "Less Than" Relation:
- Consider sets $A = \{1, 2, 3, 4, 5\}$ and $B = \{1, 2, 3, 4, 5\}$ .
- Define the relation $R$ (less than) on $A$ such that $aRb$ if and only if a < b.
- The resulting set is: $R = \{(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)\}$ .
- Logic: In the pair $(a, b)$ , $a$ represents elements in set $A$ and $b$ represents elements in set $B$ . For instance, $(1, 2)$ is valid because $1$ (from set $A$ ) is less than $2$ (from set $B$ ). This logic applies to every element in the set $R$ .
Example 2: The "Multiple Of" Relation:
- Let $A = \{1, 2, 3, 4, 6\}$ .
- Define the relation $R$ such that $aRb$ if and only if $b$ is a multiple of $a$ .
- The resulting set is: $R = \{(1, 1), (1, 2), (1, 3), (1, 4), (1, 6), (2, 2), (2, 4), (2, 6), (3, 3), (3, 6), (4, 4), (6, 6)\}$ .

An undirected graph (referred to simply as a graph) is denoted by $G = (V, E)$ .
Components of a Graph:
- Nodes or Vertices (V): These are the points within the graph.
- Edges (E): These are the lines that connect specific pairs of points.
Node Degree in Undirected Graphs:
- The degree of a node is defined as the total number of edges connected to that particular node.
- The order of vertices in an edge pair does not matter in an undirected graph (i.e., the pair $(i, j)$ is equivalent to $(j, i)$ ).
Formal Description Examples:
- Example Graph 1:
  - Description: $( \{1, 2, 3\}, \{ \{1, 2\}, \{2, 3\}, \{1, 3\} \} )$ .
  - Analysis: Every node has a degree of 2. Node 1 has edges to nodes 2 and 3; node 2 has edges to nodes 1 and 3; and node 3 has edges to nodes 1 and 2.
- Example Graph 2:
  - Description: $( \{1, 2, 3, 4\}, \{ \{1, 2\}, \{1, 3\}, \{1, 4\}, \{2, 3\}, \{2, 4\}, \{3, 4\} \} )$ .
  - Analysis: Nodes 1 and 4 possess a degree of 3. Nodes 2 and 3 possess a degree of 2.

A graph that utilizes arrows instead of simple lines to indicate direction is known as a directed graph, or digraph.
Formal Definition of a Digraph:
- A digraph is denoted as $G = (V, E)$ .
- It consists of a finite set of vertices $V$ .
- It contains a set of ordered pairs of vertices called edges $E$ .
Degrees in Directed Graphs:
- Outdegree: The total number of arrows (edges) pointing away from a specific node.
- Indegree: The total number of arrows (edges) pointing toward a specific node.
Digraph Example 1:
- Formal Description: $( \{1, 2, 3, 4, 5\}, \{(1, 2), (1, 3), (3, 4), (3, 5), (4, 2), (4, 3), (5, 4)\} )$ .
- Data points: The outdegree of node 5 is 1. The indegree of node 4 is 2.
Digraph Example 2: Relation to Digraph Mapping:
- Let sets $A = \{1, 2, 3, 4\}$ and $B = \{1, 2, 3, 4\}$ .
- Let the relation $R$ be defined as: $R = \{(1, 1), (1, 2), (2, 1), (2, 2), (2, 3), (2, 4), (3, 4), (4, 1)\}$ .
- This relation can be represented as a digraph where each ordered pair in $R$ constitutes a directed edge from the first element to the second element.