szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna
PostNapisane: 10 cze 2008, o 16:50 
Użytkownik
Avatar użytkownika

Posty: 86
Lokalizacja: Warszawa
Niech G=(V,E) bedziue grafem gdzie |V|=n i |E|> \frac{n^2-3n+4}{2}. Pokazac ze G jest hamiltonowski
b) podac przyklad grafu |E|= \frac{n^2-3n+4}{2}, ktory nei jest hamiltonowski
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019
Góra
Mężczyzna
PostNapisane: 11 cze 2008, o 00:11 
Użytkownik

Posty: 9834
Lokalizacja: Bydgoszcz
Dowód do a) masz tutaj:
http://pl.wikipedia.org/wiki/Twierdzenie_o_ilo%C5%9Bci_kraw%C4%99dzi_%28graf_hamiltonowski%29

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

Q.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 liczba dzieląca symbol Newtona  kamzeso  3
 Liczba odwzorowań zbioru w zbiór ...  mol_ksiazkowy  1
 Liczba chromatyczna - zadanie 6  darex99  1
 Liczba elementów zbioru - zadanie 2  szymek12  2
 Liczba chromatyczna - zadanie 7  eldamiano22  0
cron
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl