Udowodnić, że \(\displaystyle{ diam(G) \le 2rad(G)}\), gdzie \(\displaystyle{ diam(G)=max\{dist(x,y)\}}\) - średnica grafu, a \(\displaystyle{ rad(G)=min_{x}max_y\{dist(x,y)\}}\) - promień grafu G.
Z góry dziękuję za pomoc.
Nierówność między średnicą a promieniem grafu prostego
-
Qń
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
Nierówność między średnicą a promieniem grafu prostego
\(\displaystyle{ x}\) dla którego wyrażenie \(\displaystyle{ \max_y\{ dist (x,y)\}}\) przyjmuje wartość miminalną oznaczmy przez \(\displaystyle{ a}\). Mamy zatem:
\(\displaystyle{ rad(G)=\max_y\{ dist (a,y)\}}\)
Stąd zaś:
\(\displaystyle{ 2rad(G)= \max_y\{ dist (a,y)\}+\max_y\{ dist (a,y)\}=\max_y\{ dist (a,y)\}+\max_x\{ dist (a,x)\}= \\ =\max_{x,y}\{ dist (a,y)+ dist (a,x)\}\ge \max_{x,y}\{ dist (x,y)\}=diam (G)}\)
Q.
\(\displaystyle{ rad(G)=\max_y\{ dist (a,y)\}}\)
Stąd zaś:
\(\displaystyle{ 2rad(G)= \max_y\{ dist (a,y)\}+\max_y\{ dist (a,y)\}=\max_y\{ dist (a,y)\}+\max_x\{ dist (a,x)\}= \\ =\max_{x,y}\{ dist (a,y)+ dist (a,x)\}\ge \max_{x,y}\{ dist (x,y)\}=diam (G)}\)
Q.