szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 9 lip 2015, o 13:21 
Użytkownik

Posty: 25
Lokalizacja: Taknie
Witam. Jak zabrać się za takie zadanie, w którym mam rozstrzygnąć dla jakich m graf K_{10,m} posiada ścieżkę Hamiltona. z góry dziękuję za pomoc.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 23 lip 2015, o 08:29 
Gość Specjalny

Posty: 3047
Lokalizacja: Gołąb
m=9,10,11
Niech graf ma dwie składowe X,Y takie, że \left|X\right|=10 i \left|Y\right|=m. Graf jest dwudzielny, więc zawsze będziemy przechodzić z jednej składowej do drugiej. Wierzchołki nie mogą się powtarzać. Możliwe są dwa przypadki:
1. Startujemy z jakiegokolwiek wierzchołka z X. Wówczas, żeby obejść pozostałe wierzchołki z X potrzeba nam 9 razy przejść przez jakiś wierzchołek z Y. Stąd m=9. Odwiedzając ostatni wierzchołek w X możemy jeszcze z niego pójść do składowej Y (jeśli się da), co daje możliwość m=10. Wtedy też istnieje cykl Hamiltona.
2. Startujemy z wierzchołka w Y. Musimy 10 razy być w składowej X więc też 10 razy wychodzimy ze składowej Y. Daje to możliwość m=10, którą znaliśmy już wcześniej. Tymczasem z ostatniego wierzchołka w X możemy pójść jeszcze do Y, co daje jeszcze możliwość m=11.

I to by było na tyle. W razie potrzeby bardziej szczegółowych wyjaśnień pytaj.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Sprawdzanie obecności cyklu Eulera i Hamiltona w grafie  AlAmilar  3
 Dowód na istnienie grafu Hamiltona.  karpiuch  7
 Potęgi grafów i cykle hamiltona  rubik1990  1
 Planarność, izomorfizm, cykl Hamiltona  jeth  5
 Cykl Hamiltona w grafie Petersena  Sage!  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl