[Graphentheorie:] Zz.: rad(G) <= diam(G) <= 2*rad(G) ?!?

14.06.2005, 00:51	Asgaroth	Auf diesen Beitrag antworten »
*[Graphentheorie:] Zz.: rad(G) <= diam(G) <= 2rad(G) ?!?** 1. Zu jeder Ecke $\begin{eqnarray} a\in E \end{eqnarray}$ eines zusammenhängenden Graphen $\begin{eqnarray} G = (E,K) \end{eqnarray}$ betrachten wir den maximalen Abstand $\begin{eqnarray} d(a,b) \end{eqnarray}$ zu einer anderen Ecke b. Diejenigen Ecken $\begin{eqnarray} a_0 \end{eqnarray}$ , für welche diese Zahl $\begin{eqnarray} \max_{b\in E} d(a_0,b) \end{eqnarray}$ minimal ist (d.h. $\begin{eqnarray} \max_{b\in E} d(a_0,b) =\min_{a\in E} \max_{b\in E} d(a,b) \end{eqnarray}$ ), bezeichnen wir als zentral. Diesen maximalen Abstand von $\begin{eqnarray} a_0 \end{eqnarray}$ zu einer anderen Ecke nennt man den Radius $\begin{eqnarray} rad(G) = \min_{a\in E} \max_{b\in E} d(a,b) \end{eqnarray}$ von G. Analog wird der Durchmesser $\begin{eqnarray} diam(G) = \max_{a\in E} \max_{b\in E} d(a,b) \end{eqnarray}$ definiert. Zeige: $\begin{eqnarray} rad(G)\le diam(G) \le 2rad(G) \end{eqnarray}$ Also ich hatte mir überlegt das der maximale Radius $\begin{eqnarray} \max(rad(G)) \end{eqnarray}$ von G, $\begin{eqnarray} \max_{a\in E} \max_{b\in E} d(a,b) \end{eqnarray}$ ist. Dies kommt zustande wenn das minimum zugleich das maximum ist. Dadurch wäre dann: $\begin{eqnarray} \max(rad(G))=\max_{a\in E} \max_{b\in E} d(a,b) = diam(G) \end{eqnarray}$ damit wäre schoneinmal $\begin{eqnarray} rad(G)\le diam(G) \end{eqnarray}$ bewiesen. Bei $\begin{eqnarray} diam(G) \le 2rad(G) \end{eqnarray}$ bin ich mir allerdings nicht ganz sicher. Es müsste nach meiner idee $\begin{eqnarray} 2rad(G) \end{eqnarray}$ dann maximal $\begin{eqnarray} 2max(rad(G)) \end{eqnarray}$ sein und damit dann $\begin{eqnarray} 2* \max(rad(G))=2* \max_{a\in E} \max_{b\in E} d(a,b) = 2* diam(G) \end{eqnarray}$ dadurch folgt dann $\begin{eqnarray} 2diam(G) \geq diam(G) \Rightarrow 2rad(G) \geq diam(G) \end{eqnarray}$ Aber ich glaube das wäre alles zu einfach, ich hab sicher irgend einen Denkfehler in meiner "Lösung", allerdings kann das unter umständen daran liegen das ich das ganze $\begin{eqnarray} \max \max \end{eqnarray}$ und $\begin{eqnarray} \min \max \end{eqnarray*}$ nicht so ganz verstanden habe... falls mir das jemand genauer erklären könnte wäre mir auch geholfen. Mit freundlichen Grüßen und schon im voraus dankend, Asgaroth

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »