Graphe

Graphe, the French term for the mathematical object known in English as a graph, consists of a set of vertices (or nodes) and a set of edges (or links) that connect pairs of vertices. A graphe may be directed or undirected and may be weighted or unweighted.

Common variants include simple graphe (no loops or multiple edges), multigraph (allowing multiple edges between the same pair of vertices), and pseudograph (allowing loops). In directed graphe, one distinguishes in-degree and out-degree. A graphe is connected if there is a path between every pair of vertices; otherwise it has connected components. A graphe is planar if it can be drawn in the plane without edge crossings. Bipartite graphe have their vertices partitioned into two sets with edges only across sets.

A graphe is typically represented in software as adjacency lists or adjacency matrices. Basic problems include finding a shortest path (Dijkstra’s or Bellman–Ford), traversals (breadth-first or depth-first), and reachability. Important concepts include paths, cycles, subgraphs, spanning trees, and graph isomorphism. Special classes include Eulerian graphe (with a trail that uses every edge exactly once) and Hamiltonian graphe (with a cycle visiting every vertex).

The term graphe derives from the Greek graphein, meaning to write. The study began with Euler’s Königsberg bridges problem in 1736, which helped found graph theory. Today graphe model networks in many domains, including social networks, transportation, circuit design, chemistry, and biology.