Witam, mam takie zadanie do rozwiązania:
Wykazać, że jeżeli \(\displaystyle{ G}\) jest niezorientowanym grafem regularnym stopnia \(\displaystyle{ d}\) o \(\displaystyle{ n=2d-1}\) wierzchołkach, to \(\displaystyle{ G}\) jest hamiltonowski. Zweryfikować to dla grafu o \(\displaystyle{ d=4}\).
Mógłby mi ktoś pomóc je rozwiązać? Za wszelkie wskazówki będę bardzo wdzięczny
graf Hamiltona
-
kerajs
- Użytkownik
- Posty: 8714
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 338 razy
- Pomógł: 3434 razy
Re: graf Hamiltona
Liczba krawędzi w grafie G to: \(\displaystyle{ \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ż \(\displaystyle{ {k-1 \choose 2}+2}\)
Wystarczy więc sprawdzić dla jakich d zachodzi:
\(\displaystyle{ {(2d-1)-1 \choose 2}+2 \le d^2- \frac{d}{2}}\)
stąd:
\(\displaystyle{ 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.
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ż \(\displaystyle{ {k-1 \choose 2}+2}\)
Wystarczy więc sprawdzić dla jakich d zachodzi:
\(\displaystyle{ {(2d-1)-1 \choose 2}+2 \le d^2- \frac{d}{2}}\)
stąd:
\(\displaystyle{ 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.