Eine kombinatorische Struktur aus einer Menge von Knoten (Vertices) und einer Menge von Kanten (ungeordnete oder geordnete Paare von Knoten), die diskrete Beziehungen, Konnektivität und Interaktionen modelliert.

Prinzip

Adjazenz kodiert binäre Relationen: Existenz, Richtung und Gewicht von Kanten fassen die Architektur von Verbindungen zusammen; graphentheoretische Begriffe (Wege, Komponenten, Zyklen, Schnitte) formalisieren Konnektivität unabhängig von einer Einbettung.

Demonstration

Ein soziales Netzwerk, bei dem Knoten Personen und gewichtete Kanten die Kommunikationshäufigkeit darstellen: Komponenten zeigen getrennte Communities, kürzeste‑Pfad‑Algorithmen identifizieren minimale Vermittlungen und Zentralitätsmaße heben einflussreiche Knoten hervor.

Fehlanwendung

Einen Graphen als geometrisches Objekt mit Metrikeigenschaften nur anhand von Knotenpositionen zu interpretieren, ohne Kantendaten zu verwenden, oder einen Multigraphen als simplen Graphen zu behandeln und damit Multiplizität zu verlieren, die den Fluss beeinflusst.

Konsequenz

Korrekte Graphmodellierung liefert Algorithmen für Routing, Clustering, Matching und Fluss; spektrale Eigenschaften von Graphmatrizen (Adjazenz, Laplace) ermöglichen Partitionierung, Diffusionsmodellierung und Stabilitätsanalyse.

Umkehrung

Diskrete Kanten durch kontinuierliche Verbindungen (eine Mannigfaltigkeit oder ein metrisches Kontinuum) zu ersetzen, kehrt das diskrete relationale Modell in einen kontinuierlichen Bereich um, in dem kombinatorische Algorithmen nicht direkt anwendbar sind.

Abgrenzung

Umfasst einfache Graphen, gerichtete, gewichtete und Multigraphen, schließt jedoch Hypergraphen (Kanten, die beliebige Teilmengen verbinden) sowie simpliziale Komplexe höherer Ordnung und rein geometrische Punktwolken ohne definierte Kanten aus.

Semantische Spannung

Spannung zwischen 'Graph' und 'Network': 'Graph' betont die kombinatorische Struktur, 'Network' impliziert häufig Anwendungs‑Kontext und Dynamik oder Metrik; Spannung besteht auch gegenüber Adjazenzmatrix (algebraische Darstellung) und Hypergraph (höhere Ordnungsrelationen).

Synthese

Ein Graph ist die diskrete Abstraktion paarweiser Konnektivität: eine minimalistische Datenstruktur (Knoten plus Kanten), die kombinatorische, algebraische und algorithmische Analysen erlaubt, um Beziehungs‑ und Flussprobleme zu modellieren und zu lösen.