szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 4 maja 2017, o 22:00 
Użytkownik

Posty: 319
Lokalizacja: Gorzów Wlkp.
Witam,

Mam takie zadanko
Cytuj:
Korzystając z twierdzenia Diraca uzasadnij, że jeżeli G ma przynajmniej 2 wierzchołki i \delta(G)\ge\frac{V(G)-1}{2} to G ma ścieżkę Hamiltona.


Znam twierdzenie Diraca i z tego co wiem tyczy się one cykli Hamiltona, a nie ścieżki. Trochę nie za bardzo wiem jak z niego skorzystać tym bardziej, że mamy tu do czynienia z 2 wierzchołkami, a twierdzenie Diraca można zastosować gdy mamy do czynienia z 3.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 5 maja 2017, o 11:30 
Użytkownik
Avatar użytkownika

Posty: 1227
No dobra, to zauważ, że jeśli wezmę graf, który ma cykl Hamiltona i wyrzucę z tego grafu jeden wierzchołek, to dostanę graf, który ma ścieżkę Hamiltona, prawda?
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Wariacje z powtorzeniami : wzor  hipero  3
 Ile monitorów można wybrać ?? jaki wzor?  Anonymous  1
 korzystając z indukcji mat. udowodnij Pn = n!  nelik1987  1
 [Dyskretna/Kombinacje] Wzór - twierdzenie do udowodnienia  Szczawik  0
 wzór newtona  net  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl