Graph Theory

In power system modeling, the physical network is abstracted into a graph G = (V, E) where:

• Vertices (V) represent electrical buses, substations, and load connection points
• Edges (E) represent transmission lines, distribution feeders, transformers, and switching devices

Each edge carries weights such as impedance, thermal capacity, or line length. This abstraction allows network reconfiguration algorithms to treat switch operations as edge additions or removals, transforming a complex electrical engineering problem into a computationally tractable graph search.

Graph connectivity is encoded mathematically using two fundamental matrix representations:

• Adjacency Matrix (A): An n×n matrix where A[i][j] = 1 if an edge connects bus i to bus j, and 0 otherwise. For weighted graphs, the entry stores the edge weight instead
• Incidence Matrix (B): An n×m matrix mapping buses to branches, where each column represents an edge with +1 at the source bus and -1 at the destination bus

These matrices form the computational backbone for power flow solvers and state estimation algorithms, enabling efficient matrix operations during topology optimization.

Dijkstra's algorithm and its variants are applied to find optimal power delivery paths through meshed networks. In grid reconfiguration:

• Edge weights are set to line losses (I²R) rather than physical distance
• The algorithm identifies the path that minimizes total resistive losses while respecting thermal constraints
• For service restoration, the shortest path to an alternative source determines which tie switches to close

Advanced implementations use A search* with heuristic functions based on geographic proximity and available capacity to accelerate convergence in large-scale distribution networks with thousands of buses.

Distribution networks must operate in a radial configuration — a topology without loops — to simplify protection coordination and fault current management. This operational requirement maps directly to the graph theory concept of a spanning tree:

• A spanning tree connects all vertices using exactly n-1 edges with no cycles
• Each valid grid configuration corresponds to a unique spanning tree of the underlying meshed graph
• Kruskal's algorithm and Prim's algorithm generate minimum-weight spanning trees, where weight can represent losses, voltage deviation, or loading imbalance

The Branch Exchange Method iteratively swaps edges to transition between spanning trees, finding lower-loss radial configurations without violating connectivity.

When a fault occurs, depth-first search (DFS) and breadth-first search (BFS) algorithms traverse the network graph to determine:

• Upstream isolation: Which switching devices must open to de-energize the faulted segment
• Downstream restoration: Which healthy sections can be re-energized through alternative tie switches
• Connectivity verification: Ensuring no customers are inadvertently isolated after reconfiguration

These traversal algorithms execute in O(V + E) time, enabling real-time fault response within the sub-cycle protection requirements of modern distribution automation systems.

Graph partitioning algorithms divide the network into self-sufficient subgraphs during emergency conditions:

• Each partition must contain sufficient distributed generation to meet local load
• Spectral clustering uses eigenvalues of the graph Laplacian matrix to identify natural partition boundaries
• The minimum cut problem identifies the fewest edges to sever, minimizing switching operations

This technique enables microgrid formation during wide-area disturbances, where each island maintains its own frequency and voltage control independent of the main grid.