szukanie zaawansowane
 [ Posty: 1 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 12 sie 2015, o 18:44 
Użytkownik

Posty: 394
Lokalizacja: Warszawa
1.Twierdzenie Diraca jest najlepsze w swojej klasie, tzn. w założeniu \delta \ge  \frac{p}{2}
liczby \frac{p}{2} nie można zastąpić mniejszą (to znaczy można,ale otrzyma się fałszywe twierdzenie.

2. Jeśli \left| V(G)\right| \ge 5 i każdy podgraf indukowany w G przez 5 wierzchołków jest 2-spójny to G
ma cykl Hamiltona.

3.G jest dwuspójny i każdy podgraf indukowany w G przez 3 wierzchołki ma co najmniej jedna krawędź to G ma cykl Hamiltona.


2.
Bierzemy dowolny wierzchołek x grafu G.
Przypuśćmy,że istnieją 3 wierzchołki z,t,u różne od x z którymi x nie sąsiaduje. Wówczas,dla każdego w \neq x,z,t,u w podgrafie indukowanym przez \left\{ w,x,z,t,u\right\} x ma stopień 1 (połączony z w) a więc podgraf ten nie jest dwuspójny. Wiec wierzchołki takie nie istnieją,czyli każdy wierzchołek x,oprócz samego siebie, nie sąsiaduje z co najwyżej dwoma innymi wierzchołkami. Stąd dla każdego x,
deg(x) \ge p-3 a ponieważ p \ge 5,więc deg(x) \ge  \frac{p}{2} i z twierdzenia Diraca mamy cykl Hamiltona.


Proszę o wskazówki do 2 pozostałych i sprawdzenie tego :)
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 1 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Zadania testowe - pemutacje, zwracanie :)  Anonymous  2
 dziwne zadanie z matematyki dyskretnej  mkarwin  1
 takze dziwne zadanie z matematyki dyskretnej  mkarwin  5
 3 zadania...  Ciapanek  2
 Zadania z kombinatoryki  neworder  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl