In functional programming, graphs—both directed and undirected—are commonly represented using adjacency lists or adjacency matrices. These representations are manipulated through pure functions, adhering to the principles of functional programming.

To elaborate, a graph consists of a set of vertices and edges, where each edge connects a pair of vertices. In a directed graph, edges have a specific direction, indicating a one-way relationship from one vertex to another. In contrast, an undirected graph has edges that do not have a designated direction. In functional programming, these graphs are typically modeled using data structures such as adjacency lists or adjacency matrices.

An adjacency list is a collection of unordered lists that represent a finite graph. Each list corresponds to a vertex and contains the set of its neighboring vertices. This representation is storage-efficient, as it only records the vertices that are directly connected by edges. For instance, in Haskell, you can represent an adjacency list as a list of tuples, where the first element of each tuple is a vertex and the second element is a list of its neighboring vertices.

Conversely, an adjacency matrix is a two-dimensional array of size $V \times V$, where $V$ denotes the number of vertices in the graph. In this matrix, the entry $A[i][j]$ is either $1$ or $0$, depending on whether there is an edge from vertex $i$ to vertex $j$. This representation is particularly efficient when dealing with dense graphs, where the number of edges is close to $V^2$.

Manipulating graphs in functional programming relies on pure functions—functions that do not produce side effects and consistently return the same output for identical inputs. For example, when adding a vertex to a graph represented by an adjacency list, you would generate a new list that includes the new vertex alongside all existing vertices and edges. Similarly, removing a vertex would involve creating a new list that contains all vertices and edges, excluding those associated with the vertex to be removed. This method safeguards the original graph from modification, which is a fundamental principle of functional programming.