Direkt zum Inhalt

Lexikon der Mathematik: Durchmesser eines Graphen

größter existierender Abstand in einem Graphen.

Dabei wird der Abstand dG(x, y) zweier Ecken x und y in einem zusammenhängenden GraphenG durch die Länge eines kürzesten Weges von x nach y definiert, und man setzt dG(x, x) = 0.

Die Exzentrizität einer Ecke vE(G) wird gegeben durch

\begin{eqnarray}e(v,G)=\rm{max}\{{d}_{G}(x,v)|x\in E(G)\}.\end{eqnarray}

Die Größen diam(G) = max{e(x, G)|xE(G)} bzw. rad(G) = min{e(x, G)|xE(G)} nennt man Durchmesser bzw. Radius von G.

Folgende Abschätzungen lassen sich schnell nachweisen:

\begin{eqnarray}\text{rad(}G\text{)}\le \text{diam(}G\text{)}\le \text{2rad(}G\text{)}\text{.}\end{eqnarray}

Beide Ungleichungen sind bestmöglich, denn es gilt z. B. rad(C) = diam(C) = ⌊n/2⌋ für einen Kreis der Länge n und rad(W) = p und diam(W) = 2p für einen Weg der Länge 2p.

Ist diam(G) ≥ 4, so beweist man mit etwas mehr Aufwand \(\rm{diam}(\bar{G})\,\le \,2\), wobei \(\bar{G}\) der Komplementärgraph von G ist. Daher ist der Durchmesser eines selbstkomplementären Graphen höchstens 3. Diese Beobachtung geht auf G. Ringel (1963) zurück.

Das Zentrum eines Graphen besteht aus allen Ecken x mit e(x, G) = rad(G). Schon im Jahre 1869 hat C. Jordan gezeigt, daß das Zentrum eines Baumes aus einer Ecke oder zwei adjazenten Ecken besteht.

  • Die Autoren
- Prof. Dr. Guido Walz

Schreiben Sie uns!

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.