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 v ∈ E(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)|x ∈ E(G)} bzw. rad(G) = min{e(x, G)|x ∈ E(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.
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.