Cykl Hamiltona gdy go byc nie powinno

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
filip.wroc
Użytkownik
Użytkownik
Posty: 153
Rejestracja: 17 sty 2010, o 15:37
Płeć: Mężczyzna
Lokalizacja: Wroclaw
Pomógł: 13 razy

Cykl Hamiltona gdy go byc nie powinno

Post autor: filip.wroc »

Mam zadanie:
5.Rozmieść zera i jedynki na okręgu tak, by każda trzycyfrowa liczba dwójkowa była ciągiem trzech kolejnych symboli na okręgu.

Wskazówka: znajdź cykl Hamiltona w grafie mającym zbiór wierzchołków BxBxB, gdzie B={0,1}, oraz mającym krawędź między (v1,v2,v3) i (w1,w2,w3) , jeśli (v1,v2) = (w2,w3) lub (v2,v3) = (w1,w2) .
No wiec rozrysowałem sobie ten graf i okazało się, że jest 3-regularny. Z twierdzenia Ore wynika, że nie będzie tu cyklu Hamiltona.
I teraz mam zagwozdkę - ja źle narysowałem graf, źle zrozumiałem tw. Ore, czy odpowiedzią jest 'nie da rady'?
Graf, który rozrysowałem (pominąłem pętle, bo te nic nie dadzą w tym zadaniu):

Znalazłem za to cykl eulerowski:
001
011
111
110
011
101
110
100
000
001
010
101
010
100
001
Czy to błąd w zadaniu?
Po co w ogóle ta wskazówka, jeżeli można po prostu zamieścić 24 cyfry na okręgu, na zasadzie 000 001 010 011 100 101 110 111 (tu się styka z 000)? Może źle zrozumiałem treść zadania?
Ostatnio zmieniony 13 maja 2010, o 14:41 przez miki999, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Użytkownik
Użytkownik
Posty: 9833
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2632 razy

Cykl Hamiltona gdy go byc nie powinno

Post autor: »

filip.wroc pisze:okazalo sie, ze jest 3-regularny.
Nie (choć narysowałeś go dobrze).
Z twierdzenia Ore wynika, ze nie bedzie tu cyklu Hamiltona.
Nie, twierdzenie Ore mówi nam wyłącznie o warunku wystarczającym do istnienia cyklu Hamiltona, ale nie jest to warunek konieczny, tzn. może istnieć cykl Hamiltona w grafie, który tego warunku nie spełnia.
Po co w ogole ta wskazowka, jezeli mozna po prostu zamiescic 24 cyfry na okregu
W treści zadania powinno być napisane, że tych zer i jedynek na okręgu ma być w sumie osiem (względnie: że ma być możliwie mało).

Z cyklu Hamiltona:
\(\displaystyle{ 000-001-010-101-011-111-110-100-000}\)
można wywnioskować rozmieszczenie:
\(\displaystyle{ 01011100}\)
Spróbuj sam zastanowić się jak to działa.

Q.
Xitami

Cykl Hamiltona gdy go byc nie powinno

Post autor: Xitami »

ups
filip.wroc
Użytkownik
Użytkownik
Posty: 153
Rejestracja: 17 sty 2010, o 15:37
Płeć: Mężczyzna
Lokalizacja: Wroclaw
Pomógł: 13 razy

Cykl Hamiltona gdy go byc nie powinno

Post autor: filip.wroc »

Qń pisze:
filip.wroc pisze:okazalo sie, ze jest 3-regularny.
Nie (choć narysowałeś go dobrze).
Ups. Teraz widze, ze sa wierzcholki stopnia 3 i 4. Moj blad.
Z twierdzenia Ore wynika, ze nie bedzie tu cyklu Hamiltona.
Nie, twierdzenie Ore mówi nam wyłącznie o warunku wystarczającym do istnienia cyklu Hamiltona, ale nie jest to warunek konieczny, tzn. może istnieć cykl Hamiltona w grafie, który tego warunku nie spełnia.
Tego nie zauwazylem. Rozumiem juz moj blad.
\(\displaystyle{ 01011100}\)
Spróbuj sam zastanowić się jak to działa.
Q.
Sam tego cyklu nie umialem znalesc, ale wiem skad sie bierze rozwiazanie.
Gdy kolo siebie stoja 2 takie same pary cyfr to po prostu 'sklejamy' je razem (np 000 - 001 00 jest dwa razy, wiec dostajemy 0 00 1).

Dzieki za pomoc.
lgamon
Użytkownik
Użytkownik
Posty: 67
Rejestracja: 9 lis 2014, o 22:23
Płeć: Mężczyzna
Lokalizacja: Opole
Podziękował: 4 razy

Cykl Hamiltona gdy go byc nie powinno

Post autor: lgamon »

Czy tak powinien wygladac ten graf?
ODPOWIEDZ