Schwenkova věta

Z Multimediaexpo.cz

Schwenkova věta je matematická věta z teorie grafů, která stanovuje podmínky řešitelnosti problému jezdcovy procházky.

Obsah [skrýt] 1 Znění 2 Důkaz 2.1 Podmínka č. 1 2.2 Podmínka č. 2 2.3 Podmínka č. 3 2.4 Opačná implikace 3 Externí odkazy

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ů:

1. obě čísla m a n jsou lichá; m a n nejsou současně obě rovna 1
2. m = 1, 2 nebo 4; m a n nejsou současně obě rovna 1
3. 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. 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ř. 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. 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:

1. Ř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.
2. Druhé navštívené pole musí být potom prvkem množin $B_1$ a $B_2$.
3. Třetí navštívené pole musí být prvkem množin $A_1$ a $A_2$.
4. Čtvrté navštívené pole musí být prvkem množin $B_1$ a $B_2$.
5. 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.

Externí odkazy

[zobrazit] Náklady na energie a provoz naší encyklopedie prudce vzrostly. Potřebujeme vaši podporu... Kolik ?? To je na Vás. Náš FIO účet — 2500575897 / 2010
Informace o článku. Článek je převzat z Wikipedie, otevřené encyklopedie, do které přispívají dobrovolníci z celého světa. Tento text je dostupný za podmínek Creative Commons 3.0 Unported – creativecommons.org. Originální článek na české Wikipedii