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 $G=(V,E)$ ein einfacher Graph. Dann heißt

$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 $d(G):={\frac {2|E|}{|V|^{2}}}$, um übersichtlichere Ergebnisse bei asymptotischen Aussagen für $|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.

Literatur

• Reinhard Diestel: Graphentheorie. Springer, Berlin 2010, ISBN 978-3-642-14911-5 (354 S.).