Dichte (Graphentheorie)
Die Dichte oder Kantendichte eines einfachen Graphen ist in der Graphentheorie eine Kennzahl, die das Verhältnis von tatsächlich vorhandenen Kanten im Vergleich zu potentiell möglichen Kanten angibt. Die Dichte kann Werte zwischen 1 (Vollständiger Graph) und 0 (Graph ohne Kanten) annehmen.
Definition
Sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G=(V,E)} ein einfacher Graph. Dann heißt
- Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d(G) := \frac{|E|}{\binom{|V|}{2}} = \frac{2|E|}{|V|(|V|-1)} }
die Dichte oder auch Kantendichte des Graphen. Damit ist die Dichte das Verhältnis der Kantenzahl des Graphen zur Kantenzahl des vollständigen Graphen mit gleich vielen Knoten. Es findet sich auch die Definition Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d(G) := \frac{2|E|}{|V|^2} } , um übersichtlichere Ergebnisse bei asymptotischen Aussagen für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle |V| \rightarrow \infty } zu erhalten.
Verwendung
Die Dichte eines Graphen spielt eine Rolle in der extremalen Graphentheorie. In diesem Gebiet wird unter anderem gefragt, welche Dichte eines Graphen notwendig ist, um die Existenz eines bestimmten Teilgraphen zu garantieren.
