sundirected

An undirected graph, sometimes referred to as a sundirected graph, is a graph in which edges have no orientation. Each edge connects two vertices without any order, so if a is adjacent to b, then b is also adjacent to a. Edges can be simple (no repeats or loops) or multiedges, and a loop contributes twice to the degree of its vertex.

A graph G is typically denoted as G = (V, E), where V is a set of vertices and E is a set of unordered pairs of vertices. The degree of a vertex v, deg(v), counts incident edges; a loop adds 2 to deg(v). Undirected graphs are commonly represented by symmetric adjacency matrices, where the entry A[u][v] equals the number of edges between u and v (or 1 for simple graphs). Adjacency lists store neighbor sets for each vertex.

Key concepts include connectivity, where a graph is connected if there is a path between every pair of vertices; otherwise it consists of connected components. Particular classes include trees (connected acyclic graphs), forests (disjoint unions of trees), cycles, and bipartite graphs. Regular graphs have the same degree at every vertex. Planarity concerns whether a graph can be drawn in the plane without crossing edges.

Algorithms for undirected graphs include depth-first search and breadth-first search for traversal, as well as algorithms for minimum spanning trees (Kruskal, Prim) on weighted graphs, and various path and connectivity problems. Since the edges are undirected, many properties are symmetric and can simplify analysis.

Applications of undirected graphs appear in modeling mutual relationships (for example, friendship networks), road maps where all roads are bidirectional, certain chemical structures, and network reliability studies. The undirected model serves as the underlying structure for many problems where edge orientation is either absent or ignored, contrasting with directed graphs where edges have a chosen direction.