Pokaż, że w grafie spójnym dwie drogi maksymalnej długości mają zawsze jeden wspólny wierzchołek.
Proszę o pomoc.
Najdłuższe drogi w grafie.
-
Gacuteek
- Użytkownik
- Posty: 1075
- Rejestracja: 13 mar 2008, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 5 razy
- Pomógł: 272 razy
Najdłuższe drogi w grafie.
Nie wprost
Przypuśćmy że dwie drogi maksymalnej długości nie mają wspólnego wierzchołka. Oznaczmy te drogi \(\displaystyle{ D_{1}}\) i \(\displaystyle{ D_{2}}\)(zbiory elementów drogi). Niech \(\displaystyle{ d_{1}}\) będzie dowolnym punktem z drogi \(\displaystyle{ D_{1}}\) zaś \(\displaystyle{ d_{2}}\) dowolnym punktem z drogi \(\displaystyle{ D_{2}}\). Skoro graf jest spójny to istnieje droga z \(\displaystyle{ d_{1}}\) do \(\displaystyle{ d_{2}}\). Weźmy koniec drogi \(\displaystyle{ D_{1}}\) taki , którego odległość od \(\displaystyle{ d_{1}}\) jest większa ( bez straty ogólności) , nazwijmy go \(\displaystyle{ d_{k}}\) , tak samo postępujemy z drogą \(\displaystyle{ D_{2}}\) i wybrany koniec nazywamy \(\displaystyle{ d_{l}}\). Odległość wierzchołków \(\displaystyle{ d_{1}}\) i \(\displaystyle{ d_{2}}\) jest co najmniej 1, zaś odległość \(\displaystyle{ d_{1}}\) od \(\displaystyle{ d_{k}}\) oraz \(\displaystyle{ d_{2}}\) od \(\displaystyle{ d_{l}}\) są równe co najmniej długości połowy drogi \(\displaystyle{ D_{1}}\). Tak skonstruowana droga \(\displaystyle{ d_{k} -d_{l}}\) jest dłuższa od drogi \(\displaystyle{ D_{1}}\) oraz \(\displaystyle{ D_{2}}\) o co najmniej jeden wierzchołek. Zatem dostajemy sprzeczność z założeniem. Zatem dwie drogi maksymalnej długości w grafie spójnym mają wspólny wierzchołek.
Pozdrawiam MG
Przypuśćmy że dwie drogi maksymalnej długości nie mają wspólnego wierzchołka. Oznaczmy te drogi \(\displaystyle{ D_{1}}\) i \(\displaystyle{ D_{2}}\)(zbiory elementów drogi). Niech \(\displaystyle{ d_{1}}\) będzie dowolnym punktem z drogi \(\displaystyle{ D_{1}}\) zaś \(\displaystyle{ d_{2}}\) dowolnym punktem z drogi \(\displaystyle{ D_{2}}\). Skoro graf jest spójny to istnieje droga z \(\displaystyle{ d_{1}}\) do \(\displaystyle{ d_{2}}\). Weźmy koniec drogi \(\displaystyle{ D_{1}}\) taki , którego odległość od \(\displaystyle{ d_{1}}\) jest większa ( bez straty ogólności) , nazwijmy go \(\displaystyle{ d_{k}}\) , tak samo postępujemy z drogą \(\displaystyle{ D_{2}}\) i wybrany koniec nazywamy \(\displaystyle{ d_{l}}\). Odległość wierzchołków \(\displaystyle{ d_{1}}\) i \(\displaystyle{ d_{2}}\) jest co najmniej 1, zaś odległość \(\displaystyle{ d_{1}}\) od \(\displaystyle{ d_{k}}\) oraz \(\displaystyle{ d_{2}}\) od \(\displaystyle{ d_{l}}\) są równe co najmniej długości połowy drogi \(\displaystyle{ D_{1}}\). Tak skonstruowana droga \(\displaystyle{ d_{k} -d_{l}}\) jest dłuższa od drogi \(\displaystyle{ D_{1}}\) oraz \(\displaystyle{ D_{2}}\) o co najmniej jeden wierzchołek. Zatem dostajemy sprzeczność z założeniem. Zatem dwie drogi maksymalnej długości w grafie spójnym mają wspólny wierzchołek.
Pozdrawiam MG