3 zadania: szachownica, graf, rekurencja

[jraven]

1. Na tablicy wymiaru \(\displaystyle{ n n}\) znajduje sie \(\displaystyle{ n^{2}}\) figur szachowych, każda na jednym kwadracie. Chcemy przestawić każdą figurę na przyległy w tym samym rzędzie lub kolumnie kwadrat, w ten sposób, że po przestawieniu wszystkich \(\displaystyle{ n^{2}}\) figur w dalszym ciągu każda będzie zajmowała jeden kwadrat. Pokazać, że jest to możliwe wtedy i tylko wtedy, gdy \(\displaystyle{ n}\) jest parzyste.

2. Pokazać, że dla dowolnego grafu \(\displaystyle{ G = (V,E)}\),
\(\displaystyle{ \chi_{e}(G) qslant \frac{ ft|E\right| }{ ft[ \frac{1}{2} ft|V\right| \right] }}\)
gdzie \(\displaystyle{ \left[x\right]}\) oznacza część całkowitą liczby \(\displaystyle{ x}\)

3. Na podstawie zależności rekurencyjnej
\(\displaystyle{ D_{n}=(n-1)(D_{n-1} + D_{n-2})}\) (// dla \(\displaystyle{ n qslant 3}\))
udowodnić równanie
\(\displaystyle{ D_{n}=nD_{n-1} + (-1) ^{n}}\)
dla
\(\displaystyle{ n qslant 1}\)[/latex][/code]

Na koniec tylko zaznaczę, że chodzi mi o wskazówki lub rozwiązania zadań. Szczególnie chodzi mi o zadanie 2 - gdyż grafów nie umiem wcale :/

[*Kasia]

Zad. 1
Zauważ, że podczas przestawiania figury, zmieniasz kolor pola, na którym ona stoi. Zatem musisz mieć tyle samo pól czarnych co białych, a to zachodzi tylko wtedy, gdy liczba wszystkich pól jest parzysta, czy n jest parzyste.

[jraven]

Rzeczywiście - proste i łatwe.. od razu widać rozwiązanie
Dziękuję

Jeszcze nurtuje mnie jak zrobić zadanie 2 (kolorowanie krawędzi).
Myślę, że trzeba skorzystać z twierdzenia Visinga.. tylko nie wiem jak

[UNIX_admin]

Ad. 2.

krawedzi w jednym kolorze moze byc maksymalnie \(\displaystyle{ \lfloor \frac{1}{2} |V| \rfloor}\) kolorow jest \(\displaystyle{ \chi_{e}(G)}\) zatem \(\displaystyle{ |E| qslant \chi_{e}(G) \lfloor \frac{1}{2} |V| \rfloor}\)