Schwenkova věta - Encyklopedie - Portál divoch.net

Hledat:

Invia.cz Last minute Tunisko Dovolená v Chorvatsku Pojeďte do Egypta Bulharsko Last minute Kréta
 

Schwenkova věta

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

Znění[editovat | editovat zdroj]

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[editovat | editovat zdroj]

Podmínka č. 1[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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 , přičemž bude obsahovat jednu polovinu polí šachovnice (např. bílá pole) a 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 ).

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

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

Z toho plyne, že množina má stejné prvky jako množina a že množina má stejné prvky jako množina . 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[editovat | editovat zdroj]

Neexistenci uzavřeného řešení v případě podmínky č. 3 lze prokázat rozborem případů.

Opačná implikace[editovat | editovat zdroj]

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.

Související články[editovat | editovat zdroj]

V tomto článku byl použit překlad textu z článku Knight's tour na anglické Wikipedii.

 
Tento článek je převzat z české wikipedie - otevřené encyklopedie, originální článek naleznete na adrese: „https://cs.wikipedia.org/w/index.php?title=Schwenkova_věta&oldid=14763463
Stránka byla naposledy upravena 5. 3. 2017 v 12:01. Editovat celý článek Schwenkova věta.
Text je dostupný pod licencí Creative Commons Uveďte autora – Zachovejte licenci 3.0 Unported, případně za dalších podmínek. Podrobnosti naleznete na stránce Podmínky užití.
Další služby: Portál | Katalog | Hledej | Zprávy | Počasí | Kurzy | Práce | Slovník | TV | Online hry | Java hry | SMS | Loga a melodie | Chat | Fórum | Kontakt | Set-top-boxy