szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 29 sty 2017, o 00:50 
Użytkownik

Posty: 2
Lokalizacja: Lublin
Dobry wieczór. Chciałbym prosić o ocenienie czy moje rozumowanie przy tym zadaniu jest prawidłowe. Treść "Sprawdź czy założenia twierdzenia Orego są spełnione w n-wierzchołkowym kole".
Założenie 1:
Założenie jest spełnione, bo n-wierzochłkowe koło zostało utworzone z (n-1) wierzchołkowego obwodu, który jest grafem regularnym stopnia 2, a graf regularny jest z definicji grafem prostym, zatem n-wierzchołkowe koło również jest gryfem prostym.
Założenie 2: |V(g)|=n>=3
n-wierzchołkowe koło jest utworzone z (n-1)-wierzchołkowego obwodu. Minimalna ilość wierzchołków w (n-1)-wierzchołkowym obwodzie wynosi 3, więc minimalna ilość wierzchołków w n-wierzchołkowym kole wynosi 3+1=4 > 3. Więc |V(g1)|=n>3, zatem założenie jest spełnione.
Założenie 3:
Dla każdej pary dowolnych wierzchołków v i w nie połączonych krawędzią d(v)+d(w)>=n
W n-wierzchołkowym kole są jest n-1 wierzchołków 3 stopnia oraz 1 wierzchołek (n-1)-stopnia, jednak jest on połączony krawędzią z każdym wierzchołkiem. Zatem rozpatrujemy wyłącznie jeden przypadek: a i b - niesąsiadujące ze sobą wierzchołki, d(a)=3 i d(b)=3. 3+3=6, więc jeśli n<=6, to założenie jest spełnione i droga Hammiltona istnieje dla tego grafu, a jeśli n>6, to założenie nie jest spełnione i droga Hamiltona nie istnieje.
Pozdrawiam!
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 31 sty 2017, o 10:42 
Użytkownik
Avatar użytkownika

Posty: 1229
Z niespełnienia założeń nie możesz wnioskować, że nie jest spełniona teza twierdzenia. Nie myl twierdzenia z twierdzeniem odwrotnym. Reszta jest ok.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 twierdzenie o rekurencji uniwersalne  tukanik  0
 Element największy zbioru (Twierdzenie Ore)  lgtco99  3
 [Dyskretna/Kombinacje] Wzór - twierdzenie do udowodnienia  Szczawik  0
 twierdzenie o długości kolejnych boków czworokąta  kolega buahaha  1
 Twierdzenie o pierwiastkach wymiernych  pvnrt  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl