szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 16 paź 2015, o 15:09 
Użytkownik

Posty: 98
Lokalizacja: Wroclaw
Czy istnieje graf:
a) 10-regularny
b) 18 wierzchołków
c) Niezawiera cyklu Hamiltona

Znam twierdzenie Nash'a-Williams'a, tylko nie wiem czy na podstawie tego, że niezachodzi warunek mogę stwierdzić, że nie istnieje taki graf, czyli, że mogę użyć twierdzenie w drugą stronę ? czyli k=10, |V|=18, 2*10+1=21!=18 czyli nie istnieje ?
Nie mam innego pomysłu, stąd moje pytanie.
Góra
Mężczyzna Offline
PostNapisane: 16 paź 2015, o 19:49 
Użytkownik
Avatar użytkownika

Posty: 3273
Lokalizacja: blisko
Znam twierdzenie, które mówi, że jeżeli stopień każdego wierzchołka jest większy od połowy ilości wierzchołków to graf jest hamiltonowski czyli zawiera cykl Hamiltona!
A u ciebie tak właśnie jest.
Góra
Mężczyzna Offline
PostNapisane: 16 paź 2015, o 22:35 
Użytkownik

Posty: 98
Lokalizacja: Wroclaw
No tak, faktycznie można skorzystać z twierdzenie Diraca, ja użyłem Orego,i faktycznie dla dowolnych dwóch wierzchołków suma spełnia warunek: 20 \ge 18. Dziękuje.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 3 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 [Teoria grafów] Poprawność dowodu istnienia cyklu Hamiltona  kapsl0k  0
 Udowodnij istnienie - zadanie 3  Dario1  1
 Graf nie izomorficzny regularny 3 stopnia z 9 wierzchołkami  winfast29  3
 Graf skierowany odpowiadający macierzy  alberthus  1
 W grafie 2-spójnym każde dwa wierzchołki należą do cyklu  rafalpw  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl