Une structure combinatoire constituée d'un ensemble de sommets (nœuds) et d'un ensemble d'arêtes (paires ou paires ordonnées de sommets) utilisée pour représenter des relations discrètes, la connectivité et les interactions.

Principe

L'adjacence encode les relations binaires : la présence, la direction et le poids des arêtes traduisent l'architecture des connexions ; les concepts de la théorie des graphes (chemins, composantes, cycles, coupures) formalisent la connectivité indépendamment de tout plongement.

Démonstration

Un réseau social où les sommets représentent des personnes et les arêtes pondérées la fréquence des communications : les composantes révèlent des communautés déconnectées, les algorithmes de plus court chemin identifient des introductions en nombre minimal d'étapes, et les mesures de centralité mettent en évidence les nœuds influents.

Mauvaise application

Interpréter un graphe comme un objet géométrique avec des propriétés métriques basé uniquement sur les positions des nœuds sans utiliser les données d'arêtes, ou traiter un multigraphe comme un graphe simple en perdant l'information de multiplicité cruciale pour le débit ou la capacité.

Conséquence

Un modélisation correcte par graphe permet des algorithmes de routage, de regroupement, d'appariement et de flot ; les propriétés spectrales des matrices de graphe (adjacence, Laplacien) permettent le partitionnement, la modélisation de diffusion et l'analyse de stabilité.

Inversion

Remplacer les arêtes discrètes par des connexions continues (une variété ou un continuum métrique) inverse le modèle relationnel discret en un domaine continu où les algorithmes combinatoires ne s'appliquent plus directement.

Limite

Couvre les graphes simples, orientés, pondérés et les multigraphes mais exclut les hypergraphes (arêtes joignant des sous‑ensembles arbitraires sans réduction par paires), les complexes simpliciaux à faces d'ordre supérieur, et les nuages de points purement géométriques sauf si des arêtes sont définies.

Tension sémantique

Tension entre « graphe » et « réseau » : le graphe insiste sur la structure combinatoire, le réseau implique souvent un contexte d'application et possiblement une dynamique ou une métrique ; tension aussi avec matrice d'adjacence (représentation algébrique) et hypergraphe (relations d'ordre supérieur).

Synthèse

Le graphe est l'abstraction discrète de la connectivité par paires : une structure minimale (sommets et arêtes) qui admet une analyse combinatoire, algébrique et algorithmique pour modéliser et résoudre des problèmes de relations et de flux.