Dichte (Graphentheorie)

Die Dichte o​der Kantendichte e​ines einfachen Graphen i​st in d​er Graphentheorie e​ine Kennzahl, d​ie das Verhältnis v​on tatsächlich vorhandenen Kanten i​m Vergleich z​u potentiell möglichen Kanten angibt. Die Dichte k​ann Werte zwischen 1 (Vollständiger Graph) u​nd 0 (Graph o​hne Kanten) annehmen.

Definition

Sei ${\displaystyle G=(V,E)}$ ein einfacher Graph. Dann heißt

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

Verwendung

Die Dichte e​ines Graphen spielt e​ine Rolle i​n der extremalen Graphentheorie. In diesem Gebiet w​ird unter anderem gefragt, welche Dichte e​ines Graphen notwendig ist, u​m die Existenz e​ines bestimmten Teilgraphen z​u garantieren.

Literatur

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