Cesko.wiki Schwenkova věta
Author
Albert FloresSchwenkova věta je matematická věta z teorie grafů, která stanovuje podmínky řešitelnosti problému jezdcovy procházky.
Znění
Pro jakoukoliv šachovnici o rozměrech m × n polí, kde m ≤ n, je uzavřené řešení jezdcovy procházky vždy možné, s výjimkou následujících případů:
# obě čísla m a n jsou lichá; m a n nejsou současně obě rovna 1 # m = 1, 2 nebo 4; m a n nejsou současně obě rovna 1 # m = 3 a n = 4, 6, nebo 8
Důkaz
Podmínka č. 1
Není těžké dokázat, že když platí podmínka číslo jedna, je uzavřená procházka jezdce nemožná.
Představme si typickou šachovnici střídající černá a bílá pole. Kdykoliv se jezdec pohne, skončí vždy na poli opačné barvy. +more Pokud tedy stojí na bílém poli, následujícím skokem se ocitne na poli černém. Pokud stojí na černém, skočí na bílé. Proto při uzavřené procházce navštíví jezdec stejný počet bílých a černých polí.
Protože ale obě čísla m a n jsou lichá, je počet polí šachovnice rovněž lichý a tedy počet bílých a černých polí na šachovnici je nutně odlišný (například šachovnice 5 × 5 má 13 polí jedné barvy a 12 druhé).
Má-li jezdec dokončit uzavřenou procházku, musí navštívit stejný počet bílých a černých polí, ovšem uvažovaná šachovnice má odlišný počet bílých a černých polí, proto na ní uzavřenou procházku nelze dokončit. Mohou však existovat řešení otevřená.
Podmínka č. 2
Podmínka č. 2 říká, že má-li kratší strana délku 1, 2 nebo 4, potom není uzavřená procházka možná.
Na první pohled je jasné, že pokud m = 1 nebo 2, není jezdcova procházka vůbec možná: jezdec není schopen navštívit každé pole této šachovnice (s výjimkou triviálního případu „šachovnice“ 1 × 1 pole).
Lze však také prokázat, že uzavřená procházka nemá řešení ani na šachovnici o 4 × n polích.
Předpokládejme, že úloha má na šachovnici 4 × n řešení. Sestavme 2 množiny polí A_1 a B_1 , přičemž A_1 bude obsahovat jednu polovinu polí šachovnice (např. +more bílá pole) a B_1 druhou (např. černá pole). Jak již bylo uvedeno výše, jezdec musí při svém pohybu střídat bílá a černá pole ( A_1 a B_1 ).
Na diagramu vpravo můžeme definovat A_2 jako množinu zelených polí a B_2 jako množinu červených polí. Počty zelených a červených polí si jsou rovny. +more Je zřejmé, že z pole v A_2 musí jezdec v dalším tahu skočit na pole v B_2 . A protože musí navštívit každé pole, musí z pole v množině B_2 skočit na pole množiny A_2 (pokud by po sobě následovaly dva tahy v rámci množiny B_2 , musely by po sobě následovat také dva tahy v rámci množiny A_2 , což není možné).
Zde však dochází k rozporu:
#Řekněme, že první pole, které jezdec navštíví, bude pole z množiny A_1 a současně z množiny A_2 . Pokud tomu tak není, přehodíme označení množin A_1 a B_1 a případně A_2 a B_2 tak, aby to byla pravda. +more #Druhé navštívené pole musí být potom prvkem množin B_1 a B_2 . #Třetí navštívené pole musí být prvkem množin A_1 a A_2 . #Čtvrté navštívené pole musí být prvkem množin B_1 a B_2 . #A tak dále.
Z toho plyne, že množina A_1 má stejné prvky jako množina A_2 a že množina B_1 má stejné prvky jako množina B_2 . To však evidentně není pravda, neboť červeno-zelený vzor na diagramu neodpovídá černo-bílému šachovnicovému vzoru; množina červených polí není stejná jako množina černých polí (a množina zelených není stejná jako množina bílých).
Z toho plyne, že výše uvedený předpoklad byl nepravdivý a na šachovnici 4 × n nelze pro žádné n nalézt řešení jezdcovy procházky.
Podmínka č. 3
Neexistenci uzavřeného řešení v případě podmínky č. 3 lze prokázat rozborem případů.
Opačná implikace
K důkazu věty je nutné prokázat ještě opačnou implikaci, tj. že na všech obdélníkových šachovnicích, které nespadají do jedné ze tří výše uvedených kategorií, lze uzavřené řešení jezdcovy procházky nalézt.