Proste zadanko ;>

0

Spróbujcie to rozwiązać, jeżeli w ogóle to możliwe [???] : http://www.emkej10.piwko.pl/zadanie.htm

0

Problem sprowadza się do sprawdzenia, czy graf o o krawędziach (ciężko mi tu macierze rysować :P):
1-2
1-2
1-3
1-3
1-4
1-4
1-5
1-5
1-6
2-3
2-6
3-4
3-6
4-5
4-6
5-6
zawiera drogę Hamiltona.
Tak na oko to nie :(

0

Hmm już to kiedyś widziałem i jest to niemożliwe do wykonania według jakiejś zasady kogoś tam (mówiła ona coś o mostach i ich parzystości czy coś takiego). Poza tym nauczyciel matmy mojej koleżanki powiedział, że można to rozwiązać tylko przeprowadzając dwie symetryczne linie według środkowej pionowej ściany.

0

MoH: o mostach to jest cykl Eulera. Tutaj tego raczej nie da się zastosować. Cykl Eulera jest jest wówczas, gdy przez wszystkie punkty grafu przejdzie się dokładnie raz i wróci w to samo miejsce (przy drodze nie ma tego drugiego ograniczenia).
Jeżeli za punkty grafu wziąłbyś ścianki, które ma przekroczyć, to możnaby dojść do ścianki i wrócić jeszcze w tym samym "pomieszczeniu". I akurat drogę Eulera możnaby tutaj bardzo łatwo znaleźć.
Jeżeli za wierzchołki przjąłbyś pomieszczenia, to mógłbyś pominąć niektóre ścianki przy przechodzeniu przez wierzchołki.
Dlatego właśnie trzeba ścianki oznaczyć jako krawędzie (bo tylko w jedną stronę się przechodzi) i przejść po wszystkich krawędziach dokładnie raz (czyli znaleźć drogę Hamiltona).
Jak ktoś znajdzie algorytm stwierdzający, czy w grafie jest droga (lub cykl) Hamiltona bez sprawdzania wszystkich możliwości, to niech da znać ;)

0

Dryobates: może i nie da sie tego zastosować, ale i tak wiem, że tego sie chyba nie da rozwiązać

0

http://vogel.iglu.cz/bonus/images/zad1.jpg

//Coś Ci się rozlała czerwona farbka po lewej [rotfl] - m.M

1 użytkowników online, w tym zalogowanych: 0, gości: 1