graf hamiltonowski z liczba krawedzi

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Awatar użytkownika
kamil.jack
Użytkownik
Użytkownik
Posty: 86
Rejestracja: 10 lut 2008, o 14:27
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 27 razy

graf hamiltonowski z liczba krawedzi

Post autor: kamil.jack » 10 cze 2008, o 16:50

Niech G=(V,E) bedziue grafem gdzie |V|=n i \(\displaystyle{ |E|> \frac{n^2-3n+4}{2}}\). Pokazac ze G jest hamiltonowski
b) podac przyklad grafu \(\displaystyle{ |E|= \frac{n^2-3n+4}{2}}\), ktory nei jest hamiltonowski

Gość Specjalny
Gość Specjalny
Posty: 9834
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2626 razy

graf hamiltonowski z liczba krawedzi

Post autor: » 11 cze 2008, o 00:11

Dowód do a) masz tutaj:
http://pl.wikipedia.org/wiki/Twierdzeni ... onowski%29

Kontrprzykładu do b) na razie nie umiem znaleźć - by to zrobić należy dla jakiegoś \(\displaystyle{ n}\) z grafu pełnego \(\displaystyle{ K_n}\) usunąć \(\displaystyle{ n-2}\) krawędzi tak, żeby w nowopowstałym grafie nie istniała droga Hamiltona. Ale cholera wie jak to zrobić i dla jakiego \(\displaystyle{ n}\) .

Q.

ODPOWIEDZ