szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
 Tytuł: graf Hamiltona
PostNapisane: 13 sty 2019, o 21:21 
Użytkownik

Posty: 126
Lokalizacja: Polska
Witam, mam takie zadanie do rozwiązania:

Wykazać, że jeżeli G jest niezorientowanym grafem regularnym stopnia d o n=2d-1 wierzchołkach, to G jest hamiltonowski. Zweryfikować to dla grafu o d=4.

Mógłby mi ktoś pomóc je rozwiązać? Za wszelkie wskazówki będę bardzo wdzięczny :)
Góra
Mężczyzna Offline
PostNapisane: 14 sty 2019, o 11:40 
Użytkownik
Avatar użytkownika

Posty: 6665
Liczba krawędzi w grafie G to: \frac{d(2d-1)}{2}=d^2- \frac{d}{2}
Ponieważ liczba krawędzi może być tylko liczbą naturalną to liczba d musi być parzysta.

Tw.
Graf prosty o k wierzchołkach jest hamiltonowskim gdy jego liczba krawędzi jest nie mniejsza niż {k-1 \choose 2}+2

Wystarczy więc sprawdzić dla jakich d zachodzi:
{(2d-1)-1 \choose 2}+2 \le d^2- \frac{d}{2}
stąd:
d \ge  \frac{7}{4}
czyli każdy G o parzystym d jest hamiltonowski.

Rysunki:
Moim zdaniem istnieją dwa nieizomorficzne grafy G o 7 wierzchołkach, z których wychodzą po 4 krawędzie. Narysuj je i wskaż na nich ścieżki Hamiltona.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Graf Hamiltona  lukabesoin  2
 graf petersena nie jest hamiltonowski dowód??  alefx  2
 Sprawdzanie obecności cyklu Eulera i Hamiltona w grafie  AlAmilar  3
 Graf Samodopełniający  Anonymous  1
 Graf pełny dwudzielny - obchód Eulera, cykl Hamiltona.  WhiteRabbit7  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl