Czy istnieje graf:
a) \(\displaystyle{ 10}\)-regularny
b) \(\displaystyle{ 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 \(\displaystyle{ k=10}\), \(\displaystyle{ |V|=18}\), \(\displaystyle{ 2*10+1=21!=18}\) czyli nie istnieje ?
Nie mam innego pomysłu, stąd moje pytanie.
graf k-refularny a istnienie cyklu hamiltona
- arek1357
- Użytkownik
- Posty: 5747
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 526 razy
graf k-refularny a istnienie cyklu hamiltona
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.
A u ciebie tak właśnie jest.
-
- Użytkownik
- Posty: 98
- Rejestracja: 27 wrz 2011, o 20:37
- Płeć: Mężczyzna
- Lokalizacja: Wroclaw
- Podziękował: 7 razy
graf k-refularny a istnienie cyklu hamiltona
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: \(\displaystyle{ 20 \ge 18}\). Dziękuje.