Dichte (Graphentheorie)

Verhältnis von vorhandenen zu möglichen Kanten in der 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

Bearbeiten

Sei   ein einfacher Graph. Dann heißt

 

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  , um übersichtlichere Ergebnisse bei asymptotischen Aussagen für   zu erhalten.

Verwendung

Bearbeiten

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

Bearbeiten