KÓŁECZKO Z GRAFÓW - CZ _{}EŚĆ II (23.01.08)

1. TEORIA

1.1. Cykl Hamiltona to cykl, ktoży przechodzi przez wszystkie wierzchołki i przedz każdy dokładnie raz.

Cykl Eulera to cykl, który przechodzi przez każd _{}a kraw_{}ed”x dokładnie raz.

1.2. Tw. Orego

Jeśli graf jest spójny, n - liczba jego wierzchołków spełnia n > 3 oraz dla każdej pary wierzchołków niepoł _{}aczonych kraw_{}edzi _{}a suma ich stopni jest wi_{}eksza lub równa n, to wtedy graf ma cykl Hamiltona.

1.3. Wniosek Diraca

Jeśli graf ma n wierzchołków i stopień każdeg wierzchołka wynosi co najmniej \frac{n}{2}, to graf ma cykl Hamiltona.

1.4. Twierdzenie Halla

Jeśli mamy n chłopców i m n dziewczynek i każda grupa k chłopców poł _{}aczywszy swoj _{}a wiedz_{}e zna niemniej niż k dziewczynek, to można każdemu z chłopców dobrać znan _{}a mu partnerk_{}e, tak aby pary były rozł _{}aczne.

2.ZADANKA

2.0. Pokazać, że graf ma cykl Eulera wtedy i tylko wtedy gdy stopień każdego wierzchołka jest parzysty.

2.1. Na uczt_{}e do Merlina przybyło 2n rycerzy. Każdy z nich ma wśród przybyłych co najwyżej n − 1 wrogów wśród przybyłych. Pokazać, że Merlin może ich usadzić przy okr _{}agłym stole tak, aby 2 wrogów nie siedziało obok siebie.

2.2. Dana jest tablica korkowa 20 × 20, podzielona na 400 kwadratów jednostkowych oraz 400 ogłoszeń, każde o polu 1, którymi da si_{}e pokryć cał _{}a tablic_{}e. Wykazać, że można tak wbić 400 szpilek, żeby każde ogłoszenie było przypi_{}ete i żeby żadne dwie szpilki nie były wbite w ten sam kwadrat tablicy.

2.3. Z kompletu domina usuwamy kostki 0−1, 0−2 i 0−3. Ile jeszcze trzeba jeszcze kostek usun _{}ać, żeby z pozostałych dało si_{}e ułożyć zamkni_{}ety łańcuch?

2.4. Mówimy, że prostok _{}at (szachownica w kształcie prostok _{}ata) n×m, n m jest łaciński, gdy wpisano w niego liczby od 1 do n tak, że w każdym wierszu i w każdej kolumnie żadne dwie liczby nie s _{}a takie same. Wykaż, że każdy prostok _{}at łaciński można dopełnić do kwadratu łacińskiego.

2.5.

2.6. Dana jest tablica N × N, w każdym jej polu jest wpisana pewna liczb rzeczywista tak, że suma liczb w każdej kolumnie jest taka sama i suma liczb w każdym wierszu jest taka sama. Dozwolony jest nast_{}epuj _{}acy ruch: wybieramy N pól tak, że żadne dwa nie leż _{}a w jednym wierszu lub w jednej kolumnie i dodajemy do wszystkich dowoln _{}a liczb_{}e (do wszystkich t_{}e sam _{}a). Udowodnij, że w skończonej liczbie ruchów można otrzymać tablic_{}e wypełnion _{}a zerami.