Graph theory

Graph theory is the mathematical study of structures made of vertices and edges. It investigates properties such as connectivity, paths, coloring, and networks.

Graph (discrete mathematics): A structure consisting of vertices and edges that connect pairs of vertices. This is the central object whose properties graph theory studies.
Path (graph theory): A sequence of vertices in which consecutive vertices are joined by edges. Paths formalize routes through a graph and underpin distance and reachability.
Shortest path problem: The problem of finding a path of minimum total weight between specified vertices. It models route planning when edges represent distance, time, or cost.
Seven Bridges of Königsberg: A historical puzzle asking whether each of Königsberg's seven bridges could be crossed exactly once. The puzzle supplied the concrete problem Euler recast in terms of vertices and edges.
Hypergraph: A generalization of a graph in which an edge can connect any number of vertices. Ordinary graph edges connect pairs, while hyperedges can represent group relationships directly.
Vertex (graph theory): An individual point or object represented within a graph. Vertices represent the entities whose relationships graph theory analyzes.
Connected graph: A graph in which every pair of vertices is joined by a path. Connectivity asks whether the graph remains traversable between all its vertices.
Dijkstra's algorithm: An algorithm that finds shortest paths from one source in a graph with nonnegative edge weights. It is a standard method for solving weighted route problems.
Leonhard Euler: An eighteenth-century mathematician whose work established foundations across many areas of mathematics. Euler's 1736 analysis of the Königsberg bridges is widely treated as graph theory's origin.
Network science: An interdisciplinary field that studies network structure and dynamics in real-world systems. It applies graph-theoretic tools while also addressing empirical systems and their behavior.

Linked from 97 pages