V sobotu 2. listopadu proběhla mohutná oslava naší plnoletosti !!
Multimediaexpo.cz je již 18 let na českém internetu !!
V tiskové zprávě k 18. narozeninám brzy najdete nové a zásadní informace.

Schwenkova věta

Z Multimediaexpo.cz

(Rozdíly mezi verzemi)
m (1 revizi)
(+ Masivní vylepšení)
Řádka 1: Řádka 1:
-
{{Wikipedia-cs|Schwenkova věta|700}}
+
'''Schwenkova věta''' je [[matematická věta]] z [[teorie grafů]], která stanovuje podmínky řešitelnosti problému [[jezdcova procházka|jezdcovy procházky]].
 +
== Znění ==
 +
''Pro jakoukoliv [[šachovnice|šachovnici]] o rozměrech ''m'' × ''n'' polí, kde ''m'' ≤ ''n'', je [[jezdcova procházka#Druhy řešení|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 [[Sudá a lichá čísla|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é [[matematický důkaz|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 [[Sudá a lichá čísla|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 [[jezdcova procházka#Druhy řešení|ř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&nbsp;&times;&nbsp;n&nbsp;řešení. Sestavme 2&nbsp;[[množina|množiny]] polí <math> A_1 </math> a <math> B_1 </math>, přičemž <math> A_1 </math> bude obsahovat jednu polovinu polí šachovnice (např.&nbsp;bílá pole) a <math> B_1 </math> druhou (např.&nbsp;černá pole). Jak již bylo uvedeno výše, jezdec musí při svém pohybu střídat bílá a černá pole (<math> A_1 </math> a <math> B_1 </math>).
 +
 +
[[Image:Grid4xnColoredSquares.jpg|thumb|200px|right|Jezdec musí střídat zelená a červená pole]]
 +
Na diagramu vpravo můžeme definovat <math> A_2 </math> jako množinu zelených polí a <math> B_2 </math> jako množinu červených polí. Počty zelených a červených polí si jsou rovny. Je zřejmé, že z&nbsp;pole v&nbsp;<math> A_2 </math> musí jezdec v&nbsp;dalším tahu skočit na pole v&nbsp;<math> B_2 </math>. A protože musí navštívit každé pole, musí z&nbsp;pole v&nbsp;množině <math> B_2 </math> skočit na pole množiny <math> A_2 </math> (pokud by po sobě následovaly dva tahy v&nbsp;rámci množiny <math> B_2 </math>, musely by po sobě následovat také dva tahy v&nbsp;rámci množiny <math> A_2 </math>, což není možné).
 +
 +
Zde však dochází k&nbsp;rozporu:
 +
 +
#Řekněme, že první pole, které jezdec navštíví, bude pole z&nbsp;množiny <math> A_1 </math> a současně z&nbsp;množiny <math> A_2 </math>. Pokud tomu tak není, přehodíme označení množin <math> A_1 </math> a <math> B_1 </math> a případně <math> A_2 </math> a <math> B_2 </math> tak, aby to byla pravda.
 +
#Druhé navštívené pole musí být potom prvkem množin <math> B_1 </math> a <math> B_2 </math>.
 +
#Třetí navštívené pole musí být prvkem množin <math> A_1 </math> a <math> A_2 </math>.
 +
#Čtvrté navštívené pole musí být prvkem množin <math> B_1 </math> a <math> B_2 </math>.
 +
#A tak dále.
 +
 +
Z&nbsp;toho plyne, že množina <math> A_1 </math> má stejné [[prvek množiny|prvky]] jako množina <math> A_2 </math> a že množina <math> B_1 </math> má stejné prvky jako množina <math> B_2 </math>. 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&nbsp;toho plyne, že výše uvedený předpoklad byl nepravdivý a na šachovnici 4&nbsp;&times;&nbsp;n nelze pro žádné ''n'' nalézt řešení jezdcovy procházky.
 +
 +
=== Podmínka č. 3 ===
 +
 +
Neexistenci uzavřeného řešení v&nbsp;případě podmínky č.&nbsp;3 lze prokázat [[důkaz rozborem případů|rozborem případů]].
 +
 +
=== Opačná implikace ===
 +
K&nbsp;[[matematický důkaz|důkazu]] [[věta (matematika)|věty]] je nutné prokázat ještě opačnou [[implikace|implikaci]], tj. že na všech [[obdélník]]ových šachovnicích, které nespadají do jedné ze&nbsp;tří výše uvedených kategorií, lze uzavřené řešení jezdcovy procházky nalézt.
 +
 +
== Externí odkazy ==
 +
 +
{{Článek z Wikipedie}}
 +
[[Kategorie:Matematické věty a důkazy]]
[[Kategorie:Grafové pojmy]]
[[Kategorie:Grafové pojmy]]

Verze z 3. 2. 2015, 11:36

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

Obsah

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í <math> A_1 </math> a <math> B_1 </math>, přičemž <math> A_1 </math> bude obsahovat jednu polovinu polí šachovnice (např. bílá pole) a <math> B_1 </math> druhou (např. černá pole). Jak již bylo uvedeno výše, jezdec musí při svém pohybu střídat bílá a černá pole (<math> A_1 </math> a <math> B_1 </math>).

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

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

Z toho plyne, že množina <math> A_1 </math> má stejné prvky jako množina <math> A_2 </math> a že množina <math> B_1 </math> má stejné prvky jako množina <math> B_2 </math>. 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

Citováno z „http://ww.multimediaexpo.cz/mmecz/index.php/Schwenkova_v%C4%9Bta“