Paths, Reachability, and Connectivity

Graph theory provides the mathematical language to model connections, flows, and structural relationships across computer networks, physical infrastructures, and logical dependencies. This module explores how entities connect, how reachability is mathematically determined, and the structural properties that define robust network topologies.

1. Fundamentals of Graphs and Structural Relations

A graph $G$ is formally defined as an ordered pair:

$G = (V, E)$

where $V$ is a non-empty set of vertices (or nodes), and $E$ is a set of edges (or connections). A mapping function $\phi$ associates each edge in $E$ with a pair of vertices from $V$ .

text

    Undirected Edge                     Directed Edge
     (Bidirectional)                    (Unidirectional)
     
       u --------- v                      u ---------> v

Edge Properties and Classifications

Adjacent Nodes: Two nodes $u, v \in V$ are adjacent if they are directly connected by an edge $e \in E$ .
Directed vs. Undirected Edges:
- A directed edge (or arc) is defined by an ordered pair $(u, v)$ , representing a unidirectional link originating at $u$ and terminating at .

Structural Typologies

Simple Graph: A graph containing no loops and no parallel edges. In a directed simple graph, there is at most one directed edge from $u$ to $v$ .
Multigraph: A graph that permits parallel edges but no loops.
Null Graph: A graph containing only isolated nodes (vertices with a degree of zero) and no edges.
Isomorphism: Two graphs $G_1 = (V_1, E_1)$ and are () if there exists a bijective function: such that for any , if and only if . A is a property preserved under isomorphism, such as the vertex count, edge count, or degree sequence.

Degree Metrics

The degree of a vertex measures its local connectivity:

In an undirected graph, the degree $\text{deg}(v)$ is the number of edges incident to $v$ .
In a directed graph, we split this metric into:
- Indegree $\text{deg}^-(v)$ : The number of edges terminating at $v$ .
- Outdegree $\text{deg}^+(v)$ : The number of edges originating from .

Mathematical Relations on Simple Digraphs

For simple directed graphs, the edge set $E \subseteq V \times V$ can be analyzed as a binary relation on the set $V$ :

Reflexive: Every node contains a self-loop ( $\forall v \in V, (v, v) \in E$ ).
Symmetric: If $(u, v) \in E$ , then $(v, u) \in E$ (equivalent to an undirected graph).

The converse (or reversal/dual) of a digraph $G = (V, E)$ , denoted $G^T$ , is obtained by reversing the direction of every edge:

$E(G^T) = \{(v, u) \mid (u, v) \in E\}$

2. Paths, Cycles, and Geodesic Metrics

Evaluating how information traverses a graph requires formal distinctions between different types of node-edge sequences.

text

Walk (General sequence of nodes & edges)
  └─► Trail (No edge is repeated)
        └─► Simple Path (No vertex is repeated)

Types of Traversal Sequences

Walk (Path): A sequence of vertices and edges $v_0, e_1, v_1, e_2, \dots, e_k, v_k$ where each edge connects and . The of the walk is the number of edges, .

Geodesics and Distance Metrics

Geodesic: A path of minimum length between two vertices.
Distance $d(u, v)$ : The length of a geodesic from $u$ to $v$ . If no path exists, $d(u, v) = \infty$ .
Distance Properties:
1. Reflexivity: $d ($ .

3. Reachability and Node Bases

Reachability is a binary relation: a vertex $v$ is reachable from $u$ (denoted $u \to^* v$ ) if there exists a directed path starting at $u$ and terminating at $v$ . Reachability is reflexive (via a path of length 0) and transitive, but not necessarily symmetric or antisymmetric.

Reachable Sets

The reachable set $R(v)$ of a node $v$ in a digraph is the set of all vertices reachable from $v$ :

$R(v) = \{u \in V \mid \text{there exists a directed path from } v \text{ to } u\}$

Node Base Theory

A node base $S \subseteq V$ for a digraph $G = (V, E)$ is a minimal subset of vertices such that every vertex in $V$ is reachable from at least one vertex in $S$ .

text

Node Base S: Minimum set of launching points to span the entire graph.
 
  [ s1 ] ───► ( v1 ) ───► ( v2 )
  [ s2 ] ───► ( v3 )

Core Mathematical Properties of a Node Base:

Zero-Indegree Invariant: $S$ must contain all vertices of $G$ that have an indegree of zero ( $\text{deg}^-(v) = 0$ ). Since no incoming edges exist for these nodes, they cannot be reached from any other vertex.
Isolated Node Invariant: $S$ must contain all isolated nodes.
Minimality (Mutual Reachability Exclusion): No node within $S$ should be reachable from any other node within . Formally:

4. Connectivity in Undirected and Directed Graphs

The structural integrity of a graph is determined by its connectivity. We define connectivity differently depending on whether edges are directed.

text

               Connectivity Hierarchy in Digraphs
               
                   ┌────────────────────────┐
                   │   Strongly Connected   │ (Mutual reachability)
                   └───────────┬────────────┘
                               │ (implies)
                               ▼
                   ┌────────────────────────┐
                   │ Unilaterally Connected │ (One-way reachability)
                   └───────────┬────────────┘
                               │ (implies)
                               ▼
                   ┌────────────────────────┐
                   │    Weakly Connected    │ (Connected when undirected)
                   └────────────────────────┘

Directed Connectivity Spectrum

Weakly Connected: A digraph is weakly connected if, when we disregard the directions of all edges, the underlying undirected graph is connected.
Unilaterally Connected: A digraph is unilaterally connected if, for any pair of distinct vertices $u, v \in V$ , there exists a path from $u$ to $v$ or a path from $v$ to $u$ .
Strongly Connected: A digraph is strongly connected if, for any pair of distinct vertices , there exists a path from to a path from to .

Components and Boundary Points

Maximal Subgraphs (Components):
- A connected component of an undirected graph is a maximal connected subgraph.
- A strong component of a digraph is a maximal strongly connected subgraph.
Articulations and Vulnerabilities:
- Cut Vertex (Articulation Point): A vertex whose removal increases the number of connected components in the graph.
- Cut Edge (Bridge): An edge whose removal increases the number of connected components.

text

                 (u) ─── [ Bridge Edge ] ─── (v)
                /   \                       /   \
              (a)---(b)                   (c)---(d)

5. Algebraic and Matrix Representations

While graphical visualizations are useful for small systems, computer algorithms process graphs using algebraic matrices.

Adjacency Matrix

For a graph with $n$ vertices, the adjacency matrix $A$ is an $n \times n$ matrix where:

$a_{ij} = \begin{cases} 1 & \text{if } (i, j) \in E \\ 0 & \text{otherwise} \end{cases}$

text

  Graph:                   Adjacency Matrix A:
   (1) ───► (2)                1  2  3
    │        │             1 [ 0  1  1 ]
    ▼        ▼             2 [ 0  0  1 ]
   (3) ◄─────┘             3 [ 0  0  0 ]

Undirected Graph Invariant: The adjacency matrix of an undirected graph is always symmetric ( $A = A^T$ ).
Degree Computations:
- Row sum represents the outdegree of vertex $i$ : $\text{deg}^+(i) = \sum_{j=1}^n a_{ij}$

Path Counting and Powers of $A$

The entry $a^{(k)}_{ij}$ of the matrix power $A^k$ represents the exact number of walks of length $k$ from vertex $i$ to vertex .

Path Matrix (Reachability Matrix)

The path matrix (or reachability matrix) $P$ is an $n \times n$ Boolean matrix where $p_{ij} = 1$ if there is a path of any length from $i$ to $j$ , and otherwise. It is calculated using Boolean joins and powers:

$P = I \lor A \lor A^{(2)} \lor A^{(3)} \lor \dots \lor A^{(n-1)}$

where $A^{(k)}$ denotes the Boolean product $A \land A^{(k-1)}$ . Alternatively, we can count paths using real arithmetic:

$B_n = A + A^2 + A^3 + \dots + A^n$

Incidence Matrix

For an undirected graph with $V$ vertices and $E$ edges, the incidence matrix $M$ is a $V \times E$ matrix where:

$m_{ij} = \begin{cases} 1 & \text{if vertex } i \text{ is incident to edge } j \\ 0 & \text{otherwise} \end{cases}$

Performance Trade-offs

Modern software systems select graph representations based on edge density:

| Feature | Adjacency Matrix | Adjacency List | | :--- | :--- | :--- | | Space Complexity | $\mathcal{O}(V^2)$ | $\mathcal{O}(V + E)$ | | Edge Lookup ( $u \to v$ ) | $\mathcal{O}(1)$ | | | | Dense graphs () | Sparse graphs () |

Algorithmic Reachability Implementation

To compute reachability programmatically, we can traverse the graph using depth-first search (DFS). The following Python implementation demonstrates how to find the reachable set $R(v)$ for a given vertex:

python

def get_reachable_set(adj_list, start_node):
    """
    Computes the reachable set R(start_node) using Depth-First Search.
    
    :param adj_list: Dict representing the adjacency list (e.g., {1: [2, 3], 2: [3], 3: []})
    :param start_node: The node from which reachability is computed
    :return: A set of all reachable nodes
    """
    visited = set()
    
    def dfs(node):
        visited.add(node)
        for neighbor in adj_list.get(node, []):
            if neighbor not in visited:
                dfs(neighbor)
                
    dfs(start_node)
    return visited
 
# Example Usage:
# Graph: 1 -> 2 -> 3; 1 -> 3
graph = {
    1: [2, 3],
    2: [3],

6. Trees: Properties, Theorems, and Traversals

A tree is a connected, undirected simple graph that contains no cycles. A disjoint collection of trees is called a forest.

text

       Tree (Acyclic, Connected)         Non-Tree (Contains Cycle)
              ( Root )                          ( Root )
               /    \                            /    \
             (A)    (B)                        (A) ── (B)
             / \                               / \
           (C) (D)                           (C) (D)

Characterization Theorems

Unique Simple Path: An undirected graph $G$ is a tree if and only if there is a unique simple path between any two of its vertices.
Edge-Vertex Relation: A tree with $n$ vertices always contains exactly $n - 1$ edges: $|E| = |V| - 1$

Rooted Trees and Terminology

In a rooted tree, one vertex is designated as the root, and all edges are directed away from it:

Parent/Child: If a directed edge goes from $u$ to $v$ , then $u$ is the parent of $v$ , and $v$ is a child of $u$ .
Siblings: Vertices that share the same parent.
Ancestors/Descendants: The ancestors of a node $v$ are the vertices on the unique path from the root to . The descendants of are all vertices that have as an ancestor.

m-ary and Binary Trees

$m$ -ary Tree: A rooted tree where every internal node has at most $m$ children.
Full $m$ -ary Tree: Every internal node has exactly $m$ children.
Binary Tree: A 2-ary tree. Each child is designated as either a left child or a right child.

Tree Traversal Algorithms

Tree traversals recursively visit every node in an ordered rooted tree exactly once:

text

                      ( Root )
                       /    \
                    [Left]  [Right]

Preorder (Root $\to$ Left $\to$ Right):
1. Visit the root.
2. Traverse the left subtree.
3. Traverse the right subtree.
Inorder (Left $\to$ Root $\to$ Right):
1. Traverse the left subtree.
2. Visit the root.
3. Traverse the right subtree.
Postorder (Left $\to$ Right $\to$ Root):
1. Traverse the left subtree.
2. Traverse the right subtree.
3. Visit the root.

7. Classical Traversal Paths and Planarity Theorems

Certain classes of paths and structural constraints have historical and practical importance in discrete mathematics.

Eulerian Paths and Circuits

An Euler Path is a trail that visits every edge in a graph exactly once.
An Euler Circuit is a closed trail that visits every edge in a graph exactly once.
Existence Theorems:
- A connected multigraph has an Euler circuit if and only if every vertex has an even degree.
- A connected multigraph has an Euler path (and no circuit) if and only if it has exactly two vertices of odd degree. These two vertices serve as the starting and ending points.

Hamiltonian Paths and Circuits

A Hamilton Path is a simple path that visits every vertex in a graph exactly once.
A Hamilton Circuit is a simple cycle that visits every vertex in a graph exactly once.
Unlike Eulerian circuits, determining whether a graph contains a Hamiltonian circuit is NP-complete. However, sufficient conditions exist:
- Dirac's Theorem: If $G$ is a simple graph with $n \ge 3$ vertices, and every vertex $v$ satisfies: $\text{deg}(v) \ge \frac{n}{2}$ then has a Hamilton circuit.

text

              K_5 (Nonplanar)              K_3,3 (Nonplanar Utility)
                   (1)                            (A)   (B)   (C)
                  / | \                            │ \ / │ \ / │
                (2)─┼─┼─(5)                        │  X  │  X  │
                 \  │ │  /                         │ / \ │ / \ │
                  (3)─(4)                         (X)   (Y)   (Z)

Planar Graphs and Euler's Formula

A graph is planar if it can be drawn in a single plane such that no two edges intersect except at their common endpoints.

Euler's Formula

For any connected planar simple graph, the relationship between the number of vertices $v$ , edges $e$ , and bounded regions (faces) $r$ is constant:

$r = e - v + 2$

Corollaries for Planar Bound Analysis

For any connected planar simple graph with $v \ge 3$ vertices, the number of edges is bounded by: $e \le 3v - 6$
If a connected planar simple graph has no cycles of length 3 (meaning its girth is at least 4, such as in bipartite graphs) and $v \ge 3$ , then: $e \le 2v - 4$

Nonplanarity Proofs

Using these corollaries, we can mathematically prove that certain graphs cannot be drawn on a plane:

For $K_5$ (Complete graph on 5 vertices): Here, $v = 5$ and $e = \binom{5}{2} = 10$ . Applying the first corollary: Thus, is nonplanar.

Kuratowski's Theorem

Two graphs are homeomorphic if they can both be obtained from the same graph by a sequence of elementary subdivisions (inserting a vertex of degree 2 into an existing edge).

Kuratowski's Theorem: A graph is planar if and only if it does not contain a subgraph that is homeomorphic to $K_5$ or $K_{3,3}$ .

Summary

Walks, Trails, and Paths: Establish the foundation of graph traversal, moving from general edge-vertex sequences to highly restricted node-elementary structures.
Connectivity Levels: Digraphs require precise definitions of weak, unilateral, and strong connectivity depending on directionality and reachability.
Node Bases: Identify the minimal set of source nodes ( $S$ ) required to traverse an entire directed system, relying on zero-indegree invariants.
Matrix Representations: Adjacency and path matrices translate topological paths into algebraic operations, enabling fast path computation via matrix powers.
Planarity Limits: Euler's formula and Kuratowski's theorem define the mathematical limits of drawing graphs on two-dimensional surfaces, establishing the properties of nonplanar structures like $K_5$ and $K_{3,3}$ .

Assessed progress

Paths, Reachability, and Connectivity

Key Concepts

Path vs. Walk vs. Trail

Connectivity in Digraphs

Node Base

Algebraic Reachability

Euler's Planarity Formula

Quick Check

Discrete Mathematical Structures

Discrete Mathematical Structures