graph

Graph theory studies graphs, mathematical structures used to model relations between objects. A graph G consists of a set V of vertices and a set E of edges that connect pairs of vertices. In an undirected graph edges have no orientation; in a directed graph, or digraph, edges have a direction indicating a one-way relationship. Edges may be simple, between two distinct vertices with at most one edge between a pair, or may allow parallel edges (multigraphs) and loops (edges from a vertex to itself), creating pseudographs.

Graphs can be weighted, with each edge assigned a numerical value such as distance or cost. Common representations include the adjacency matrix, where the entry at i, j records the presence or weight of an edge between vertices i and j, and the adjacency list, where each vertex stores its neighbors. The incidence matrix records incidence between vertices and edges.

Key concepts include the degree of a vertex (for undirected graphs, the number of incident edges; for directed graphs, in-degree and out-degree). A path is a sequence of edges joining consecutive vertices; a cycle is a closed path. A graph is connected if there is a path between every pair of vertices; otherwise it consists of connected components. A tree is a connected acyclic graph; forests are disjoint unions of trees. Planar graphs can be drawn on the plane without crossing edges.

Special families include complete graphs, bipartite graphs, regular graphs, and sparse or dense graphs. Graphs have broad applications in computer science, transportation, social networks, biology, and beyond, serving as models for routing, scheduling, network flow, and circuit design. Foundational results include the Handshaking Lemma, stating that the sum of vertex degrees equals twice the number of edges, and various traversal and optimization algorithms such as depth-first search and breadth-first search.