Schwenkova věta - Historie editací

Sysop: Nahrazení textu „“ textem „\)“

2022-08-14T14:53:37Z

Nahrazení textu „</math>“ textem „\)</big>“

← Starší verze		Verze z 14. 8. 2022, 14:53
Řádka 27:		Řádka 27:
	Lze však také prokázat, že uzavřená procházka nemá řešení ani na šachovnici o 4 × n polích.		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žina\|množiny]] polí <big>\( A_1 </~~math~~> a <big>\( B_1 </~~math~~>, přičemž <big>\( A_1 </~~math~~> bude obsahovat jednu polovinu polí šachovnice (např. bílá pole) a <big>\( 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 (<big>\( A_1 </~~math~~> a <big>\( B_1 </~~math~~>).	+	Předpokládejme, že úloha má na šachovnici 4 × n řešení. Sestavme 2 [[množina\|množiny]] polí <big>$ A_1 $</big> a <big>$ B_1 $</big>, přičemž <big>$ A_1 $</big> bude obsahovat jednu polovinu polí šachovnice (např. bílá pole) a <big>$ B_1 $</big> druhou (např. černá pole). Jak již bylo uvedeno výše, jezdec musí při svém pohybu střídat bílá a černá pole (<big>$ A_1 $</big> a <big>$ B_1 $</big>).

	[[Image:Grid4xnColoredSquares.jpg\|thumb\|200px\|right\|Jezdec musí střídat zelená a červená pole]]		[[Image:Grid4xnColoredSquares.jpg\|thumb\|200px\|right\|Jezdec musí střídat zelená a červená pole]]
-	Na diagramu vpravo můžeme definovat <big>\( A_2 </~~math~~> jako množinu zelených polí a <big>\( 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 <big>\( A_2 </~~math~~> musí jezdec v dalším tahu skočit na pole v <big>\( B_2 </~~math~~>. A protože musí navštívit každé pole, musí z pole v množině <big>\( B_2 </~~math~~> skočit na pole množiny <big>\( A_2 </~~math~~> (pokud by po sobě následovaly dva tahy v rámci množiny <big>\( B_2 </~~math~~>, musely by po sobě následovat také dva tahy v rámci množiny <big>\( A_2 </~~math~~>, což není možné).	+	Na diagramu vpravo můžeme definovat <big>$ A_2 $</big> jako množinu zelených polí a <big>$ B_2 $</big> jako množinu červených polí. Počty zelených a červených polí si jsou rovny. Je zřejmé, že z pole v <big>$ A_2 $</big> musí jezdec v dalším tahu skočit na pole v <big>$ B_2 $</big>. A protože musí navštívit každé pole, musí z pole v množině <big>$ B_2 $</big> skočit na pole množiny <big>$ A_2 $</big> (pokud by po sobě následovaly dva tahy v rámci množiny <big>$ B_2 $</big>, musely by po sobě následovat také dva tahy v rámci množiny <big>$ A_2 $</big>, což není možné).

	Zde však dochází k rozporu:		Zde však dochází k rozporu:

-	#Řekněme, že první pole, které jezdec navštíví, bude pole z množiny <big>\( A_1 </~~math~~> a současně z množiny <big>\( A_2 </~~math~~>. Pokud tomu tak není, přehodíme označení množin <big>\( A_1 </~~math~~> a <big>\( B_1 </~~math~~> a případně <big>\( A_2 </~~math~~> a <big>\( B_2 </~~math~~> tak, aby to byla pravda.	+	#Řekněme, že první pole, které jezdec navštíví, bude pole z množiny <big>$ A_1 $</big> a současně z množiny <big>$ A_2 $</big>. Pokud tomu tak není, přehodíme označení množin <big>$ A_1 $</big> a <big>$ B_1 $</big> a případně <big>$ A_2 $</big> a <big>$ B_2 $</big> tak, aby to byla pravda.
-	#Druhé navštívené pole musí být potom prvkem množin <big>\( B_1 </~~math~~> a <big>\( B_2 </~~math~~>.	+	#Druhé navštívené pole musí být potom prvkem množin <big>$ B_1 $</big> a <big>$ B_2 $</big>.
-	#Třetí navštívené pole musí být prvkem množin <big>\( A_1 </~~math~~> a <big>\( A_2 </~~math~~>.	+	#Třetí navštívené pole musí být prvkem množin <big>$ A_1 $</big> a <big>$ A_2 $</big>.
-	#Čtvrté navštívené pole musí být prvkem množin <big>\( B_1 </~~math~~> a <big>\( B_2 </~~math~~>.	+	#Čtvrté navštívené pole musí být prvkem množin <big>$ B_1 $</big> a <big>$ B_2 $</big>.
	#A tak dále.		#A tak dále.

-	Z toho plyne, že množina <big>\( A_1 </~~math~~> má stejné [[prvek množiny\|prvky]] jako množina <big>\( A_2 </~~math~~> a že množina <big>\( B_1 </~~math~~> má stejné prvky jako množina <big>\( 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 množina <big>$ A_1 $</big> má stejné [[prvek množiny\|prvky]] jako množina <big>$ A_2 $</big> a že množina <big>$ B_1 $</big> má stejné prvky jako množina <big>$ B_2 $</big>. 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.		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.

Sysop: Nahrazení textu „ $“ textem „$ \(“

2022-08-14T14:50:04Z

Nahrazení textu „<math>“ textem „<big>\(“

← Starší verze		Verze z 14. 8. 2022, 14:50
Řádka 27:		Řádka 27:
	Lze však také prokázat, že uzavřená procházka nemá řešení ani na šachovnici o 4 × n polích.		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ž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ř. 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>).	+	Předpokládejme, že úloha má na šachovnici 4 × n řešení. Sestavme 2 [[množina\|množiny]] polí <big>\( A_1 </math> a <big>\( B_1 </math>, přičemž <big>\( A_1 </math> bude obsahovat jednu polovinu polí šachovnice (např. bílá pole) a <big>\( 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 (<big>\( A_1 </math> a <big>\( B_1 </math>).

	[[Image:Grid4xnColoredSquares.jpg\|thumb\|200px\|right\|Jezdec musí střídat zelená a červená pole]]		[[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 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é).	+	Na diagramu vpravo můžeme definovat <big>\( A_2 </math> jako množinu zelených polí a <big>\( 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 <big>\( A_2 </math> musí jezdec v dalším tahu skočit na pole v <big>\( B_2 </math>. A protože musí navštívit každé pole, musí z pole v množině <big>\( B_2 </math> skočit na pole množiny <big>\( A_2 </math> (pokud by po sobě následovaly dva tahy v rámci množiny <big>\( B_2 </math>, musely by po sobě následovat také dva tahy v rámci množiny <big>\( A_2 </math>, což není možné).

	Zde však dochází k rozporu:		Zde však dochází k rozporu:

-	#Ř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.	+	#Řekněme, že první pole, které jezdec navštíví, bude pole z množiny <big>\( A_1 </math> a současně z množiny <big>\( A_2 </math>. Pokud tomu tak není, přehodíme označení množin <big>\( A_1 </math> a <big>\( B_1 </math> a případně <big>\( A_2 </math> a <big>\( 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>.	+	#Druhé navštívené pole musí být potom prvkem množin <big>\( B_1 </math> a <big>\( B_2 </math>.
-	#Třetí navštívené pole musí být prvkem množin <~~math~~> A_1 </math> a <~~math~~> A_2 </math>.	+	#Třetí navštívené pole musí být prvkem množin <big>\( A_1 </math> a <big>\( A_2 </math>.
-	#Čtvrté navštívené pole musí být prvkem množin <~~math~~> B_1 </math> a <~~math~~> B_2 </math>.	+	#Čtvrté navštívené pole musí být prvkem množin <big>\( B_1 </math> a <big>\( B_2 </math>.
	#A tak dále.		#A tak dále.

-	Z 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 toho plyne, že množina <big>\( A_1 </math> má stejné [[prvek množiny\|prvky]] jako množina <big>\( A_2 </math> a že množina <big>\( B_1 </math> má stejné prvky jako množina <big>\( 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.		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.

Sysop: + Masivní vylepšení

2015-02-03T11:36:23Z

+ Masivní vylepšení

← Starší verze		Verze z 3. 2. 2015, 11:36
Řá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 × n řešení. Sestavme 2 [[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ř. 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>).
		+
		+	[[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 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:
		+
		+	#Ř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.
		+	#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 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 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 [[důkaz rozborem případů\|rozborem případů]].
		+
		+	=== Opačná implikace ===
		+	K [[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 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]]

Sysop: 1 revizi

2013-08-21T21:13:10Z

1 revizi

← Starší verze

Verze z 21. 8. 2013, 21:13

Sysop: + Nový článek

2012-10-22T01:20:56Z

+ Nový článek

Nová stránka