szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 13 maja 2010, o 01:49 
Użytkownik

Posty: 153
Lokalizacja: Wroclaw
Mam zadanie:
Cytuj:
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):
Obrazek
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?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 13 maja 2010, o 02:05 
Użytkownik

Posty: 9836
Lokalizacja: Bydgoszcz
filip.wroc napisał(a):
okazalo sie, ze jest 3-regularny.

Nie (choć narysowałeś go dobrze).

Cytuj:
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.

Cytuj:
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:
000-001-010-101-011-111-110-100-000
można wywnioskować rozmieszczenie:
01011100
Spróbuj sam zastanowić się jak to działa.

Q.
Góra
Mężczyzna Offline
PostNapisane: 13 maja 2010, o 02:37 
Użytkownik
Avatar użytkownika

Posty: 683
Lokalizacja: Gliwice
ups
Góra
Mężczyzna Offline
PostNapisane: 13 maja 2010, o 13:57 
Użytkownik

Posty: 153
Lokalizacja: Wroclaw
Qń napisał(a):
filip.wroc napisał(a):
okazalo sie, ze jest 3-regularny.

Nie (choć narysowałeś go dobrze).

Ups. Teraz widze, ze sa wierzcholki stopnia 3 i 4. Moj blad.
Cytuj:
Cytuj:
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.

Cytuj:
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.
Góra
Mężczyzna Offline
PostNapisane: 5 maja 2015, o 21:00 
Użytkownik

Posty: 68
Lokalizacja: Opole
Czy tak powinien wygladac ten graf?
http://www.img.pl/nQfh
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Minimalna kwota jaką powinno pobrać kasyno za grę  kk12345  7
 cykle hamiltona - grafy dwudzielne-problem nadal aktualny  mateuss  0
 cykl Eulera, krawędziowo rozłączne ścieżki  anilahcim  0
 Graf Hamiltona i krawędź cięcia - zadanie 16  moncq  1
 Permutacje cykl  timus221  19
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl