An undirected graph is a type of graph in which edges have no direction, meaning that they do not have an initial or terminal vertex. In other words, the relationship between vertices in an undirected graph is symmetric, and edges can be represented simply as unordered pairs of vertices.
Formally, an undirected graph G is defined by a set of vertices V and a set of edges E, where each edge is an unordered pair of vertices. Mathematically, E is a subset of (2V), the set of all 2-element subsets (unordered pairs) of V.
Undirected graphs are often represented visually with nodes (vertices) and lines (edges) connecting the nodes. The absence of arrows on the edges signifies that the relationship between vertices is mutual or bidirectional.
Examples of situations that can be modeled with undirected graphs include:
-
Social networks: Nodes represent individuals, and edges represent friendships or connections. Friendships are typically mutual, making the graph undirected.
-
Transportation networks: Nodes represent locations, and edges represent roads or links between locations. The roads are bidirectional in most cases.
-
Puzzle solving: Nodes represent states, and edges represent possible transitions between states in a puzzle-solving scenario. The transitions are often symmetric.
Undirected graphs can be connected (there is a path between every pair of vertices) or disconnected (there are isolated components). Algorithms for traversing, searching, and analyzing undirected graphs play a fundamental role in graph theory and various applications, such as network analysis and optimization.
