Graphs

Graphs are mathematical structures used to model pairwise relations between objects. A graph consists of a set of vertices, or nodes, and a set of edges connecting pairs of vertices. In a directed graph, edges have a direction; in an undirected graph they do not. Edges may be unweighted or weighted. Graphs can be finite or infinite, simple or allow multiple edges (multigraphs) or loops (pseudographs).

Key concepts include the degree of a vertex (in-degree and out-degree in directed graphs). A path is a sequence of edges; a cycle starts and ends at the same vertex. A graph is connected if any two vertices are joined by a path; for directed graphs, strong connectivity requires a directed path in both directions. Subgraphs, induced subgraphs, and spanning subgraphs are formed by selecting subsets of vertices and edges. Notable families include trees (connected acyclic graphs), forests, complete graphs, and bipartite graphs. Planar graphs can be drawn on a plane without crossing edges.

Algorithms and representations: BFS and DFS explore structure. Shortest-path algorithms such as Dijkstra’s and Bellman–Ford compute minimal distances. Kruskal’s and Prim’s algorithms find minimum spanning trees. Network flow and max-flow/min-cut solve allocation problems; graph coloring addresses partitioning. Common representations include adjacency matrices and adjacency lists, and incidence matrices record vertex-edge incidences.

Applications include computer networks, social networks, transportation and logistics, scheduling, and dependency analysis in software and project management. Theoretical aspects connect to fields such as combinatorics, topology, and algorithm design. Graphs provide a versatile framework for modeling relations, analyzing connectivity, redundancy, and flow.