ALGORITMY UZLŮ
TEORIE UZLŮ PATŘÍ TOPOLOGII
Studium uzlů vychází z abstrakce uzlového vlákna (provazce).
Zobrazení uzlu předpokládá znalost geometrie osy vlákna - struktury zapletení. Pro realistické zobrazení uzlu použijeme metod počítačové grafiky.
Poznámka: Praktické aplikace modelují vlákno pomocí teorie pružnosti a pevnosti s různou výpočetní náročností (smotek struny.....textilní úplet).
Střípky Z teorie UZlŮ ( Robert G. Scharein, 1998, KNOTPLOT)
Matematickým uzlem (knot) rozumíme jednoduchou uzavřenou křivku umístěnou v třídimenzionálním Euklidovském prostoru R3.
Uzlem je i spojka (link).
Některé uzly mají lokální jména: čtvercový uzel                             babiččin uzel
Poznámka: Např. Čeština zná pletení, proplétání, zaplétání, splétání, oplétání, vplétání, ... uzly, smyčky, kličky, spojky, svazky, šňůry, pletence, copy ...
3
<e> $
DEKORATIVNÍ UZLY, SPOJKY A PLETENCE
Díky své strukturální komplikovanosti vytvářejí uzly esteticky zajímavé kreace.
První úlohou matematiky (resp. topologie) je rozhodnutí o ekvivalenci dvou uzlů.
Dva obrazy jednoho uzlu:
Diagram uzlu
Projekce uzlu do roviny vytvoří jednoduchou prezentaci - planární graf, tzv. diagram uzlu. Vrcholy grafu budou body křížení provazcu a popíšeme je + (nad) a - (pod) podle dohody. Provazce vytvoří hrany grafu.
K. Reidemeister v r. 1935 dokázal, že dva uzly jsou ^^^^           ^/^t                    stejné tehdy a jen tehdy, mají-li stejné uzlové
diagramy.
Resp. tehdy, je-li možné přetransformovat jeden diagram v druhý bez přerušení provazce.
Pro tento převod definoval tři typy transformací (pohybů):
fi-A E-X KX
Minimální projekce uzlů
Projekcí daného uzlu do roviny je mnoho a proto matematikové hledají projekce s nejmenším počtem křížení.
Nelze-li již uzly dělit na jednodušší elementy, nazývají se prvouzlv (prime knots) a autoři je pak zařazují do katalogů uzlů (od r. 1927).
Katalogové prvouzly :
O
io /s^ öl Uŕ"\ii. öl
^tto»    S],L^   ^15—«.     ^16^^     8i7^~      äiäj«.     Si9         S211         Sil     _
$ ® @ ® <§•<§> (Si ^ (i?
atd.
Př. Efekt transformací
Lissajousovy parametrické uzly
y(t) - cot>(nyt + <f>y) z(/) = cosier + <£,)

Podobně katalogové spojky:
n2              72
1<o '
o
72             72
6?
3
*i _   8*
6?.
line».     °1 1/
©   ©
... atd.
Na všechny uzly a spojky však Reidermeisterovy transformace nestačí. Např. Freedmanův uzel: Spojení dvou triviálních uzlů „0".
Šňůry, copy a pletence
šňůry o 2 až 6 pramenech
n
x
Tyto útvary je třeba nejdříve volnými deformacemi změnit v uzly.
Zápis uzlů
Zápis uzlů řetězci znaků
Nic moc nového!                Gaussovo kódování
ABCDEFGCDEHABGFH
Gaussovo kódovaní je omezeno na střídání křížení nad a pod (+1, -1, +1, ...). S počtem křížení n roste délka řetězce 2n .
Tuto nevýhodu odstranili H. Dowker a M. B. Thistlethwaite v r. 1983.
Opačná cesta je obtížnější.
10
Dowker Thistlethwaitovo kódování
[4 6 21                                                   |6 B 2 4|                                 [12 8 10  14 4 16 2 í]
Křížení je značeno postupně v dohodnutém směru podél provazce 1,2,3,... 2n. Každé křížení je označeno dvěma údaji, sudým a lichým.
DT definovali paritně reverzní mapování p(i) pro / = 1, 2, 3, ..., n. Pak / a p(i) označují tentýž bod
p(p(i)) = i. Odtud p(i) = p(1), p(2), p(3), ..., p(2n-1).
12
Příklad DT zápisu:
Knot Diagrams from Dowker Codes
Diagram of 3(5 crossing knot with Dowker code
[40 24 10 30 22 52 32 64 46 12 6 42 60 2 S 50 66 16 62 58 28 4 54 34 14 20 68 36 72 26 70 56 48 IS 44 3
To verify the code, start at the bottom and proceed in the direction red-orange-yellow....
Př.     elementy 3, 2
výsledek násobení:
xxx   xx   goí
součin 32
součin je asociativní zleva:
tři»*»
/Z*.~*S 432 (43)2                   f^~, 4(3:
abcd = (((ab)c)d
„Kalkul pro zaplétání"	
V roce 1970 John Conway zavádí pro tvorbu uzlů elementární prvky a definuje algebraické operace pro zaplétání.	
Př. Základní elementy.                                        ^^ + 1	X -1
a—*«.»«.          £&	Sft
( L značí element)                  součet	součin
výsledky sčítání:    XX         XXX       XXXX	
+2                                            -3	+4
	14
Pro splétání složitějších uzlů má Conway konstrukční struktury
šablony
8, 9. @L^
Hledáme vhodný zápis pro „počítačovou konstrukci" dekorativních uzlů. vhodný = pokud možno, navazující na konstrukci mozaik
Keltové neznali teorii uzlů a přesto úspěšně uzlováním dekorovali již ve čtvrtém století př.n.l:
Keltské vzory 2:

Keltské vzory 1:
Ilustrace obálek inspirované keltskými vzory:
^H-A\^M3
CELTIC DESIGN
KNOTWORK
The Secret Met h«) ot the Scribe*
Al DAN MEEHAN
Keltské uzly a pletence.
Keltové - 4. stol. př.n. I., Irští mniši - 6. stol. n. I.....Christian Mercat 1993-7.
Mercatův (Abbottův) algoritmus (1997) vychází z duálního grafu uzlu.
Primární planární graf uzlu vznikne regulární projekcí uzlu.
Parceluje rovinu na oblasti a vytváří mapu grafu, kterou „sachovnicovite" vybarvíme tak, že
parcela vně neomezená bude tmavá.
planární projekce uzlu primární graf uzlu (diagram)
mapa primárního grafu
i/rchol primárního grafu
X
Definujme čtyři typy hran (stěn buněk):
Hrana bude typu 1, tedy kladná, když provazec přicházející zleva kříží shora.
Hrana bude typu 2, tedy záporná, v ostatních případech.
hrana typu 1
hrana typu 2
Hrany typu 1 a 2 tedy představují stěny s otvorem, kterým provazce procházejí a kde se kříží. Z hlediska chování provazců jde o stejný typ stěny (stěna s otvorem).
Položíme-li nové vrcholy grafu do světlých oblastí (ok, smyček), dostaneme duální graf uzlu.
Ať hrany duálního grafu představují stěny buněk.
Př.
Trojúhelníková struktura grafu jako pásová šablona.
Zavedeme třetí typ hrany.
\/   A  \/   A   \/
M____Ĺ
L_x_
hrana typu 3 (vynechaná)
Hrana typu 3 je vynechanou hranou (spojení dvou vrcholů v primárním grafu). V této stěně buňky se provazce míjejí.
Př. Hrany typu 3 ve čtvercové struktuře grafu:
il.l I l'l
Pro volnější tvarování průběhu provazce zavedeme čtvrtý typ hrany:
Hrana typu 4 neobsahuje křížení, tj. představuje stěnu bez otvoru pro průchod provazce.
hrana typu 4         \   /
(bez kříženi)           J I /

/w\
Př. Finální zobrazení uzlů ve 3D
Trojúhelníková mříž:
Př. Modifikace hran grafu
Čtyřúhelníková mříž varianta 1:
Čtyřúhelníková mříž - varianta 2:
Zapouzdřený motiv a jeho duální graf
motiv                                   schéma zapouzdření
AS4
duální graf pro skládání
Hrany typu 3 přejdou v hrany typu 4 a naopak!
Příklad složení trojúhelníkových motivů:
Lichoběžníková rozeta jako mříž:
Složitější struktury vytvoříme skládáním jednodušších zapouzdřených uzlů.
Technika neúplného zapouzdření skýtá další možnosti.
A/
Př. Kombinace různých mřížek:
Fantazii se meze nekladou (Aidan Meehan)
Algoritmus tří mřížek
• *                      • r
■'■... '       ■                                                                                                               : :   :
..... ,  .....   ..
.    .■■"■.
■    ■■■
"■■/•;
.i:.;":'-!-!;::í!. •
(b)
(c)

12 if	5f it r-------------U----------*. i
(e)
(f)
■—""íľ"—
(d)
I                     i   ——
(g)
Glassneruv algoritmus (Grid-oriented Knots)
Irští mniši - 6. století, ilustrátor Georg Bain 1951, A. Glassner 1999.
Uzly jsou konstruovány v pravidelné čtvercové mřížce h, v a mají vnitřní a vnější část proplétání:
<a>                             (b)                               (c)
Jsou-li h a v nesoudělná čísla, je uzel tvořen jedním provazcem, mají-li společného dělitele, tvoří
uzel několik provazců (uzel je spojka).
Uzel je definován prvním (startovním) křížením (+,-).
34
Zavedení překážek
(viz dřívější neprůchozí stěny buněk)
(a)
(a)                   (b)                 (c)                   (d)
36
Umístění překážek má několik omezení:
Překážky se nesmějí protínat. Spojují horizontálně či vertikálně sousední body ve své mřížce.
Př.
Uzel (5,4)
— —p-----------_
- - - - - -r - -
(d)
(«0

(f)
Hadovité uzly přes hadovité mozaiky
Náhodně otáčená dlaždice:
Sebastian Truchet - 1657 -1729
Jedna z kreací A. Glassnera

: 'rgřSSffiíŘ íf^ffSffiíí:
Glassnerovy buňky X a T
Zavedení buněk typu X (spojování protilehlých průchodů buněk, tj. křížení) a typu T (spojování průchodů přilehlých stěn) dovolí vytváření „hadů".
T=> Pater Sébastien Truchet
	bunk	I I		buňky   T
Záměna
X-T
<:
A
W
:>
G
ft
}
G
ft
D  ^?
€)
1
D
Orientované (směrované) skelety.
Glassner hady přirovnává k hadicím s proudící vodou.    v^~
Náhrada X za T mění směr toku, který musí zůstat
v uzlu jednosměrný a nepřerušený.
=ö ^
Př. Konstrukce „hada".
zelená: měněná buňka
modrá: vynucená
konfigurace
šedá:   změněná buňka
Síť nemusí být čtvercová, stačí, má-li buňka čtyři stěny.
síť 2 sít'1
Př.
Uzel konstruovaný
kruhové obálce.
Výsledný tvar je definován startovací buňkou:					o				o				o				42
výsledky různých startů Př. Keltský uzel („neúplný had")				c	J(	t	~-\	r	{	Jr	■>	r	Jr	--	>		
					\	■}	t	>   C	->	Jr	)r	^   e	Jr	\	\	)	
					V	\	>	)	'■-	1	Jr	)	'■,.	>	v		
					r	L ^	J		r		J		r		J		
				c	\	t	>i	r	■	\	"\	r	{	<~	S		
					\	\	t	•s   L	\	\	Ý	>)   e	|	r	■	P	
					K	{	\	J	v	\	Jr	J	v.	1	>		
q	0					O				\-J				Vj			
	^	t_	=%	Glassner vytvořil pomocné programy - KnotAssistant pro strojový návrh a ruční dokončení uzlů. f    Vytvořil i mozaikový systém se zámkovými dlaždicemi,													
		0		Systém	je modifikací uvedené X-T výměny								buněk				
Aplikací sítě buněk na rozvinutý plášť vhodného tělesa vytvoříme efektní 3D uzel:
čtyřstěn
krychle
Samostatnou skupinu tvoří např. uzly na toroidu a další.
Uzel jako mozaika (a naopak)! Cíle dosaženo?
Abbottův program Knots3D (výstup 2D)
■Mssmsi
File    Custom    Help
JU|*I
-Basic Kxiol Chaia NX     NY FF r z-MiiiBi	cl eristic s------
	Square-Square -Square-Triangrj Hexagonal Circular Octagonal       ^\
r 2D Val	jes------
1st Col	■
Width	\r
Scale	j 35
Swish	|30
Smooth	\Š~
Stretch	\r~
New Grid	Old Grid    |
	
2D	Create 3D
	
2D View	3D View   |
	
Random  1	
W Show grid with knot \7 Show crossings
-3D Save Format	
iŤ	iPÜVi
r	VRML2
r	OBJ
r	DXF
r	STL
w
Abbottův program Knots3D (vstupní graf uzlu)
ebsehzei
ThrtafijPhifi)
JD]X|
NX    NY WW T Z-Mirrcr	ia r act eristic s------	
		Square-Square» Square T riangrj Hexagonal Circular Octagonal       ZA
■2D Val. 1st Col Width
Smooth   2 Stretch  H"
Create       Create
10
|7 Show grid with knot 3   Show crossings
10.95    ka  10.30    kdjs,| 1100    ks|0.5      N flÖ"
r 3D Valu	es------
Sides	W
Points	W
Radius	w
Smooth	w
Zfacl»,	w
No. Polygons	
1	
-3D Save Format	
í*	POV
r	VRML2
r	OBJ
r	DXF
r	STL
	
Abbottův program Knots3D (výstup 3D)
EBEMEI
1 st Col Width     I
Smooth [g Stretch V\~
New Grid	Old Grid   |
	
Create 2D	Create 3D
	
2D	3D
	
Random	
■/  Show grid with knot [7 Show crossings
kd  |0 95    ka  10.30    kdjst|l100    ks|0.5      N fTÖ"
r 3D Values------	
Sides	W
Points	W
Radius	w
Smooth	w
Z-iado,	w
No. Polygons	
|2304	
p 3D Save Format	
CÍ	POV
r	VRML2
c	DBJ
r	DXF
c	STL