Wykaż,że dla dowolnego grafu G prawdziwa jest nierówność :
\(\displaystyle{ Rad(G) \leq |G|/2}\)
graf, promień dowód
-
Rudis
- Użytkownik
- Posty: 83
- Rejestracja: 6 sty 2014, o 13:07
- Płeć: Mężczyzna
- Lokalizacja: Brak
- Podziękował: 3 razy
- Pomógł: 17 razy
graf, promień dowód
Zgaduję,że zadanie na środową dyskretną.
Zacznę od tego, że graf musi być spójny bo w definicji promienia występuję odległość między wierzchołkami.A jak odległość to i krawędzie.W przypadku grafu niespójnego z jednym samotnym wierzchołkiem ciężko określić jego odległość od pozostałych.(Brak krawędzi)
Gdy już ustaliliśmy, że graf jest spójny możemy wywnioskować, że istnieje ścieżka dla dowolnych dwóch wierzchołków długości co najwyżej n-1.(graf o |V|=n) Jeżeli ścieżka jest najdłuższa dla tych wierzchołków to z tego wynika, że są to wierzchołki skrajne.Wystarczy, że weźmiemy pod lupę wierzchołek ze środka wyżej omawianej ścieżki.Z tego wierzchołka jest najdalej do wierzchołka skrajnego tj. co najwyżej n/2 długości.To oczywiście nie jest dowód , można podpiąć pod szkic.Właściwy dowód to dwie linijki z wykorzystaniem własności metryki.Nie podam go oczywiście bo nic nie dałaś od siebie w tym temacie.Zero prób czegokolwiek.Pozdrawiam.
Zacznę od tego, że graf musi być spójny bo w definicji promienia występuję odległość między wierzchołkami.A jak odległość to i krawędzie.W przypadku grafu niespójnego z jednym samotnym wierzchołkiem ciężko określić jego odległość od pozostałych.(Brak krawędzi)
Gdy już ustaliliśmy, że graf jest spójny możemy wywnioskować, że istnieje ścieżka dla dowolnych dwóch wierzchołków długości co najwyżej n-1.(graf o |V|=n) Jeżeli ścieżka jest najdłuższa dla tych wierzchołków to z tego wynika, że są to wierzchołki skrajne.Wystarczy, że weźmiemy pod lupę wierzchołek ze środka wyżej omawianej ścieżki.Z tego wierzchołka jest najdalej do wierzchołka skrajnego tj. co najwyżej n/2 długości.To oczywiście nie jest dowód , można podpiąć pod szkic.Właściwy dowód to dwie linijki z wykorzystaniem własności metryki.Nie podam go oczywiście bo nic nie dałaś od siebie w tym temacie.Zero prób czegokolwiek.Pozdrawiam.