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.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) .
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?