Graphes

Graphes, also called graphs in English, are a mathematical structure consisting of a set of vertices (or nodes) and a set of edges that connect pairs of vertices. Edges may be undirected, indicating a bidirectional relation, or directed, giving an orientation and forming a digraph. In weighted graphs, edges carry a numerical weight representing cost, length, or capacity. If no edge connects a pair of vertices more than once and a vertex has no loop, the graph is simple; general graphs may include multiple edges or loops (multigraphs and pseudographs).

Graphs are commonly represented in two ways: adjacency matrices and adjacency lists. An adjacency matrix is a square array indicating whether pairs of vertices are connected (and by what weight, if applicable). An adjacency list lists, for each vertex, its neighboring vertices. The degree of a vertex in an undirected graph is the number of incident edges; in a directed graph, a vertex has an in-degree and an out-degree.

Core concepts include paths, walks, trails, and cycles. A graph is connected if there is a path between every pair of vertices; a connected component is a maximal connected subgraph. Trees are connected acyclic graphs. Planar graphs can be drawn on a plane without edge crossings. Graph coloring assigns colors to vertices so that adjacent vertices differ in color.

Applications and subareas are broad, covering matching, flow, routing, and network design, as well as isomorphism, subgraph containment, and coloring problems. Graphs underpin many algorithms, such as graph traversals (breadth-first and depth-first search) and shortest-path methods (Dijkstra and Bellman-Ford), forming a foundational tool in computer science and discrete mathematics.

Historically, graph theory emerged from Euler’s solution to the Königsberg bridges problem, laying the groundwork for the field. The term graph, and the modern abstract concept, developed in the 19th century and is now central to modeling relational structures across disciplines.