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: 6670
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 - zadanie 2  mol_ksiazkowy  5
 graf spójny - zadanie 2  aGabi94  1
 Kolorowanie wierzchołków (graf z petlami)  sputnik1957  3
 Czy graf jest dwudzielny?  blade  6
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl