Schwenkova věta

Z Multimediaexpo.cz

Verze z 14. 8. 2022, 14:53; Sysop (diskuse | příspěvky)
(rozdíl) ← Starší verze | zobrazit aktuální verzi (rozdíl) | Novější verze → (rozdíl)

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

Obsah

[skrýt]

Znění

Pro jakoukoliv šachovnici o rozměrech m × n polí, kde mn, 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í A1 a B1, přičemž A1 bude obsahovat jednu polovinu polí šachovnice (např. bílá pole) a B1 druhou (např. černá pole). Jak již bylo uvedeno výše, jezdec musí při svém pohybu střídat bílá a černá pole (A1 a B1).

Jezdec musí střídat zelená a červená pole

Na diagramu vpravo můžeme definovat A2 jako množinu zelených polí a B2 jako množinu červených polí. Počty zelených a červených polí si jsou rovny. Je zřejmé, že z pole v A2 musí jezdec v dalším tahu skočit na pole v B2. A protože musí navštívit každé pole, musí z pole v množině B2 skočit na pole množiny A2 (pokud by po sobě následovaly dva tahy v rámci množiny B2, musely by po sobě následovat také dva tahy v rámci množiny A2, 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 A1 a současně z množiny A2. Pokud tomu tak není, přehodíme označení množin A1 a B1 a případně A2 a B2 tak, aby to byla pravda.
  2. Druhé navštívené pole musí být potom prvkem množin B1 a B2.
  3. Třetí navštívené pole musí být prvkem množin A1 a A2.
  4. Čtvrté navštívené pole musí být prvkem množin B1 a B2.
  5. A tak dále.

Z toho plyne, že množina A1 má stejné prvky jako množina A2 a že množina B1 má stejné prvky jako množina B2. 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

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