Graph Theory in Networks

Applying concepts like graph degree, paths, and connectivity to network analysis.

The Language of Networks

At its core, a telecommunication network can be visualized as a map of interconnected points. Graph theory is the branch of mathematics that provides the perfect language and set of tools to describe, analyze, and optimize these networks. By representing a network as a graph, we can apply rigorous mathematical principles to solve complex problems related to routing, reliability, and efficiency.

The Building Blocks of a Graph

Every network graph consists of two fundamental components:

Vertex (or Node): A point in the network. This can represent a computer, a router, a switch, or a telephone exchange.
Edge (or Link): A connection between two vertices. This represents a physical communication link, such as a fiber optic cable, a copper wire, or a wireless connection.

Graphs can be (if traffic flows only one way) or (if traffic can flow in both directions).

Key Graph Properties and Network Characteristics

Analyzing certain properties of the graph gives us deep insights into the characteristics of the network it represents.

Graph Degree

The of a vertex measures its connectivity. The minimum ( $\delta(G)$ ) and maximum ( $\Delta(G)$ ) degrees in a graph tell us about the least and most connected nodes in the network, which is crucial for identifying potential bottlenecks or single points of failure.

Special Graph Types

Regular Graph: A graph where every vertex has the same degree. This represents a network with a balanced and predictable structure. A 3-regular graph is called a cubic graph.
Complete Graph ( $K_n$ ): A graph where every pair of vertices is connected by an edge. This represents a fully meshed, highly redundant network. The number of edges required is $\frac{n(n-1)}{2}$ , making it very expensive for large $n$ .
Planar Graph: A graph that can be drawn on a plane without any edges crossing. This concept is relevant to the physical layout of circuits and some network diagrams. The notes mention that a complete graph with 5 or more vertices ( $K_5$ ) is non-planar.

Paths and Network Resilience

A key function of a network is to find paths for data to travel from a source to a destination. The number and type of available paths determine the network's resilience to failures.

Edge-Disjoint Paths: These are two or more paths between the same start and end nodes that do not share any common edges (links). This provides resilience against a single link failure (e.g., a cut cable).
Vertex-Disjoint Paths: These are paths that share only their start and end nodes, with no common intermediary nodes or links. This is a stronger form of resilience, as it protects against the failure of an entire node (e.g., a router crash), not just a link.
Graph Connectivity: This is a measure of a network's robustness. ( $\kappa'(G)$ ) is the minimum number of links that must fail to split the network into two. ( $\kappa(G)$ ) is the minimum number of nodes that must fail. These values are related by the inequality: $\kappa(G) \leq \kappa'(G) \leq \delta(G)$ .

Classic Graph Problems in Networking

Many fundamental network design tasks correspond to well-known problems in graph theory.

Minimum Spanning Tree (MST): The goal is to find a subset of edges that connects all vertices in a together, without creating any cycles and with the minimum possible total edge weight.
This is directly applicable to designing the most cost-effective backbone network that connects a set of cities or data centers. The notes mention two famous algorithms for finding the MST: Prim's algorithm and Kruskal's algorithm.
Traveling Salesman Problem (TSP) & Hamiltonian Cycle: This is the problem of finding the shortest possible route that visits each vertex exactly once and returns to the origin. A route that visits every vertex exactly once is called a .
This problem arises in network topology design, particularly for ring networks, where the goal is to connect all nodes in a loop with the minimum total cable length.