Szachy - teoria grafów

jusssstysia · Post autor: **jusssstysia** » 30 sty 2010, o 18:28

Niech n będzie liczbą nieparzystą. Udowodnij, że konik szachowy nie może odwiedzić wszystkich pól szachowych i powrócić do punktu wyjścia poruszając się zgodnie z regułami gry w szachy. W tym celu
a) Przedstawić szachownice jako graf, którego wierzchołkami są pola szachownicy, a dwa pola są połączone krawędzią, jeśli z jednego można się ruchem konika przedostać na drugie.
b) Wyjaśnić ze otrzymany graf jest dwudzielny
c) Przedstawić zadaną trasę konika jako odpowiednie pojecie z teorii grafów.
d) Dokładnie uzasadnić powołując się na odpowiednie twierdzenia, ze taka trasa nie jest możliwa.

miodzio1988 · Post autor: **miodzio1988** » 30 sty 2010, o 18:33

No to jaki jest problem? Czarne pola to wierzchołki z jednej klasy, białe pola to wierzchołki drugiej klasy. Twierdzenie Halla i jedziesz.(mozna inaczej)
Z czym Ci się kojarzy ten problem?