Offensive Security Researcher & Quantum Cryptography Analyst

Comprehensive Guide to Sets, Relations, Functions, Graphs, and Trees in Discrete Mathematics

Abdul Wahab Junaid
Comprehensive Guide to Sets, Relations, Functions, Graphs, and Trees

I treat sets, relations, functions, graphs, and trees as the backbone vocabulary of discrete mathematics. I use sets to group objects, relations to connect them, functions to map between them, graphs to model networks of connections, and trees as a special, hierarchical case of graphs. I find that nearly every data structure and algorithm I encounter in computer science rests on one or more of these five concepts, which is why I consider them foundational rather than optional theory.

History and Background

I trace set theory to Georg Cantor’s work in the 1870s, where he formalized the notion of infinite sets and cardinality, sparking both a mathematical revolution and philosophical controversy. I see relations and functions formalized alongside set theory, especially through the work of Giuseppe Peano and later the Bourbaki group, who grounded functions as special sets of ordered pairs. Graph theory, I note, began with Leonhard Euler’s 1736 solution to the Seven Bridges of Königsberg problem, widely regarded as the founding result of the field. Tree structures emerged from both graph theory and Arthur Cayley’s 1857 work counting tree structures related to chemical isomers, and later became a core structure in computer science through the development of data structures in the mid-20th century.

Problem Statement

I use these structures to solve the general problem of representing and reasoning about collections of objects and their relationships. Sets let me answer “what belongs together?” Relations let me answer “how are these objects connected?” Functions let me answer “what does this input map to?” Graphs let me model arbitrary networks (social networks, road maps, dependency graphs), and trees let me model strictly hierarchical relationships (file systems, organizational charts, decision processes) efficiently.

Core Concepts

Sets: I define a set as an unordered collection of distinct elements, denoted $A = {1, 2, 3}$. I use operations like union ($\cup$), intersection ($\cap$), difference ($-$), and complement.

Relations: I define a relation $R$ between sets $A$ and $B$ as a subset of $A \times B$. I classify relations by properties: reflexive, symmetric, antisymmetric, and transitive. A relation that is reflexive, symmetric, and transitive is an equivalence relation.

Functions: I define a function $f: A \to B$ as a relation where every element of $A$ maps to exactly one element of $B$. I classify functions as injective (one-to-one), surjective (onto), or bijective (both).

Graphs: I define a graph $G = (V, E)$ as a set of vertices $V$ and edges $E$ connecting pairs of vertices. I distinguish directed vs undirected, weighted vs unweighted, and cyclic vs acyclic graphs.

Trees: I define a tree as a connected, acyclic graph. I use terms like root, parent, child, leaf, depth, and height to describe tree structure.

How It Works

I approach problems in this domain through a consistent process:

  1. I identify which structure best models my problem (set membership, pairwise relationship, mapping, network, or hierarchy).
  2. For sets, I determine which operations (union, intersection, etc.) answer my question.
  3. For relations, I check the defining properties (reflexivity, symmetry, transitivity) to classify the relation.
  4. For functions, I verify whether the mapping is well-defined and check injectivity/surjectivity.
  5. For graphs, I choose a representation (adjacency matrix or list) and apply a traversal or search algorithm (BFS, DFS).
  6. For trees, I apply recursive algorithms that exploit the hierarchical, acyclic structure (traversals, balancing, searching).

Working Principle

I understand the internal logic of these structures as being built on top of one another: a relation is fundamentally a subset of a Cartesian product (itself built from sets), a function is a constrained relation, and a graph is a generalized relation visualized as vertices and edges. A tree is a graph with the additional constraint of connectivity and acyclicity, which gives it the property that there exists exactly one path between any two nodes. I rely on this nested structure whenever I reason about correctness — properties proven for general relations often specialize cleanly to functions, and properties proven for general graphs often specialize to trees.

Mathematical Foundation

I define set cardinality using the inclusion-exclusion principle for two sets:

$$ |A \cup B| = |A| + |B| – |A \cap B| $$

I define a relation’s transitive closure $R^+$ as the smallest transitive relation containing $R$, computed as:

$$ R^+ = \bigcup_{k=1}^{\infty} R^k $$

I define function composition for $f: A \to B$ and $g: B \to C$ as:

$$ (g \circ f)(x) = g(f(x)) $$

I state the Handshaking Lemma for graphs:

$$ \sum_{v \in V} \deg(v) = 2|E| $$

I define a tree with $n$ vertices as having exactly:

$$ |E| = n – 1 $$

edges, which I prove by induction: a single-vertex tree has 0 edges ($n-1 = 0$), and adding any new vertex to a tree must add exactly one edge to preserve connectivity without creating a cycle, so if a tree with $k$ vertices has $k-1$ edges, a tree with $k+1$ vertices has $k$ edges.

I define the height $h$ of a balanced binary tree with $n$ nodes as bounded by:

$$ h = \lceil \log_2(n+1) \rceil – 1 $$

Diagrams

flowchart TD
    A[Problem: Model relationships between objects] --> B{What kind of structure?}
    B -->|Grouping objects| C[Use Sets]
    B -->|Pairwise connection| D[Use Relations]
    B -->|Input to output mapping| E[Use Functions]
    B -->|Arbitrary network| F[Use Graphs]
    F --> G{Connected and Acyclic?}
    G -->|Yes| H[Special case: Tree]
    G -->|No| I[General Graph]

Pseudocode

I write pseudocode for a breadth-first traversal of a tree, which I use to process nodes level by level:

function BFS_TREE(root):
    if root is null:
        return

    queue = new empty queue
    enqueue(queue, root)

    while queue is not empty:
        node = dequeue(queue)
        visit(node)

        for each child in node.children:
            enqueue(queue, child)

Step-by-Step Example

I demonstrate with a small binary tree:

        1
       / \
      2   3
     / \
    4   5

I perform a breadth-first traversal:

  1. I enqueue node 1, then dequeue and visit it. I enqueue its children, 2 and 3.
  2. I dequeue and visit 2. I enqueue its children, 4 and 5.
  3. I dequeue and visit 3. It has no children.
  4. I dequeue and visit 4. It has no children.
  5. I dequeue and visit 5. It has no children.

I record the traversal order as: 1, 2, 3, 4, 5.

Time Complexity

I analyze breadth-first traversal of a tree with $n$ nodes as $O(n)$ in the best, average, and worst case, since I visit every node exactly once and perform $O(1)$ work enqueuing/dequeuing each. For general graph traversal (BFS/DFS) using an adjacency list, I get $O(V + E)$, where $V$ is the number of vertices and $E$ the number of edges, since I visit each vertex once and examine each edge once. Set operations like union and intersection run in $O(|A| + |B|)$ when implemented with hash-based sets, or $O(|A| \log|A| + |B| \log |B|)$ with sorted/tree-based sets.

Space Complexity

I require $O(V)$ space for the queue in BFS in the worst case (a wide tree/graph where most nodes are at the same level), and $O(h)$ space for DFS recursion, where $h$ is the height of the tree/graph (representing the maximum call stack depth). For representing a graph, I need $O(V^2)$ space with an adjacency matrix or $O(V + E)$ space with an adjacency list, which I prefer for sparse graphs.

Correctness Analysis

I justify BFS correctness by induction on levels: I assume all nodes at depth $d$ are correctly enqueued before processing begins on depth $d+1$, and I show that since I only enqueue a node’s children after visiting the node itself, all nodes at depth $d$ are dequeued (and their children enqueued) before any node at depth $d+1$ is dequeued, preserving level-order correctness. I justify the tree edge-count identity ($|E| = n – 1$) by structural induction, as shown in the Mathematical Foundation section. I justify equivalence relation partitioning by showing that reflexivity, symmetry, and transitivity together guarantee that the equivalence classes I generate are disjoint and their union is the entire set.

Advantages

Disadvantages

Applications

I apply these concepts in:

Implementation in C

I implement a simple binary tree with BFS traversal, with comments:

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

// I create a new tree node with given data
Node* createNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

// I implement a simple queue using an array for BFS
#define MAX_QUEUE 100

void bfsTraversal(Node* root) {
    if (root == NULL) return;

    Node* queue[MAX_QUEUE];
    int front = 0, rear = 0;

    queue[rear++] = root;

    while (front < rear) {
        Node* current = queue[front++];
        printf("%d ", current->data); // I visit the node

        if (current->left != NULL) queue[rear++] = current->left;
        if (current->right != NULL) queue[rear++] = current->right;
    }
    printf("\n");
}

int main() {
    // I build the sample tree from the walkthrough
    Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    printf("BFS traversal: ");
    bfsTraversal(root);

    return 0;
}

Sample Input and Output

I build the tree shown in the step-by-step example directly in code (no external input needed), and I expect this output:

BFS traversal: 1 2 3 4 5

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version