Turniej a ścieżka Hamiltona

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Rudis
Użytkownik
Użytkownik
Posty: 83
Rejestracja: 6 sty 2014, o 13:07
Płeć: Mężczyzna
Lokalizacja: Brak
Podziękował: 3 razy
Pomógł: 17 razy

Turniej a ścieżka Hamiltona

Post autor: Rudis »

Udowodnij, że ścieżka Hamiltona w dowolnym turnieju zaczyna się w wierzchołku o stopniu największym a kończy w wierzchołku o stopniu najmniejszym.


Nie potrafię tego ugryźć dlatego proszę o pomoc w dowodzie.
Ostatnio zmieniony 21 mar 2015, o 22:12 przez Rudis, łącznie zmieniany 1 raz.
Awatar użytkownika
Zordon
Użytkownik
Użytkownik
Posty: 4977
Rejestracja: 12 lut 2008, o 21:42
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 75 razy
Pomógł: 910 razy

Turniej a ścieżka Hamiltona

Post autor: Zordon »

To nie jest prawda.
Jak definiujesz stopień w grafie skierowanym?
Rudis
Użytkownik
Użytkownik
Posty: 83
Rejestracja: 6 sty 2014, o 13:07
Płeć: Mężczyzna
Lokalizacja: Brak
Podziękował: 3 razy
Pomógł: 17 razy

Turniej a ścieżka Hamiltona

Post autor: Rudis »

Znalazłem kontrprzykład, jednak twierdzenie słowo w słowo przepisałem z książki i nie byłem pewny swoich racji.

Wyżej: stopień tzn. stopień wychodzący.
Gdyby w twierdzeniu z pierwszego posta pojawiło się na początku słówko "istnieje" to czy wtedy byłaby to prawda?
Awatar użytkownika
Zordon
Użytkownik
Użytkownik
Posty: 4977
Rejestracja: 12 lut 2008, o 21:42
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 75 razy
Pomógł: 910 razy

Turniej a ścieżka Hamiltona

Post autor: Zordon »

A potrafisz pokazać, że każdy turniej ma ścieżkę hamiltona?
Rudis
Użytkownik
Użytkownik
Posty: 83
Rejestracja: 6 sty 2014, o 13:07
Płeć: Mężczyzna
Lokalizacja: Brak
Podziękował: 3 razy
Pomógł: 17 razy

Turniej a ścieżka Hamiltona

Post autor: Rudis »

Tak
ODPOWIEDZ