Mam taki problem z zadaniem z dyskretnej, a w zasadzie nie jestem pewny pewnej rzeczy. Tu jest treść tego zadania:
. Początek tego zadania brzmi:
Pracujesz w firmie logistycznej. Tabela obok przedstawia odległości pomiędzy miastami powiatowymi w województwie
świętokrzyskim, a gwiazdką zaznaczone są istniejące połączenia drogowe.
. Dalsza część tego zadania brzmi:
Odpowiedz na pytanie czy możliwy jest przejazd przez wszystkie odcinki dróg, który rozpoczyna się w Kielcach, w ten sposób,aby każdy odcinek drogi przebyty był tylko jeden raz.
. Rozumiem że wyraz wszystkie odnosi się do stworzenia grafu, który będzie zawierał połączenia między miastami oznaczonymi tylko gwiazdką. Dziękuje.
Niekoniecznie. Jeśli więcej niż dwa miasta (a tak jest w zadaniu) mają nieparzystą liczbę połaczeń (czyli wierzchołki grafu odpowiadające miastom są nieparzystego stopnia) to taka droga (linia jednokreślna) nie istnieje.
Rozumiem że musiałbym stworzyć graf i na tej podstawie starać się znaleźć w nim drogę Eulera? Ok w porządku. Tylko chciałbym zapytać czy ja ten graf musiałbym stworzyć poprzez połączenie jakiegoś miasta ze wszystkimi np. tak jak tutaj zaznaczyłem:
. Czy tylko łączyć te miasta z gwiazdką np.:
. Według którego schematu powinienem zrobić ten graf. Pierwsze zdjęcie(w którym łącze Kielce ze wszystkimi miastami, które tam zaznaczyłem) czy drugie(w którym łącze Kielce z miastami oznaczonymi gwiazdką, które też zaznaczyłem) i tak z każdym miastem po kolei idąc od góry(Kielce), kończąc na dole(Opatów).
Dobrze to może inaczej. Patrząc się na treść tego zadania, to które rozwiązanie będzie poprawne? Pokaże to na przykładzie.
-Graf, który składa się z połączonych ze sobą miast(takich, które mają gwiazdke w nazwie)? Np.
-Czy graf, w którym łącze każdą miejscowość ze sobą? Np.
Chociaż w moim subiektywnym odczuciu łączenie tego miasta z każdym to jest bezsens. No ale wole zapytać kogoś bardziej doświadczonego.
Sorry, nie bywam regularnie i stąd opóźniona odpowiedź.
Oczywiście, w grafie łączysz krawędzią miasta z połączeniem drogowym, czyli z odległościami z gwiazdką.
Moim zdaniem graf jest zbędny, skoro już z kilku pierwszych miast Kielce, Starachowice i Skarżysko mają po trzy drogi z nich wychodzące.
