Witam,
mam problem z takim zadaniem:
Wielki matematyk szwajcarski Leonard Euler (XVIII w.) mieszkał w Królewcu. Części tegi miasta, przez które przepływała rzeka, były połączone siedmioma mostami:
Euler zauważył, że nie można tak zaplanować spaceru, aby przejść przez wszystkie mosty tylko jeden raz (sprawdź to!). Czy można dobudować jeden most tak, aby taki spaceer był możliwy? Jeśli tak, to dorysuj go i zaznacz przykładową trasę takiego spaceru.
Ma ktoś jakiś pomysł?:)
Mosty królewieckie
-
saaloomeeaa_2016
- Użytkownik
- Posty: 1
- Rejestracja: 2 wrz 2016, o 14:19
- Płeć: Kobieta
- Lokalizacja: Rzeszów
Mosty królewieckie
Ostatnio zmieniony 2 wrz 2016, o 17:03 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Staraj się lepiej dobierać nazwy tematów, tak by wskazywały o czym jest treść zadania. Temat umieszczony w złym dziale.
Powód: Staraj się lepiej dobierać nazwy tematów, tak by wskazywały o czym jest treść zadania. Temat umieszczony w złym dziale.
-
kerajs
- Użytkownik
- Posty: 8585
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 307 razy
- Pomógł: 3351 razy
Mosty królewieckie
Jak przypuszczam chodzi o inny dowód niż rysunkowy.
Oznaczę brzegi przez P(rawy), L(ewy), a wyspy przez G(órna) i D(olna). Mosty niech będą kamieniami domina. Wtedy mam kamienie PD, PD, PG, GD, DL, DL, GL. Układając ścieżkę przejścia przez kolejne mosty, podobnie jak układając kamienie domina, elementy tak samo oznaczone są obok siebie. Wtedy pełna ścieżka ma :
a) Parzystą ilość każdego elementu, i jest wtedy zamkniętą pętlą.
b) Nieparzystą ilość dwóch elementów które są na końcach ścieżki i parzysta ilość elementów pozostałych.
Niestety w Królewcu mosty mają nieparzystą ilość czterech elementów co nie spełnia a), b) więc ścieżka (układ domina) nie istnieje.
Wystarczy dodać jeden most aby dostać sytuację b)
Np. Dodaję PD i układam przykładowe ścieżki (nieparzyste L i G muszą być na końcach) :
LD DP PD DL LG GD DP PG albo LG GD DL LD DP PD DP PG
Oznaczę brzegi przez P(rawy), L(ewy), a wyspy przez G(órna) i D(olna). Mosty niech będą kamieniami domina. Wtedy mam kamienie PD, PD, PG, GD, DL, DL, GL. Układając ścieżkę przejścia przez kolejne mosty, podobnie jak układając kamienie domina, elementy tak samo oznaczone są obok siebie. Wtedy pełna ścieżka ma :
a) Parzystą ilość każdego elementu, i jest wtedy zamkniętą pętlą.
b) Nieparzystą ilość dwóch elementów które są na końcach ścieżki i parzysta ilość elementów pozostałych.
Niestety w Królewcu mosty mają nieparzystą ilość czterech elementów co nie spełnia a), b) więc ścieżka (układ domina) nie istnieje.
Wystarczy dodać jeden most aby dostać sytuację b)
Np. Dodaję PD i układam przykładowe ścieżki (nieparzyste L i G muszą być na końcach) :
LD DP PD DL LG GD DP PG albo LG GD DL LD DP PD DP PG
-
Mruczek
- Użytkownik
- Posty: 1114
- Rejestracja: 26 paź 2008, o 19:43
- Płeć: Mężczyzna
- Podziękował: 23 razy
- Pomógł: 157 razy
Mosty królewieckie
Oj tam z tym dominem... - przeróbmy te mosty i wyspy na graf nieskierowany.
To znaczy niech każda wyspa (białe pole, czy tam pole domina) będzie wierzchołkiem, a mosty (czy tam kostki domina) krawędziami łączącymi wierzchołki. Problem przedstawiony w tym zadaniu dotyczy ścieżki Eulera, czyli ścieżki przechodzącej przez każdą krawędź grafu jeden raz.
Ścieżka Eulera istnieje gdy graf jest spójny (a u nas tak jest) oraz: każdy wierzchołek grafu ma stopień (czyli ilość krawędzi z którą jest połączony) parzysty (i wtedy jest cyklem) lub gdy dokładnie dwa wierzchołki mają stopień nieparzysty. Dowód tego faktu jak i algorytm generowania ścieżki / cyklu Eulera można znaleźć np. w książce "Wprowadzenie do teorii grafów" Wilsona.
U nas cztery wierzchołki mają nieparzysty stopień, więc ścieżka Eulera nie istnieje. Dodając dowolny jeden most, dodajemy jedną krawędź, która powoduje, że dokładnie dwa wierzchołki mają stopień nieparzysty i dokładnie dwa stopień parzysty, więc wtedy ścieżka Eulera istnieje.
To znaczy niech każda wyspa (białe pole, czy tam pole domina) będzie wierzchołkiem, a mosty (czy tam kostki domina) krawędziami łączącymi wierzchołki. Problem przedstawiony w tym zadaniu dotyczy ścieżki Eulera, czyli ścieżki przechodzącej przez każdą krawędź grafu jeden raz.
Ścieżka Eulera istnieje gdy graf jest spójny (a u nas tak jest) oraz: każdy wierzchołek grafu ma stopień (czyli ilość krawędzi z którą jest połączony) parzysty (i wtedy jest cyklem) lub gdy dokładnie dwa wierzchołki mają stopień nieparzysty. Dowód tego faktu jak i algorytm generowania ścieżki / cyklu Eulera można znaleźć np. w książce "Wprowadzenie do teorii grafów" Wilsona.
U nas cztery wierzchołki mają nieparzysty stopień, więc ścieżka Eulera nie istnieje. Dodając dowolny jeden most, dodajemy jedną krawędź, która powoduje, że dokładnie dwa wierzchołki mają stopień nieparzysty i dokładnie dwa stopień parzysty, więc wtedy ścieżka Eulera istnieje.