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

A set of vocabulary flashcards defining key terms related to binary relations and graph theory, including undirected and directed graph properties.

Relation

A set of pairs where the first component of each pair is chosen from a set called the domain, and the second component is chosen from a set called the range.

Domain

The set from which the first component of each pair in a relation is chosen.

Range

The set from which the second component of each pair in a relation is chosen.

$$R \subseteq A \times B$$

A relation $R$ from set $A$ to set $B$ is a subset of the Cartesian product of $A$ and $B$.

$$aRb$$

The notation used to say that the pair $(a,b)$ is an element of the relation $R$, denoted as $(a,b) \in R$.

Undirected graph

A graph denoted by $G= (V,E)$ that consists of a set of points with lines connecting some of the points.

Nodes or vertices ($V$)

The points that make up an undirected or directed graph.

Edges ($E$)

The lines connecting nodes in an undirected graph or the set of ordered pairs in a directed graph.

Degree

The number of edges at a particular node in an undirected graph.

Directed Graph (digraph)

A graph denoted as $G= (V,E)$ consisting of a finite set of vertices $V$ and a set of ordered pairs of vertices called edges $E$, represented by arrows.

Outdegree

The number of arrows pointing from a particular node in a directed graph.

Indegree

The number of arrows pointing to a particular node in a directed graph.

$$A \times B$$

The symbol used for the Cartesian product of sets $A$ and $B$.