forum.zadania.info

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.

Ok. Wielkie dzięki za pomoc. Tylko tyle chciałem się dowiedzieć. Dzięki