O vlastnostech turnajů On Properties of Tournaments

ˇ ˇ ´ ODBORNA ´ STREDO SKOLSK A ˇ CINNOST Obor 01 - Matematika a statistika

O vlastnostech turnaj˚ u On Properties of Tournaments

Autor:

Jakub Kopˇ riva 2. roˇcn´ık, vˇseobecné gymnázium

ˇ Skola:

Slovansk´ e gymn´ azium Olomouc tˇr. Jiˇr´ıho z Podˇebrad 13 771 11 Olomouc

Konzultant:

Mgr. Michal Botur, Ph.D. Katedra algebry a geometrie Pˇr´ırodovˇedecká fakulta Univerzita Palackého Olomouc

Olomouc 2011

Prohl´ aˇ sen´ı Prohlaˇsuji, ˇze jsem svou práci vypracoval samostatnˇe pod veden´ım Mgr. Michala Botura, Ph.D. Pouˇzil jsem pouze podklady uvedené v pˇriloˇzeném seznamu a postup pˇri zpracován´ı a dalˇs´ım nakládán´ı s prac´ı je v souladu se zákonem ˇc. 121/2000 Sb., o právu autorském, o právech souvisej´ıc´ıch s právem autorsk´ ym a o zmˇenˇe nˇekter´ ych zákon˚ u (autorsk´ y zákon) v platném znˇen´ı. V Olomouci dne 13. kvˇetna 2011

Podˇ ekov´ an´ı Dˇekuji Mgr. Michalu Boturovi, Ph.D. za obˇetavou pomoc a d˚ uleˇzité, podnˇetné a vˇecné pˇripom´ınky, které mi bˇehem práce poskytoval, a v neposledn´ı ˇradˇe za trpˇelivost s vysvˇetlován´ım matematické formalizace. Dˇekuji Mgr. Janˇe Fojt´ıkové a RNDr. Karlu Hronovi, Ph.D. za cenné podnˇety a pˇripom´ınky k formáln´ım aspekt˚ um práce. Dˇekuji PhDr. Nadˇe Hronové za neocenitelnou pomoc po stránce jazykové.

Obsah Abstrakt

4

´ Uvod

6

1 Z´ aklady algebry 1.1 Mnoˇziny 1.2 Mnoˇzinové operace 1.3 Binárn´ı relace

8 8 10 13

2 Relaˇ cn´ı struktury 2.1 Obecné vlastnosti 2.2 Kongruence na relaˇcn´ıch strukturách

18 18 19

3 Turnaje a jejich vlastnosti 3.1 Obecné vlastnosti turnaj˚ u 3.2 Struktura turnaj˚ u

21 21 23

4 Kongruence na turnaj´ıch 4.1 Vlastnosti kongruenc´ı 4.2 Simple turnaje

30 30 33

5 Aplikace v´ ysledk˚ u 5.1 S´ıtˇe a jejich vlastnosti

36 36

Z´ avˇ er a diskuse

40

Seznam pouˇ zit´ eho znaˇ cen´ı

42

Zdroje

43

Pˇ r´ılohy

46

Abstrakt Turnaje a jejich vlastnosti byly uspokojivˇe zkoumány a popsány pouze z hlediska teorie graf˚ u. V´ ysledky tohoto v´ yzkumu maj´ı zaj´ımavé aplikace v oblasti sociáln´ıch vˇed v teorii volby a teorii sociáln´ıho v´ ybˇeru. Tato práce si ovˇsem klade za c´ıl popsat turnaje z hlediska algebry, k d˚ ukazu nˇekter´ ych vˇet jsou vˇsak mimo algebraick´ ych metod pouˇzity také metody kombinatorické. Turnaje jsou definovány jako relaˇcn´ı struktury, tedy jako mnoˇziny s reflexivn´ı, antisymetrickou a u ´plnou binárn´ı relac´ı na nich. V práci jsou zavedeny pojmy: cyklick´ y turnaj, tranzitivn´ı turnaj, kongruence na turnaj´ıch a simple turnaje a jsou dány spolu do souvislost´ı. Práce ukazuje pˇr´ımou souvislost mezi tranzitivn´ımi turnaji a lineárn´ımi svazy. Jednou z nejd˚ uleˇzitˇejˇs´ıch ˇcást´ı práce je jasná definice cyklick´ ych turnaj˚ u, pomoc´ı které jsou odvozeny jejich d˚ uleˇzité vlastnosti. Práce se také zab´ yvá moˇznostmi definován´ı a konstrukc´ı kongruenc´ı na turnaj´ıch, je zaveden pojem simple turnaje. Simple turnaje jsou dány do souvislost´ı s cyklick´ ymi a tranzitivn´ımi turnaji a jsou popsány nˇekteré jejich vlastnosti. Struˇcnˇe jsou nast´ınˇeny moˇzné aplikace z´ıskan´ ych poznatk˚ u.

Kl´ıˇ cov´ a slova Relaˇcn´ı struktura; kongruence; turnaj; simple turnaj; cyklick´ y turnaj; kombinatorika a teorie graf˚ u.

4

Abstract Tournaments and their properties were described yet only in terms of graph theory. There are interesting applications of those research results in social sciences for example in vote theory and social choice theory. This work is aimed to describe tournaments in terms of algebra. Instead of usual algebraic methods there are combinatorial methods used to prove some theorems. Tournaments are defined as relational structures which means a set with reflexive, antisymetric and complete binary relation on it. Cyclic tournaments, transitive tournaments, tournament congruences and simple tournaments are defined in this work and there are also shown relations among them. The work shows relation between transitive tournaments and linear lattices. One of the most important parts of the work is a clear definition of a cyclic tournament which is used to illustrate properties of cyclic tournaments. The work also contains definition of tournament congruences, way of their construction and description of their properties. Simple tournaments are defined and their properties are described with knowledge of properties of tournament congruences. Relations among simple tournaments and cyclic and transitive tournaments are shown in this work too. The work also contains an outline of the possible usage of the acquired knowledge.

Key words Relational structure; congruence; tournament; simple tournament; cyclic tournament; combinatorics and graph theory.

5

´ Uvod Turnaje a jejich vlastnosti [W ol2] byly podrobnˇeji zkoumány a popsány pouze z hlediska teorie graf˚ u [T ru] napˇr´ıkald byl vyˇc´ıslen poˇcet neizomorfn´ıch turnaj˚ u, pro r˚ uzná n, pomoc´ı aplikace Pólyovy vyˇc´ıslovac´ı metody [W ik1] a [W ik2], na tˇechto stránkách se nacházej´ı i odkazy na dalˇs´ı ˇclánky, které se sp´ıˇse zab´ yvaj´ı r˚ uzn´ ymi aplikacemi turnaj˚ u. Prozat´ım se pravdˇepodobnˇe nikdo hloubˇeji nevˇenoval v´ yzkumu turnaj˚ u z hlediska algebry, proto je tato práce v mnohém nová a prakticky nenavazuje na ˇza´dnou pˇredchoz´ı práci. Kapitoly 1 a 2 se vˇenuj´ı v´ ykladu ˇca´sti teoretického základu, na kterém práce stoj´ı, zejména teorie mnoˇzin a základn´ıch pojm˚ u binárn´ıch relac´ı v Kapitole 1 a základy problematiky relaˇcn´ıch struktur a kongruenc´ı na nich v Kapitole 2, svazy [Rach] jsou axiomatizovány v Pˇr´ıloze #2, ovˇsem v práci nejsou popsány základy kombinatoriky [Cal]. Kapitola 3 se vˇenuje pˇredstaven´ı nejd˚ uleˇzitˇejˇs´ıch ˇcást´ı v´ ysledk˚ u v oblasti obecn´ ych vlastnost´ı turnaj˚ u, cyklick´ ych turnaj˚ u a tranzitivn´ıch turnaj˚ u. V Kapitole 4 jsou zavedeny kongruence na turnaj´ıch a jsou pˇredstaveny nejd˚ uleˇzitˇejˇs´ı v´ ysledky o jejich vlastnostech a simple turnaj´ıch a jejich vlastnostech. Kapitola 5 se vˇenuje nástinu aplikac´ı nˇekter´ ych v´ ysledk˚ u práce jak v oblasti sociáln´ıch vˇed, tak matematiky. Tato práce vznikala v obdob´ı mezi ˇr´ıjnem 2010 a u ńorem 2011 v rámci projektu Badatel, WWW: http://badatel.upol.cz, kter´ y je organizován Pˇr´ırodovˇedeckou fakultou Univerzity Palackého v Olomouci, pod veden´ım Mgr. Michala Botura Ph.D. C´ılem práce je dobˇre definovat cyklické turnaje, popsat jejich vlastnosti a souvislosti s tranzitivn´ımi turnaji. Definovat kongruence na turnaj´ıch, jejich konstrukci a v souvislosti s nimi definovat simple turnaje. V neposledn´ı ˇradˇe také dát do souvislost´ı simple turnaje s cyklick´ ymi a tranzitivn´ımi turnaji.

6

Matematika je hra hraná podle jistých jednoduchých pravidel s nesmyslnými znaky na pap´ıˇre. David Hilbert1

1

David Hilbert (1862 – 1943), v´ yznamn´ y nˇemeck´ y matematik, kter´ y se mimoˇrádnˇe zaslouˇzil o axiomatizaci geometrie a také formuloval slavné Hilbertovy problémy, které v´ yznamˇe ovlivˇ novaly smˇery matematického v´ yzkumu ve 20. stolet´ı.

7

Kapitola 1 Z´ aklady algebry Tato kapitola slouˇz´ı jako naprost´ yu ´vod do problematiky, velice struˇcnˇe se zab´ yvá pojmy mnoˇzina, mnoˇzinová operace, binárn´ı relace, zobrazen´ı a relace ekvivalence, které jsou nezbytnˇe nutné k pochopen´ı obsahu dalˇs´ıch kapitol.

1.1 Mnoˇ ziny Mnoˇzinou rozum´ıme koneˇcn´ y, nebo nekoneˇcn´ y soubor objekt˚ u - prvk˚ u mnoˇziny, u kter´ ych nezáleˇz´ı na poˇrad´ı a mnohoˇcetnosti.[W ol1] Mnoˇziny znaˇc´ıme velk´ ymi p´ısmeny, prvky povˇetˇsinou mal´ ymi p´ısmeny. Skuteˇcnost, ˇze prvek a náleˇz´ı do mnoˇziny A, znaˇc´ıme a ∈ A, skuteˇcnost, ˇze prvek b nenáleˇz´ı do mnoˇziny A, se znaˇc´ı b ∈ / A. Obecnˇe existuj´ı dva zp˚ usoby zápisu mnoˇzin: 1. Mnoˇzinu m˚ uˇzeme zapsat v´ yˇctem prvk˚ u. Pˇr´ıklad • Mnoˇzina prvn´ıch 4 pˇrirozen´ ych ˇc´ısel A = {1; 2; 3; 4} 8

• Mnoˇzina vˇsech reáln´ ych koˇren˚ u rovnice x2 − x − 1 = 0 ( B=

√ √ ) 1− 5 1+ 5 ; 2 2

2. Mnoˇzinu m˚ uˇzeme zapsat pomoc´ı charakteristické vlastnosti.2 Pˇr´ıklad • Mnoˇzina prvn´ıch 4 pˇrirozen´ ych ˇc´ısel

3

A = {a ∈ N | a ≤ 4} • Mnoˇzina vˇsech reáln´ ych koˇren˚ u rovnice x2 − x − 1 = 0 B = x ∈ R | x2 − x − 1 = 0 Definice 1.1 Mohutnost mnoˇziny je u koneˇcn´ ych mnoˇzin rovna poˇctu prvk˚ u dané mnoˇziny. Mohutnost mnoˇziny A se znaˇc´ı |A|. Pˇr´ıklad • Mˇejme mnoˇzinu prvn´ıch 4 pˇrirozen´ ych ˇc´ısel A = {1; 2; 3; 4}, pak |A| = 4.

2 3

Pr´ azdn´ a mnoˇzina se znaˇc´ı ∅. Z´ apis A = {a ∈ N | a ≤ 4} se ˇcte: “Mnoˇziny pˇrirozen´ ych ˇc´ısel a takov´ ych, ˇze a ≤ 4 ”.

9

1.2 Mnoˇ zinov´ e operace Definice 1.2 Pr˚ unik mnoˇzin A a B se znaˇc´ı A ∩ B. Pr˚ unikem mnoˇzin A a B je mnoˇzina taková, ˇze A ∩ B = {c | c ∈ A ∧ c ∈ B}. Je-li pr˚ unikem mnoˇzin A a B mnoˇzina C, pak tuto skuteˇcnost znaˇc´ıme A ∩ B = C.

Obrázek 1: Pr˚ unik mnoˇzin Pˇr´ıklad • Mˇejme mnoˇziny A a B takové, ˇze A = {a ∈ N | a ≤ 4} = {1; 2; 3; 4} B = {b ∈ R | b2 −7b+10 = 0} = {2; 5}, pak pr˚ unikem mnoˇzin A a B je mnoˇzina taková, ˇze A ∩ B = {c ∈ N | c2 − 7c + 10 = 0 ∧ c ≤ 4} = {2}. Definice 1.3 Sjednocen´ı mnoˇzin A a B se znaˇc´ı A ∪ B. Sjednocen´ım mnoˇzin A a B je mnoˇzina taková, ˇze A ∪ B = {c | c ∈ A ∨ c ∈ B}. Je-li sjednocen´ım mnoˇzin A a B mnoˇzina C, pak tuto skuteˇcnost znaˇc´ıme A ∪ B = C.

10

Obrázek 2: Sjednocen´ı mnoˇzin Pˇr´ıklad • Mˇejme mnoˇziny A a B takové, ˇze A = {a ∈ N | a ≤ 4} = {1; 2; 3; 4} B = {b ∈ R | b2 −7b+10 = 0} = {2; 5}, pak sjednocen´ım mnoˇzin A a B je mnoˇzina taková, ˇze A ∪ B = {c ∈ N | c2 − 7c + 10 = 0 ∨ c ≤ 4} = {1; 2; 3; 4; 5}. Definice 1.4 Rozd´ıl mnoˇzin A a B se znaˇc´ı A\B. Rozd´ılem mnoˇzin A a B (v tomto poˇrad´ı) je mnoˇzina taková, ˇze A\B = {c | c ∈ A ∧ c ∈ / B}. Je-li rozd´ılem mnoˇzin A a B mnoˇzina C, pak tuto skuteˇcnost znaˇc´ıme A\B = C.

Obrázek 3: Rozd´ıl mnoˇzin 11

Pˇr´ıklad • Mˇejme mnoˇziny A a B takové, ˇze A = {a ∈ N | a ≤ 4} = {1; 2; 3; 4} B = {b ∈ R | b2 −7b+10 = 0} = {2; 5}, pak rozd´ılem mnoˇzin A a B je mnoˇzina taková, ˇze A\B = {c ∈ N | c ≤ 4 ∧ c2 − 7c + 10 6= 0} = {1; 3; 4}. Definice 1.5 Kartézský souˇcin mnoˇzin A a B v tomto poˇrad´ı se znaˇc´ı A × B. Kartézsk´ ym souˇcinem mnoˇzin A a B je mnoˇzina taková, ˇze A × B = {(a; b) | a ∈ A ∧ b ∈ B}, kde (a; b) je uspoˇrádaná dvojice prvk˚ u a a b. Je-li kartézsk´ ym souˇcinem mnoˇzin A a B mnoˇzina C, pak tuto skuteˇcnost znaˇc´ıme A × B = C. Pˇr´ıklad • Mˇejme mnoˇziny A a B takové, ˇze A = {a ∈ N | a ≤ 4} = {1; 2; 3; 4} B = {b ∈ R | b2 −7b+10 = 0} = {2; 5}, pak kartézsk´ ym souˇcinem mnoˇzin A a B je mnoˇzina taková, ˇze A × B = {(1; 2); (1; 5); (2; 2); (2; 5); (3; 2); (3; 5); (4; 2); (4; 5)}. V kontextu v´ yˇse definovan´ ych mnoˇzinov´ ych operac´ı m˚ uˇzeme zavést pojem podmnoˇzina, jehoˇz znalost je nutná k definován´ı dalˇs´ıch d˚ uleˇzit´ ych pojm˚ u. Definice 1.6 Mˇejme mnoˇziny A a B, pokud plat´ı, ˇze A ∩ B = B nebo A ∪ B = A 4 , pak mnoˇzina B je podmnoˇzinou mnoˇziny A, tato skuteˇcnost se znaˇc´ı B ⊂ A, pokud B 6= A, v opaˇcném pˇr´ıpadˇe B ⊆ A, tedy pokud m˚ uˇze platit B = A. 4

Tyto v´ yroky jsou ekvivalentn´ı, protoˇze A ∩ B = B, pak A ∪ B = A ∪ (A ∩ B) = A.

12

Pˇr´ıklad • Mˇejme mnoˇziny pˇrirozen´ ych ˇc´ısel N, cel´ ych ˇc´ısel Z, racionáln´ıch ˇc´ısel Q, reáln´ ych ˇc´ısel R, a komplexn´ıch ˇc´ısel C, pak pro tyto mnoˇziny plat´ı N ⊂ Z ⊂ Q ⊂ R ⊂ C.

1.3 Bin´ arn´ı relace Definice 1.7 Binárn´ı relac´ı R mezi mnoˇzinami A a B v tomto poˇrad´ı naz´ yváme libovolnou podmnoˇzinu R kartézského souˇcinu A × B. Jestliˇze R ⊆ A2 , pak R je binárn´ı relac´ı na A. Pˇr´ıklad • Mˇejme mnoˇziny A a B takové, ˇze A = {a ∈ N | a ≤ 4} = {1; 2; 3; 4} B = {b ∈ R | b2 −7b+10 = 0} = {2; 5}. Proto kartézsk´ ym souˇcinem mnoˇzin A a B je mnoˇzina taková, ˇze A × B = {(1; 2); (1; 5); (2; 2); (2; 5); (3; 2); (3; 5); (4; 2); (4; 5)}. ˇ Definujeme relaci R. Reknˇ eme, ˇze plat´ı (a; b) ∈ R, pokud tyto prvky splˇ nuj´ı podm´ınku a + b < ab, tedy R = {(a; b) | a ∈ A∧b ∈ B; a+b < ab} = {(2; 5); (3; 2); (3; 5); (4; 2); (4; 5)}. Definice 1.8 Inverzn´ı relac´ı k binárn´ı relaci R ⊆ A × B, je taková mnoˇzina uspoˇra´dan´ ych −1 dvojic (b; a), které náleˇz´ı R tehdy a jen tehdy, jestliˇze (a; b) ∈ R.

13

Pˇr´ıklad • Mˇejme mnoˇziny A a B takové, ˇze A = {a ∈ N | a ≤ 4} = {1; 2; 3; 4} B = {b ∈ R | b2 −7b+10 = 0} = {2; 5}, a relaci R takovou, ˇze R = {(a; b) | a ∈ A ∧ b ∈ B; a+b < ab} = {(2; 5); (3; 2); (3; 5); (4; 2); (4; 5)}, pak relac´ı R−1 je relace taková, ˇze R−1 = {(5; 2); (2; 3); (5; 3); (2; 4); (5; 4)}. Definice 1.9 Binárn´ı relace f mezi mnoˇzinami A a B se naz´ yvá zobrazen´ım mnoˇziny A do B, znaˇc´ı se f : A → B, plat´ı-li, ˇze pro kaˇzdé a ∈ A existuje jedin´ y obraz b ∈ B takov´ y, ˇze (a; b) ∈ f . Takov´ yto obraz obvykle znaˇc´ıme b = f (a). 5 Definice 1.10 Zobrazen´ı f : A → B se naz´ yvá: 1. injektivn´ı, tj. prosté, plat´ı-li, f (a) = f (b) ⇒ a = b, 2. surjektivn´ı, plat´ı-li, ˇze ke kaˇzdému b ∈ B existuje nˇejaké a ∈ A takové, ˇze f (a) = b, 3. bijektivn´ı, plat´ı-li, ˇze je zároveˇ n injektivn´ı a surjektivn´ı.

5

Nejlepˇs´ım pˇr´ıkladem zobrazen´ı je funkce. Skuteˇcnost, ˇze ˇze pro kaˇzdé a ∈ A existuje jen jedno f (a) ∈ B, tedy ˇze existuje jen jedna funkˇcn´ı hodnota kaˇzdého prvku, je moˇzno ilustrovat na grafu funkce v souˇradnicové soustavˇe Oxy , kde kaˇzdá rovnobˇeˇzka s osou y protne graf funkce nejv´ yˇse jednou.

14

Obrázek 4: Pˇr´ıklady relac´ı a zobrazen´ı Popis obrázku • Relace na obrázku a) nen´ı zobrazen´ı. • Relace na obrázku b) je injektivn´ı zobrazen´ı, ale nen´ı surjektivn´ı, protoˇze neexistuje ˇza´dné x ∈ A takové, ˇze f (x) = u. • Relace na obrázku c) je bijektivn´ı zobrazen´ı. • Relace na obrázku d) je zobrazen´ı, ale nen´ı injektivn´ı ani surjektivn´ı, protoˇze neexistuje ˇza´dné x ∈ A takové, ˇze f (x) = z a jelikoˇz f (c) = f (d), ale c 6= d. Pˇr´ıklad • Zobrazen´ı f1 : R → R+ takové, ˇze f1 : y = |x|, je zjevnˇe surjektivn´ı, ale nen´ı injektivn´ı, protoˇze plat´ı, ˇze |x| = | − x|, ale obecnˇe neplat´ı, ˇze −x = x. • Zobrazen´ı f2 : R+ → R takové, ˇze f2 : y = log x, je zjevnˇe bijektivn´ı. 15

• Zobrazen´ı f3 : N → N takové, ˇze f3 : y = x2 je injektivn´ı, ale nen´ı surjektivn´ı, protoˇze neexistuje napˇr´ıklad ˇzádné n ∈ N takové, ˇze by platilo n2 = 2. Definice 1.11 Binárn´ı relace R ⊆ A2 se naz´ yvá

6

1. reflexivn´ı, plat´ı-li ∀x ∈ A : (x; x) ∈ R, 2. symetrická, plat´ı-li ∀x, y ∈ A : (x; y) ∈ R ⇒ (y; x) ∈ R, 3. antisymetrická, plat´ı-li ∀x, y ∈ A : (x; y) ∈ R ∧ (y; x) ∈ R ⇒ x = y, 4. tranzitivn´ı, plat´ı-li ∀x, y, z ∈ A : (x; y) ∈ R ∧ (y; z) ∈ R ⇒ (x; z), ∈ R 5. u ´plná, plat´ı-li ∀x, y ∈ A : (x; y) ∈ R ∨ (y; x) ∈ R. Definice 1.12 Relace ekvivalence je reflexivn´ı, symetrická a tranzitivn´ı binárn´ı relace. Znaˇc´ı se xEy. Mˇejme mnoˇzinu A a ekvivalenci E ⊆ A2 , pak se mnoˇzina x/E = {y ∈ A | yEx} naz´ yvá tˇr´ıdou ekvivalence E s reprezentantem x, pˇriˇcemˇz ∀y ∈ 6

Nˇekteré tyto vlastnosti jsou navzájem disjunktn´ı. Libovolná binárn´ı relace nemus´ı splˇ novat ani jednu z tˇechto vlastnost´ı. Zápis (x; y) ∈ R je ekvivalentn´ı se zápisem xRy, kter´ y se pouˇz´ıv´ a d´ ale.

16

x/E : x/E = y/E. Tˇr´ıdy ekvivalence jsou disjunktn´ı. Mnoˇzinu vˇsech tˇr´ıd ekvivalence, tedy {x/E | x ∈ A} nazváme faktormnoˇzinou podle ekvivalence E a znaˇc´ıme A/E.

17

Kapitola 2 Relaˇ cn´ı struktury V této kapitole budou pomoc´ı poznatk˚ u z minulé kapitoly definovány pojmy relaˇcn´ı struktura, pravé a levé okol´ı prvku a kongruence na relaˇcn´ıch strukturách.

2.1 Obecn´ e vlastnosti Definice 2.1 Mˇejme libovolnou mnoˇzinu A a libovolnou n-árn´ı relaci R takovou, ˇze plat´ı R ⊆ An a R 6= ∅, pak struktura S = (A; R) je relaˇcn´ı struktura. Definice 2.2 Je dána relaˇcn´ı struktura S = (A; R), kde R ⊆ A2 . 1. Mnoˇzina PR (x) se naz´ yvá pravým okol´ım prvku x. PR (x) je mnoˇzina obsahuj´ıc´ı prvky, s nimiˇz je x v relaci na pravém m´ıstˇe, formálnˇe PR (x) = {y ∈ A | xRy}. 2. Mnoˇzina LR (x) se naz´ yvá levým okol´ım prvku x. LR (x) je mnoˇzina

18

obsahuj´ıc´ı prvky, s nimiˇz je x v relaci na levém m´ıstˇe, formálnˇe LR (x) = {y ∈ M | yRx}. T´ımto zp˚ usobem m˚ uˇzeme okol´ı definovat pouze d´ıky binárnosti relace R.

2.2 Kongruence na relaˇ cn´ıch struktur´ ach Definice 2.3 Kongrunce na relaˇcn´ı struktuˇre s libovolnou binárn´ı relac´ı, obvykle znaˇcená θ, je ekvivalence. Pro tˇr´ıdy této ekvivalence plat´ı, ˇze vˇsechny prvky y libolné tˇr´ıdy x/θ maj´ı ke vˇsech ostatn´ım prvk˚ um stejn´ y vztah jako reprezentant tˇr´ıdy, tedy formálnˇe ∀y ∈ x/θ : (xRz ⇒ yRz)∧(zRx ⇒ zRy)∧((x; z), (z; x) ∈ / R ⇒ (y; z), (z; y) ∈ / R). Relaˇcn´ı struktura S = (A; R) faktorizovaná kongruenc´ı θ se znaˇc´ı S/θ = (A/θ; R/θ). A/θ je mnoˇzina vˇsech tˇr´ıd kongruence a relace R/θ ukazuje vztahy mezi jednotliv´ ymi tˇr´ıdami. Plat´ı pro ni ∀x, y ∈ A : xRy ⇒ x/θ(R/θ)y/θ, tˇr´ıdy kongruence maj´ı tedy mezi sebou stejn´ y vztah jako jejich prvky, coˇz odpov´ıdá prvn´ı ˇcásti definice.

Ekvivalence θ je tedy kongruenc´ı na relaˇcn´ı struktuˇre S tehdy a jen tehdy, je-li S/θ relaˇcn´ı struktura. Definice 2.4 Mˇejme relaˇcn´ı strukturu S = (A; R), kde R ⊆ A2 . Kongruence, kde je tˇr´ıdou kongruence celá mnoˇzina A, anebo jsou tˇr´ıdami kongruence jen samotné prvky z A, se naz´ yvaj´ı triviáln´ı kongruence. 19

Pˇr´ıklad • Mˇejme relaˇcn´ı strukturu J = (A; J), kde |A| = 3 a J je reflexivn´ı, tranzitivn´ı a u ´plná.

Obrázek 5: Faktorizace J netriviáln´ımi kongruencemi

20

Kapitola 3 Turnaje a jejich vlastnosti V této kapitole jsou definovány turnaje a jsou zavedeny cyklické a tranzitivn´ı turnaje a jsou popsány jejich vlastnosti.

3.1 Obecn´ e vlastnosti turnaj˚ u Definice 3.1 Je dána relaˇcn´ı struktura T = (A; T ). Je-li T reflexivn´ı, antisymetrická au ´plná (Definice 1.11), pak relaˇcn´ı struktura T = (A; T ) je turnaj. Vˇ eta 3.1 Mˇejme turnaj T = (A; T ), kde |A| = n. Rozdˇel´ıme-li relaci T na podmnoˇzinu T1 ⊆ T takovou, ˇze plat´ı T1 = {(x; x) | x ∈ A} (existence této mnoˇziny plyne z reflexivity T ), a podmnoˇzinu T2 ⊆ T takovou, ˇze T2 = T \T1 , která tedy 2 obsahuje vˇsechny ostatn´ı uspoˇra´dané dvojice. Pak |T2 | = n 2−n . Také m˚ uˇzeme ˇr´ıct, ˇze jak´ ykoliv turnaj lze korektnˇe definovat pomoc´ı T2 . D˚ ukaz. Existuj´ı nejménˇe tˇri vysvˇetlen´ı: algebraické, geometrické a kombinatorické. Uvedeme je v tomto poˇrad´ı. Pro kaˇzdou n-prvkouvou mnoˇzinu existuje právˇe n2 uspoˇra´dan´ ych dvojic. 21

V´ıme, ˇze relace T je reflexivn´ı, nemus´ıme tedy uvádˇet uspoˇra´dané dvojice tvaru xT x (∀x ∈ A) (tyto uspoˇra´dané dvojice náleˇz´ı do T1 ), t´ım se poˇcet uspoˇra´dan´ ych dvojic sn´ıˇz´ı na n2 − n. V´ıme, ˇze relace je antisymetrická, tedy, ˇze plat´ı ∀x, y ∈ A, x 6= y : xT y ∨ yT x, t´ım pádem se poˇcet uspoˇrádan´ ych n2 −n dvojic sn´ıˇz´ı o polovinu na 2 . Pˇredstav´ıme-li si, turnaj definovan´ y relac´ı T na n-prvkové mnoˇzinˇe jako n-´ uheln´ık pro n ≥ 3 (bod pro n = 1, nebo u ´seˇcku pro n = 2). V´ıme, ˇze podle u ´plnosti relace T mus´ı doj´ıt ke spojen´ı vˇsech bod˚ u. Pak poˇcet uspoˇrádan´ ych n(n−3) n2 −n dvojic je roven souˇctu u ´hlopˇr´ıˇcek a stran, tedy n + 2 = 2 . Uspoˇra´danou dvojici je moˇzno si pˇredstavit jako dvouprvkovou podmnoˇzi nu n-prvkové mnoˇziny A, kter´ ych je právˇe n2 .7 Vˇ eta 3.2 Mˇejme turnaj T = (A; T ), pak pro vˇsechna x ∈ A plat´ı PT (x) ∩ LT (x) = {x} PT (x) ∪ LT (x) = A.

D˚ ukaz. Z reflexivity relace T vypl´ yvá, ˇze plat´ı ∀x ∈ A : xT x, d˚ usledkem toho je, ˇze plat´ı ∀x ∈ A : x ∈ PT (x) ∧ LT (x). Z antisymetriˇcnosti plyne, ˇze neexistuje takové y 6= x, ˇze plat´ı xT y ∧ yT x. Tvrzen´ı PT (x) ∩ LT (x) = {x} je tedy pravdivé. V pˇredchoz´ı ˇca´sti jsme dokázali, ˇze ∀x ∈ A : x ∈ PT (x) ∧ LT (x). Relace T je antisymetrická a u ´plná, mus´ı tedy platit ∀x, y ∈ A, y 6= x : xT y nebo 7

Ovˇeˇren´ı rovnosti:

n n(n − 1)(n − 2)! n2 − n = = 2 2!(n − 2)! 2

22

yT x, z toho plyne, ˇze plat´ı ∀x, y ∈ A, y 6= x : y ∈ PT (x), nebo y ∈ LT (x). Z toho plyne platnost PT (x) ∪ LT (x) = A.

3.2 Struktura turnaj˚ u Definice 3.2 Cyklický turnaj je takov´ y turnaj C = (A; T ), kde plat´ı ∀x ∈ A ∃y ∈ A : LT (x)\{x} = PT (y)\{y}.

Obrázek 6: Cyklická trojice Pˇred t´ım, neˇz vyslov´ıme dalˇs´ı vˇety, zejdnoduˇsme znaˇcen´ı tak, ˇze LT (x)\{x} a PT (x)\{x} oznaˇc´ıme LT (x) a P T (x). Vˇ eta 3.3 Máme-li cyklick´ y turnaj C = (A; T ), kde A je koneˇcná, pak A má lich´ y poˇcet prvk˚ u. D˚ ukaz. V´ıme, ˇze máme-li cyklick´ y turnaj C = (A; T ) pak mus´ı b´ yt splnˇeno, ˇze ∀x ∈ A ∃y ∈ A : LT (x) = P T (y) (Definice 3.3). Dokáˇzeme, ˇze existuje jen jedno takové y. Uvaˇzujme, ˇze LT (x) = P T (y) = P T (z). Ovˇsem podle antisymetriˇcnosti a u ´plnosti relace T mus´ı platit, ˇze yT z ∨ zT y, proto mus´ı platit, ˇze y ∈ P T (z) ∨ z ∈ P T (y), pˇredpokládali jsme ale, ˇze y ∈ / P T (y) a také z ∈ P T (z), docház´ıme tedy ke sporu.

23

Definujme tedy jednoznaˇcné zobrazen´ı s : A −→ A takové, ˇze ∀x, y ∈ A : s(x) = y ⇔ LT (x) = P T (y). Z v´ yˇse dokázaného faktu m˚ uˇzeme vyvodit dalˇs´ı vlastnost tohoto zobrazen´ı s(x) = s(y) ⇒ x = y. Pomoc´ı zobrazen´ı s m˚ uˇzeme tedy definovat mnoˇzinu {s0 (x), s1 (x), . . . , sn (x)}, kde s0 = x, s1 (x) = s(x), s2 (x) = s(s(x)) . . . sn (x), také plat´ı, ˇze ∀i, j ∈ {0, 1, . . . , n} : si (x) = sj (x) ⇔ i = j. Protoˇze A je koneˇcná mnoˇzina, mus´ı tedy takové n ∈ N existovat. Dokáˇzeme, ˇze v´ yˇse definovaná mnoˇzina je cyklus, proto mus´ı platit, ˇze s(x)n+1 = s0 (x). Pˇredpokládejme, ˇze s(x)n+1 = si (x), kde i ∈ {1, . . . , n}. Potom ale z v´ yˇse dokázan´ ych skuteˇcnost´ı plyne, ˇze s(x)n = si−1 (x), coˇz je ale spor s t´ım, ˇze s(x)n , si−1 (x) ∈ {s0 (x), s1 (x), . . . , sn (x)}. Proto i ∈ / {1, . . . , n}, ale i = 0. Dokáˇzeme, ˇze máme-li mnoˇzinu {s0 (x), s1 (x), . . . , sn (x)}, pak n je sudé. Z definice zobrazen´ı s plyne, ˇze x ∈ / LT (x) = P T (s(x)), proto mus´ı platit, ˇze 2 usledkem toho je, ˇze x ∈ / LT (s2 (x)) = x ∈ LT (s(x)) = P T (s (x)) (Vˇeta 3.2). D˚ P T (s3 (x)), a tedy x ∈ LT (s3 (x)) = P T (s4 (x)) atd. Toto m˚ uˇzeme zobecnit • pro i liché plat´ı, ˇze x ∈ LT (si (x)) = P T (si+1 (x)), • pro i sudé plat´ı, ˇze x∈ / LT (si (x)) = P T (si+1 (x)). Mus´ı tedy platit, ˇze pˇredpokládané n mus´ı b´ yt sudé, protoˇze pokud by n bylo 24

liché, pak by platilo, ˇze x ∈ LT (sn (x)) = P T , toto je spor s x ∈ / P T (x). Je nutné dokázat, ˇze neexistuje ˇza´dné y takové, ˇze y ∈ A, ale y ∈ / 1 n {s (x), s (x), . . . , s (x)}, tedy takové které by bylo v mnoˇzinˇe A, ale bylo by mimo cyklus. Pˇredpokládejme, ˇze y ∈ LT (x) = P T (s(x)), m˚ uˇzeme pouˇz´ıt zobecnˇen´ı v´ yˇse 0

• pro i sudé plat´ı, ˇze y ∈ LT (si (x)) = P T (si+1 (x)), • pro i liché plat´ı, ˇze y∈ / LT (si (x)) = P T (si+1 (x)). Protoˇze n je sudé, pak mus´ı platit, ˇze y ∈ P T (x), toto je ale spor s pˇredpokladem (Vˇeta 3.2). Vˇ eta 3.4 Pro kaˇzd´ y cyklick´ y turnaj C = (A; T ), kde |A| = n, plat´ı, ˇze pravá i levá . okol´ı vˇsech prvk˚ u maj´ı stejn´ y poˇcet prvk˚ u, kter´ ych je právˇe n−1 2 D˚ ukaz. Uvaˇzujme zobrazen´ı s : A −→ A takové, ˇze ∀x, y ∈ A : s(x) = y ⇔ LT (x) = P T (y), kde, pro kaˇzdé i ∈ {0, 1, . . . , m} je LT (si (x)) = P T (si+1 (x)) (Vˇeta 3.3). Z toho vˇsak plyne, ˇze |P T (si (x))| = |LT (si+1 (x))|, protoˇze plat´ı, ˇze ∀x ∈ A : LT (x) = (A\{x})\(P T (x)) (Vˇeta 3.2). M˚ uˇzeme ˇr´ıct, ˇze pro kaˇzdé i plat´ı, ˇze . . . |LT (si (x))| = |P T (si+1 (x))| = |LT (si+2 (x))| . . . . . . |P T (si (x))| = |LT (si+1 (x))| = |P T (si+2 (x))| . . . Uvaˇzujme, ˇze i = 0, potom pro n, které je sudé (Vˇeta 3.3), mus´ı platit, ˇze |LT (si (x))| = · · · = |LT (sn (x))|, pro které ale plat´ı, ˇze LT (sn (x)) = P T (x) 25

(Definice 3.3; Vˇeta 3.3). Ovˇsem P T (x) náleˇz´ı do druhé ˇrady okol´ı se stejn´ ym poˇctem prvk˚ u, mus´ı tedy platit, ˇze vˇsechna okol´ı maj´ı stejn´ y poˇcet prvk˚ u. Protoˇze je turnaj C = (A; T ) cyklick´ y, pak |A| = n je liché (Vˇeta 3.3). Pravá i levá okol´ı vˇsech prkv˚ u v A maj´ı stejn´ y poˇcet prvk˚ u. V´ıme, ˇze LT (x)∪ P T (y) = A\{x}, kde |A\{x}| = n − 1 (Vˇeta 3.2). Plat´ı tedy, ˇze poˇcet prvk˚ u n−1 prav´ ych i lev´ ych okol´ı v A je roven 2 . Vˇ eta 3.5 Pro kaˇzdou mnoˇzinu A, kde |A| = n existuje právˇe n−4 Y i=0

n − 2i − 1 2

2 ! n−1 n−1 2

cyklick´ ych turnaj˚ u C = (A; T ). D˚ ukaz. Kaˇzd´ y cyklick´ y turnaj C = (A; T ) mus´ı splˇ novat ∀x ∈ A ∃y ∈ A : LT (x) = P T (y) (Definice 3.2). Vˇsechna okol´ı mus´ı m´ıt stejn´ y poˇcet prvk˚ u, n−1 kter´ ych je právˇe 2 (Vˇeta 3.4). Z ˇcehoˇz plyne, ˇze pravé okol´ı tvoˇr´ı libo volná kombinace n−1 prvk˚ u. Plat´ı, ˇze ke kaˇzdé kombinaci z n−1 existuje n−1 n−1 2 2 právˇe jedna dalˇs´ı kombinace, které dohromady dávaj´ı n − 1, z ˇcehoˇz plyne, ˇze polovina takovéto dvojice tvoˇr´ı levé, nebo pravé okol´ı tedy existuje právˇe n−1 moˇznost´ı vytvoˇren´ı pravého a levého okol´ı, t´ım pádem je jich je právˇe n−1 2 polovina. Nezávis´ı ale na poˇrad´ı tedy existuje dvojnásobek této poloviny, coˇz moˇznost´ı uspoˇra´dán´ı okol´ı prvku v cyklickém turnaji. je právˇe n−1 n−1 2

V´ıme, ˇze ∀x ∈ A ∃y ∈ A : LT (x) = P T (y) (Definice 3.2). Uvaˇzujme tedy, ˇze máme prvek x ∈ A, protoˇze |LT (x)| = n−1 , pak mus´ı existovat právˇe 2 n−1 1 moˇznost´ı pro s (x). Pˇredpokládejme, ˇze jsme LT (x) pˇriˇradi jako pravé 2 okol´ı k s1 (x), plat´ı, ˇze |LT (s1 (x))| = n−1 a ˇze neexistuje ˇza´dné zaplnˇené 2 1 pravé okol´ı kromˇe s (x), mus´ı tedy existovat právˇe n−1 moˇznost´ı pro s2 (x). 2 Pˇredpokládejme, ˇze jsme LT (s1 (x)) pˇriˇradi jako pravé okol´ı k s2 (x), plat´ı, ˇze |LT (s2 (x))| = n−1 , ale uˇz existuje jedno zaplnˇené pravé okol´ı s1 (x), mus´ı tedy 2 26

existovat právˇe je

n−1 2

− 1 moˇznost´ı pro s3 (x). M˚ uˇzeme tedy ˇr´ıct, ˇze moˇznost´ı

2 2 2 n−1 n−3 n−5 . . . 12 , 2 2 2 Q n−4 n−2i−1 2 coˇz m˚ uˇzeme zobecnit na . i=0 2

Tato uspoˇrádán´ı jsou, pro stjené mohutnosti, izomorfn´ı, protoˇze je m˚ uˇzeme 0 1 n navzájem na sebe bijektivnˇe zobrazit pˇres cyklus {s (x), s (x), . . . , s (x)}, libovolnou volbou s0 (x) a pro odpov´ıdaj´ıc´ı n. Vˇ eta 3.6 Mˇejme cyklick´ y turnaj C = (A; T ), kde |A| = n, existuje-li podmnoˇzina M ⊆ LT (x), nebo M ⊆ P T (x), kde |M | = m, pak existuje právˇe n − 2m + 1 2 prvk˚ u, v jejichˇz stejném okol´ı se nacház´ı podmnoˇzina M . D˚ ukaz. Turnaj C = (A; T ), kde |A| = n, má 2n okol´ı. Podmnoˇzina M se nem˚ uˇze nacházet v ˇza´dném okol´ı nˇejakého prvku z M , protoˇze z okol´ı vyluˇcujeme samotné prvky, tedy okol´ı je 2n − 2m, podmnoˇzina M se nem˚ uˇze nacházet v obou okol´ıch jednoho prvku zároveˇ n, tedy 2n−2m = n−m. Protoˇze 2 ve sjednocen´ı okol´ı prvk˚ u z M se podmnoˇzina M nacház´ı právˇe m − 1 krát (Vˇeta 3.2). Podle definice cyklického turnaje bude existovat právˇe m − 1 prvk˚ u, pro které bude pouze platit, ˇze M ⊆ LT (x) ∪ P T (x), ne vˇsak jen v jednom z okol´ı. Plat´ı tedy, ˇze poˇcet okol´ı, ve kter´ ych je M podmnoˇzinou, je n − (m − 1) − m = n − 2m + 1. Jelikoˇz poˇc´ıtáme jen pravá, nebo levá okol´ı, proto z definice cyklického turnaje plyne, ˇze poˇcet takov´ ychto okol´ı je právˇe n−2m+1 (Vˇeta 3.4). 2 27

Definice 3.2 Tranzitivn´ı turnaj je takov´ y turnaj T = (A; T ), kde plat´ı ∀x, y, z ∈ A : xT y ∧ yT z ⇒ xT z.

Obrázek 7: Tranzitivn´ı trojice Definice 3.4 Mˇejme turnaj T = (A; T ). 1. Prvek x se naz´ yvá nejvˇetˇs´ı prvek turnaje, jestliˇze ∃x ∈ A, ∀y ∈ A : xT y. 2. Prvek z se naz´ yvá nejmenˇs´ı prvek 8 turnaje, jestliˇze ∃z ∈ A ∀y ∈ A, y 6= z : yT z. Vˇ eta 3.7 Koneˇcn´ y turnaj, do kterého nelze vnoˇrit cyklick´ y turnaj, obsahuje nejvˇetˇs´ı a nejmenˇs´ı prvek a je tranzitivn´ı. 9 D˚ ukaz. Pokud by existoval turnaj, kde by neexistoval nejvˇetˇs´ı a nejmenˇs´ı prvek a nebylo by moˇzné do nˇej vnoˇrit cyklick´ y turnaj, pak by muselo platit, ˇze existuj´ı skupiny/a nesrovnateln´ ych prvk˚ u, coˇz by ale znamenalo, ˇze 8

Z u ´plnosti relace T vypl´ yv´ a moˇznost existence pouze jednoho nejvˇetˇs´ıho nebo nejmenˇs´ıho prvku.

28

prvky tˇechto skupin/y tvoˇr´ı cyklické/´ y turnaj/e, coˇz ale vede ke sporu, jelikoˇz pˇredpokládáme, ˇze nelze do turnaje vnoˇrit cyklyck´ y turnaj. Pokud do nˇejakého turnaje nelze vnoˇrit cyklick´ y turnaj C, pak mus´ı platit, ˇze vˇsechny trojice jsou tranzitivn´ı, a tedy je cel´ y turnaj tranzitivn´ı. Vˇ eta 3.8 Tranzitivn´ı turnaje jsou lineárn´ımi svazy. D˚ ukaz. Nelze-li do turnaje vnoˇrit cylick´ y turnaj, pak obsahuje pouze tranzitivn´ı trojice, t´ım pádem je relace T tranzitivn´ı. Z definice relace T vypl´ yvá, ˇze je reflexivn´ı a antisymetrická. Relace T je tedy relac´ı uspoˇrádán´ı. Protoˇze je relace T u ´plná, uspoˇra´dán´ı je lineárn´ı. Z pˇredchoz´ı vˇety plyne, ˇze takov´ y turnaj má nejvˇetˇs´ı a nejmenˇs´ı prvek, je tedy svazem.

9 Existuj´ı ovˇsem i turnaje s nejvˇetˇs´ım a nejmenˇs´ım prvkem, do kter´ ych lze vnoˇrit cyklick´ y turnaj, a proto tato vˇeta neplat´ı opaˇcnˇe.

29

Kapitola 4 Kongruence na turnaj´ıch Tato kapitola se vˇenuje zaveden´ı kongruenc´ı na turnaj´ıch, jejich vlastnostem a simple turnaj˚ um a jejich vlastnostem. V této kapitole jsou vyuˇzity v´ ysledky vˇet z pˇredchoz´ı kapitoly k d˚ ukazu vˇet t´ ykaj´ıc´ıch se kongruenc´ı, jejich konstrukce a simple turnaj˚ u.

4.1 Vlastnosti kongruenc´ı Definice 4.1 Mˇejme turnaj T = (A; T ), pak θ ∈ EqA je kongruence, jestliˇze T /θ = (A/θ; T /θ) je turnaj (Definice 2.3). Vˇ eta 4.1 θ je kongruence jen tehdy, kdyˇz pro vˇsechna x/θ 6= y/θ, taková, ˇze xT y, plat´ı ∀a ∈ x/θ ∀b ∈ y/θ : aT b. D˚ ukaz. Pˇredpokládejme, ˇze θ je kongruence, pak T /θ je turnaj a zároveˇ n xT y, mus´ı tedy platit, ˇze x/θ (T /θ) y/θ, a nem˚ uˇze platit y/θ (T /θ) x/θ, protoˇze T /θ je turnaj a zároveˇ n x/θ 6= y/θ (Definice 2.3). Tedy pro ˇzádné a ∈ x/θ, b ∈ y/θ neplat´ı, ˇze bT a, protoˇze potom b/θ = y/θ (T /θ) a/θ = x/θ,

30

pak tedy nutnˇe aT b. Dokáˇzeme, ˇze T /θ je reflexivn´ı. Jelikoˇz xT x, pak mus´ı platit, ˇze ∀x/θ ∈ T /θ : x/θ(T /θ)x/θ, protoˇze T /θ je turnaj. Dokáˇzeme, ˇze T /θ je antisymetrická. Pokud by platilo, ˇze x/θ (T /θ) y/θ∧ y/θ (T /θ) x/θ, pak by ∃a1 ∈ x/θ ∃b1 ∈ y/θ : a1 T b1 , ale také ∃a2 ∈ x/θ ∃b2 ∈ y/θ : b2 T a2 . Pˇredpokládáme-li ale, ˇze x/θ 6= y/θ a ˇze xT y, pak plat´ı pouze ∃a1 ∈ x/θ ∃b1 ∈ y/θ : a1 T b1 , coˇz vede ke sporu. Dokáˇzeme, ˇze T /θ je u ´plná. Mˇejme x/θ, y/θ ∈ T /θ, protoˇze T je turnaj, pak mus´ı platit, ˇze xT y, nebo yT x, a protoˇze T /θ je turnaj pak, x/θ (T /θ) y/θ, nebo y/θ (T /θ) x/θ. Vˇ eta 4.2 Mnoˇzina vˇsech kongruenc´ı na T , obvykle znaˇcená ConT , pˇri uspoˇra´dán´ı mnoˇzinovou inkluz´ı tvoˇr´ı svaz (ConT ; ⊆) (Definice P2.5). D˚ ukaz. Z definice kongruence vypl´ yvá, ˇze je to taková ekvivalence na relaˇcn´ı struktuˇre, ˇze T /θ = (A/θ; T /θ) je turnaj. Pokud je kongruence ekvivalence, pak plat´ı, ˇze prvky jsou ekvivalentn´ı, náleˇz´ı-li do stejné tˇr´ıdy (Definice 1.12). Kongruence je tedy mnoˇzina uspoˇra´dan´ ych dvojic. M˚ uˇzeme tedy pˇredpokládat, ˇze kongruence jsou uspoˇrádány mnoˇzinovou inkluz´ı, která je relac´ı uspoˇrádán´ı. Z definice ekvivalence plyne, ˇze mezi poˇctem tˇr´ıd a poˇctem uspoˇra´dan´ ych dvojic v ekvivalenci je nepˇr´ımá u ´mˇera. Tedy, m˚ uˇzeme ˇr´ıct, ˇze nejvˇetˇs´ım a nejmenˇs´ım prvkem svazu kongruenc´ı jsou triviáln´ı kongruence (Definice 2.4).

31

Vˇ eta 4.3 Mˇejme turnaj T = (A; T ) a mnoˇzinu M takovou, ˇze M ⊆ A, pak plat´ı LT (M ) ∪ P T (M ) = A\M ⇔ ∃θi ∈ ConT ∀x ∈ M : M = x/θi , kde LT (M ) =

T

x∈M (LT (x))

a P T (M ) =

T

x∈M (P T (x)).

D˚ ukaz. Pokud existuje M ⊆ A taková, ˇze ∃θi ∈ ConT ∀x ∈ M : M = x/θi , pak plat´ı (Vˇeta 4.1), ˇze ∀x ∈ M ∀a ∈ A\M : xT a ∨ aT x, tedy plat´ı, ˇze ∀x ∈ M ∀a ∈ A\M : a ∈ PT (x) ∨ a ∈ LT (x), z toho plyne, ˇze ∀x ∈ M ∀a ∈ A\M : a ∈

\

PT (x) ∨ a ∈

x∈M

\

LT (x).

x∈M

Plat´ı, ˇze x ∈ M ⇒ x ∈ / A\M , proto plat´ı, ˇze ∀x ∈ M ∀a ∈ A\M : a ∈

\

(P T (x)) ∨ a ∈

x∈M

\

(LT (x)),

x∈M

proto plat´ı, ˇze \

(P T (x)) ∪

x∈M

\

(LT (x)) = A\M.

x∈M

Mus´ıme dokázat i druhou stranu ekvivalence. Protoˇze plat´ı \ x∈M

(P T (x)) ∪

\

(LT (x)) = A\M,

x∈M

32

pak plat´ı, ˇze ∀x ∈ M ∀a ∈ A\M : a ∈

\

(P T (x)) ∪

x∈M

\

(LT (x)).

x∈M

Z ˇcehoˇz plyne, ˇze ∀x ∈ M ∀a ∈ A\M : a ∈ PT (x) ∨ a ∈ LT (x), tedy, ˇze ∀x ∈ M ∀a ∈ A\M : xT a ∨ aT x. M˚ uˇzeme tedy pˇredpokládat, ˇze ∃θi ∈ ConT ∀x ∈ M : M = x/θi , ovˇsem je nutné dokázat, ˇze θi je kongruence (podle Definice 4.1). Pokud je θi kongruence, pak T /θ je turnaj, coˇz je splnˇeno jen tehdy, plat´ı-li ∀a ∈ x/θi ∀b ∈ A\x/θi : aT b ∨ bT a (Vˇeta 4.1). Protoˇze ∀x ∈ M ∀a ∈ A\M : xT a ∨ aT x, pak plat´ı, ˇze ∃θi ∈ ConT ∀x ∈ M : M = x/θi .

4.2 Simple turnaje Definice 4.2 Turnaj S = (A; T ) se naz´ yvá simple, obsahuje-li ConT jen triviáln´ı kongruence (Definice 2.4). Vˇ eta 4.4 Kaˇzd´ y cyklick´ y turnaj C = (A; T ) je simple. D˚ ukaz. Plat´ı, ˇze máme-li cyklick´ y turnaj C = (A; T ), kde |A| = n, existuje-li m-prvková podmnoˇzina M ⊆ LT (x), nebo M ⊆ P T (x), pak existuje právˇe n − 2m + 1 2 33

prvk˚ u v jejichˇz prav´ ych, nebo lev´ ych okol´ı je mnoˇzina M (Vˇeta 3.6). Mˇejme turnaj T = (A; T ) a mnoˇzinu M takovou, ˇze M ⊆ A, pak plat´ı LT (M ) ∪ P T (M ) = A\M ⇔ ∃θi ∈ ConT ∀x ∈ M : M = x/θi , kde LT (M ) =

T

x∈M (LT (x))

a P T (M ) =

T

x∈M (P T (x))

(Vˇeta 4.3).

Mus´ı tedy, platit, ˇze existuje-li kongruence na cyklickém turnaji, pak mus´ı n − 2m + 1 n − 2m + 1 + =n−m 2 2 Plat´ı, ˇze n−2m+1 prvk˚ u má podmnoˇzinu M o mohutnosti m ve stejn´ ych 2 okol´ıch (Vˇeta 3.6), podle vˇety o konstrukci kongruenc´ı (Vˇeta 4.3) by tedy muselo platit, ˇze by tato mohutnost musela b´ yt rovna n − m, aby existovala ´ kongruence, kde M je tˇr´ıda kongruence. Upravou rovnice z´ıskáme n − 2m + 1 = n − m, coˇz vede k v´ ysledku m=1 Má-li ovˇsem tˇr´ıda takovéto kongruence mohutnost rovnu 1, pak se také jedná o triviáln´ı kongruenci. Z tohoto plyne, ˇze na libovolném cyklickém turnaji nelze zkonstruovat jinou neˇz triviáln´ı kongruenci, pˇriˇcemˇz tento fakt odpov´ıdá definici simple turnaje (Definice 4.2). Kaˇzd´ y cyklick´ y turnaj C = (A; T ) je tedy simple. Vˇ eta 4.5 Mˇejme turnaj T = (A; T ), kde A = |n|, pokud do nˇej nelze vnoˇrit cyklick´ y turnaj, pak plat´ı, ˇze nem˚ uˇze b´ yt simple pro n > 2. D˚ ukaz. Podle v´ yˇse dokázané vˇety plat´ı, ˇze kaˇzd´ y turnaj T = (A; T ), do kterého nelze vnoˇrit cyklick´ y turnaj, obsahuje nejvˇetˇs´ı prvek, nazvˇeme ho a, 34

a nejmenˇs´ı prvek, nazvˇeme ho z (Vˇeta 3.7). Podle jejich definice (Definice 3.4) a vˇety o konstrukci kongruenc´ı (Vˇeta 4.3) plat´ı, ˇze existuj´ı kongruence θi , θj ∈ ConT takové, ˇze A\(z/θi ) a A\(a/θj ), protoˇze plat´ı ∀x ∈ A\{a} : a ∈ LT (x) a také ∀y ∈ A\{z} : z ∈ P T (y). Tyto kongruence jsou netriviáln´ı pro mnoˇzinu A s mohutnost´ı n > 2.10 Z této vˇety také plyne, ˇze nejvˇetˇs´ı moˇzná mohutnost pravého, nebo levého okol´ı kaˇzdého prvku v simple turnaji je právˇe n − 2, pokud by to tak nebylo, pak by nebyl simple, coˇz vypl´ yvá z vˇet v´ yˇse (Vˇeta 4.3, Vˇeta 4.5). V kontextu tohoto m˚ uˇzeme tedy definovat podm´ınku pro simple turnaje. Vˇ eta 4.6 Pro kaˇzd´ y simple turnaj S = (A; T ), kde |A| = n, a libovolnou netriviáln´ı (toto oznaˇcen´ı vycház´ı z definice triviáln´ıch kongruenc´ı - Definice 2.4) podmnoˇzinu M ⊂ A, kde |M | = m, pak mus´ı platit, ˇze m + mP + mL ≤ n − 1, oznaˇc´ıme-li |P T (M )| = mP a analogicky |LT (M )| = mL (Vˇeta 4.3). D˚ ukaz. Platilo-li by, ˇze m + mP + mL > n − 1, pak by existovala jediná moˇznost, tedy m + mP + mL = n, coˇz by ale znamenalo, ˇze M podle vˇety o konstrukci kongruenc´ı (Vˇeta 4.3) by existovala netriviáln´ı kongruence, kde by byla podmnoˇzina M tˇr´ıdou kongruence, a turnaj by tedy nebyl simple (Definice 4.2), coˇz je spor. 10

Tato vˇeta plat´ı, i pro turnaje s nejvˇetˇs´ım a nejmenˇs´ım prvkem, i kdyˇz do nich lze vnoˇrit cyklick´ y turnaj, protoˇze se v d˚ ukazu nepˇredpokládá tranzitivita, kterou maj´ı jen turnaje, do kter´ ych nelze vnoˇzit cyklick´ y turnaj (Vˇeta 3.8), ale pouze existence nejvˇetˇs´ıho a nejmenˇs´ıho prvku.

35

Kapitola 5 Aplikace v´ ysledk˚ u Z definice relaˇcn´ı struktury plyne, ˇze k jej´ı konstrukci je nutná mnoˇzina a neprázdná relace na n´ı, pro turnaje plat´ı, ˇze tato relace mus´ı b´ yt reflexivn´ı, antisymetrická a u ´plná. Pomoc´ı matematického aparátu popsaného v pˇredcházej´ıc´ıch kapitolách je moˇzné tyto systémy analyzovat. V´ ypoˇctová ˇca´st prezentovan´ ych v´ ysledk˚ u asi nen´ı u ´ˇcinˇeji aplikovatelná, proto se nejslibnˇeji jev´ı aplikace vlastnost´ı kongruenc´ı na turnaj´ıch. Turnaje mohou slouˇzit k modelován´ı struktur s nekvantifikovateln´ ymi vlastnostmi, kvantifikovatelné vlastnosti se kv˚ uli tranzitivnosti lépe vyjadˇruj´ı uspoˇra´dan´ ymi mnoˇzinami. Jednou z nejslibnˇejˇs´ıch aplikac´ı turnaj˚ u je modelován´ı hierarchick´ ych vztah˚ u v sociáln´ıch skupinách a z nich vycházej´ıc´ıch sociáln´ıch kongruenc´ı tzn. rozdˇelen´ı sociáln´ı skupiny na r˚ uzné skupiny podle r˚ uzn´ ych kongruenc´ı, nebo i jin´ ych vlastnost´ı. Pomoc´ı turnaj˚ u lze také vyjadˇrovat vztahy ve zv´ıˇrec´ıch sociáln´ıch skupinách, t´ımto se zab´ yvá [Lan]. Kromˇe jin´ ych existuj´ı i aplikace cyklick´ ych turnaj˚ u v teorii volby a teorii v´ ybˇeru. Jako pˇr´ıklad m˚ uˇze slouˇzit [Lit].

5.1 S´ıtˇ e a jejich vlastnosti Abychom mohli modelovat sloˇzitˇejˇs´ı struktury mus´ıme zavést pojem s´ıtˇe, 36

tedy relaˇcn´ı struktury, u které se nepˇredpokládá u ´plnost relace a která je logick´ ym zobecnˇen´ım turnaje. Definice 5.1 Je dána relaˇcn´ı struktura N = (A; R). Je-li R reflexivn´ı a antisymetrická (Definice 1.11) a splˇ nuje podm´ınky 1. neexistence nesrovnatelného prvku ∀x ∈ A ∃y ∈ A : xRy ∨ yRx, 2. kompaktnosti Pro libovolné disjunktn´ı podmnoˇziny X ⊂ A a Y ⊂ A takové, ˇze X ∪ Y = A, plat´ı ∃x ∈ X ∃y ∈ Y : xRy ∨ yRx pak relaˇcn´ı struktura N = (A; R) je s´ıt’. Pˇr´ımou souvislost s´ıt´ı a turnaj˚ u m˚ uˇzeme ukázat následuj´ıc´ı vˇetou. Vˇ eta 5.1 Pro kaˇzdou s´ıt’ N = (A; R), kde |A| > 1, existuje mnoˇzina T taková, ˇze je mnoˇzinou indexovan´ ych turnaj˚ u T = {Ti = (Ai , Ti ) | i ∈ I} (DefiS nice 3.1), kde I je libovolná indexová mnoˇzina, takov´ ych, ˇze Ti ∈T Ti = N a ∀i, j ∈ I, i 6= j : |Ai ∩ Aj | ≤ 1. D˚ ukaz. Uvaˇzujeme-li rozdˇelen´ı s´ıtˇe N = (A; R) na dvouprvkové turnaje. Uvaˇzujme tedy mnoˇziny |Ai | = 2 a |Aj | = 2, pokud by jejich pr˚ unikem byla dvouprvková mnoˇzina, pak by nutnˇe muselo platit, ˇze i = j, protoˇze v opaˇcném pˇr´ıpadˇe bychom doˇsli ke sporu. Dokázali jsme prvn´ı podm´ınku. Mus´ıme jeˇstˇe dokázat, ˇze kaˇzdou s´ıt’ N = (A; R) je moˇzné rozdˇelit na dvouprvkové turnaje. Plat´ı ∀x ∈ A ∃y ∈ A : xRy ∨ yRx (Definice 5.1), kaˇzd´ y 37

prvek je tedy alespoˇ n v jednom dvouprvkovém turnaji. M˚ uˇzeme tedy ˇr´ıct, ˇze kaˇzdou s´ıt’ lze rozdˇelit na dvouprvkové turnaje, proto existuje alespoˇ n jedno kaˇzdé s´ıtˇe na turnaje, vˇeta tedy plat´ı. 11 Abychom mohli zavést kongruence na s´ıt´ıch, mus´ıme zavedn´ım neutráln´ıch okol´ı zohlednit moˇznou ne´ uplnost relace. Definice 5.2 Je dána s´ıt’ N = (A; R). Mnoˇzina NR (x) se naz´ yvá neutráln´ım okol´ım prvku x. NR (x) je mnoˇzina obsahuj´ıc´ı prvky, s nimiˇz nen´ı x v relaci, formálnˇe NR (x) = {y ∈ A | (x; y) ∈ / R ∧ (y; x) ∈ / R}. M˚ uˇzeme tedy podobnˇe jako u turnaj˚ u (Vˇeta 4.3) ukázat konstrukci kongruenc´ı na s´ıt´ıch. Vˇ eta 5.2 Mˇejme s´ıt’ N = (A; R) a mnoˇzinu M takovou, ˇze M ⊆ A, pak plat´ı LR (M ) ∪ P R (M ) ∪ NR (M ) = A\M ⇔ ∃θi ∈ ConN ∀x ∈ M : M = x/θi , T T uvodem pˇr´ıtomnosti kde LR (M ) = x∈M (LR (x)) a P R (M ) = x∈M (P R (x)), d˚ T NR (M ) = x∈M (NR (x)) je v´ yˇse zm´ınˇená moˇzná ne´ uplnost relace R. D˚ ukaz. Je analogick´ y d˚ ukazu vˇety o konstrukci kongruenc´ı na turnaj´ıch (Vˇeta 4.3), pouze se v tomto d˚ ukazu mus´ı uvaˇzovat jedna moˇznost nav´ıc tedy moˇzná neexistence relace mezi dvˇema prvky. 11

Z podm´ınky kompaktnosti s´ıtˇe (Definice 5.1) plyne existence alespoˇ n jedné dvojice i, j ∈ I, i 6= j takové, ˇze |Ai ∩ Aj | = 1.

38

Neexistuje jediná oblast matematiky, a to jakkoli abstraktn´ı, která by se jednou nedala aplikovat na jevy reálného svˇeta. Nikolaj Ivanoviˇc Lobaˇcevskij12

12

Nikolaj Ivanoviˇ c Lobaˇ cevskij (1792 – 1856), v´ yznamn´ y rusk´ y matematik, kter´ y dok´ azal nedokazetelnost p´ atého Euklidova postulátu z pˇredchoz´ıch ˇctyˇr a objevil hyperbolickou neeuklidovskou geometrii.

39

Z´ avˇ er a diskuse Jak bylo jiˇz nazanˇceno v u ´vodu práce, literatura zkoumaj´ıc´ı turnaje z hlediska algebry témˇeˇr neexistuje, nen´ı tedy prakticky s ˇc´ım v´ ysledky práce porovnávat. Pokus´ım se tedy alespoˇ n dosaˇzené v´ ysledky objektivnˇe zhodnotit, jelikoˇz se jedná o dokázané vˇety, nen´ı tedy nutné mluvit o jejich pravdivosti jako sp´ıˇse o jejich v´ yznamu. Kapitoly 1 a 2 poskytuj´ı obecn´ y u ´vod do problematiky. Kapitola 1 je u ´vodem do algebry, vysvˇetluje pojmy jako mnoˇzina, relace a relace ekvivalence. Kapitola 2 potom struˇcnˇe pˇredstavuje relaˇcn´ı systémy a koncept kongruenc´ı na nich. Kapitola 3 se turnaj˚ um vˇenuje obecnˇe. Vˇeta 3.2 ukazuje obecné vlatsnosti relace T , pozdˇeji je vyuˇzita v d˚ ukazech nˇekolika dalˇs´ıch vˇet. Je moˇzno ˇr´ıct, ˇze nejv´ yznamnˇejˇs´ım v´ ysledkem Kapitoly 3, nen´ı ani tak vˇeta, ale zaveden´ı cyklick´ ych turanj˚ u, a ze kterého jsou postupnˇe vyvozeny vˇety 3.3 - 3.6 popisuj´ıc´ı vlastnosti cyklick´ ych turnaj˚ u. Vˇety 3.3 a 3.4 jsou pouˇzity k d˚ ukazu vˇet 3.5 a 3.6. Nejd˚ uleˇzitˇejˇs´ım z nich je asi vˇeta 3.6 aplikovaná v d˚ ukazu vˇety 4.4 v Kapitole 4. Tranzitivn´ı turnaje byly v Kapitole 3 definovány a byla dokázána jejich souvislost s cyklick´ ymi turnaji. Vˇeta 3.8 ukazuje rovnost tranzitivn´ıch turnaj˚ u a lineárn´ıch svaz˚ u. Kapitola 4 se zab´ yvá kongruencemi na turnaj´ıch a simple turnaji. Vˇeta 4.1 definuje kongruence na turnaj´ıch a ukazuje, ˇze vlastnosti kongruenc´ı na turnaj´ıch odpov´ıdaj´ı vlastnostem kongruenc´ı na relaˇcn´ıch strukturách z definice 2.3. Vˇeta 4.2 definuje svaz kongruenc´ı na turnaji. Vˇeta 4.3 je asi nejd˚ uleˇzitˇejˇs´ım v´ ysledkem celé práce, ukazuje souvislost okol´ı s kongruencemi a konstrukci kongruenc´ı na turnaji, je nezbytná pro d˚ ukaz vˇsech dalˇs´ıch vˇet. Vˇeta 4.4 je v´ yznamn´ ym v´ ysledkem celé práce, d˚ ukazem, ˇze vˇsechny cyklické turnaje jsou simple, zavrˇsuje v´ yznamnou ˇca´st práce, která se vˇenuje cyklick´ ym turnaj˚ um. Vˇeta 4.5 ukazuje pˇredv´ıdatelnou skuteˇcnost, ˇze tranzi40

tivn´ı turnaje nejsou simple za urˇcit´ ych podm´ınek. V´ ysledek vˇety 4.6 vypl´ yvá z definice simple turnaj˚ u a ukazuje základn´ı podmn´ınku simple turnaj˚ u pomoc´ı vˇety 4.3. Kapitola 5 se struˇcnˇe zab´ yvá aplikacemi turnaj˚ u a v´ ysledk˚ u této práce. D˚ uleˇzité v této kaplitole je tvrzen´ı, ˇze turnaje mohou nejlépe slouˇzit k modelován´ı struktur s nekvantifikovateln´ ymi vlastnostmi. Dále se v této kapitole nacház´ı u ´vod od problematiky s´ıt´ı, je uveden jejich vztah s turnaji, dále se tomuto tématu vˇenuje prostor v pˇr´ıloze práce. Práce pˇrináˇs´ı nové v´ ysledky a konstrukce v tématu. Nejd˚ uleˇzitˇejˇs´ımi mezi nimi jsou definice 3.3 a vˇety 3.6, 3.8, 4.3 a 4.4 popˇr´ıpadˇe jeˇstˇe 5.1, 5.2 o vlastnostech s´ıt´ı a kongruenc´ıch na nich, vˇetˇsina ostatn´ıch vˇet je uvedena jako podklad pro d˚ ukazy tˇechto vˇet nebo jejich d˚ usledky. O mnoˇzinˇe c´ılových výsledk˚ u práce C a mnoˇzinˇe vˇsech výsledk˚ u práce V m˚ uˇzeme ˇr´ıct, ˇze C ⊂ V.

41

Seznam pouˇ zit´ eho znaˇ cen´ı ∧

a z´ aroveˇ n (konjunkce)

∨

a nebo (disjunkce)

⇒

a proto (implikace)

⇔

tehdy a jen tehdy (ekvivalece)

∀

pro vˇsechna (obecn´ y kvantifikátor)

∃

pro alespoˇ n jedno (existenˇcn´ı kvantifikátor)

A

mnoˇzina A

a∈A

prvek a n´ aleˇz´ı do mnoˇziny A

b∈ /A

prvek b nen´ aleˇz´ı do mnoˇziny A

∅

pr´ azdn´ a mnoˇzina

|A|

mohutnost mnoˇziny A

A∩B

pr˚ unik mnoˇzin A a B

A∪B

sjednocen´ı mnoˇzin A a B

A\B

rozd´ıl mnoˇzin A a B (v tomto poˇrad´ı)

A×B

kartézsk´ y souˇcin mnoˇzin A a B (v tomto poˇrad´ı)

A⊂B

mnoˇzina A je vlastn´ı podmnoˇzinou B

A⊆B

mnoˇzina A je podmnoˇzinou B

R⊆

A2

bin´ arn´ı relace R na mnoˇzinˇe A

R−1

inverzn´ı relace k bin´ arn´ı relaci R

f (a)

obraz prvku a v zobrazen´ı f

E

relace ekvivalence

x/E

tˇr´ıda ekvivalece E s reprezentantem x

PR (x)

pravé okol´ı prvku x v relaci R

LR (x)

levé okol´ı prvku x v relaci R

S/θ

relaˇcn´ı struktura S faktorizovaná kongruenc´ı θ

x/θ

tˇr´ıda kongruence θ s reprezentantem x

ConA

mnoˇzina vˇsech kongruenc´ı na A

P T (x)

totéˇz jako PT (x)\{x}

LT (x)

totéˇz jako LT (x)\{x} T totéˇz jako x∈M P T (x) T totéˇz jako x∈M LT (x)

P T (M ) LT (M ) NR (x) NR (M )

neutr´ aln´ı okol´ı prvku x v relaci R T totéˇz jako x∈M NR (x)

42

Zdroje Pouˇ zit´ a literatura ˇ V.: Matematika pro gymnázia – Kombinatorika, [Cal] CALDA, E.; DUPAC, pravdˇepodobnost, statistika. 5. vydán´ı. Praha: Prometheus, 2008. ISBN 97880-7196-365-3 [Hor] HORT, Daniel; RACH˚ UNEK, Jiˇr´ı. Algebra I. 1. vydán´ı. Olomouc : Nakladatelstv´ı UP, 2003. Kapitola 2 Mnoˇziny, relace, zobrazen´ı, s. 21 - 32. ISBN 80-244-0631-4. [Rach] RACH˚ UNEK, Jiˇr´ı. Svazy. 1. vydán´ı. Olomouc : Nakladatelstv´ı UP, 2003. Kapitola 1 Základy teorie uspoˇra´dan´ ych mnoˇzin a svaz˚ u, s. 7 - 26. ISBN 80-244-0650-0. [T ru] TRUDEAU, Richard J. Introduction to Graph Therory. 2. vydán´ı. New York: Dover Publications, 1993. ISBN 0-486-67870-9 [W ol1] Wolfram MathWorld : Set [online]. [citováno: 1. ledna 2011]. Dostupné z WWW: http://mathworld.wolfram.com/Set.html Doporuˇ cen´ a literatura [Lan] Landau, H.G. (1953), ”On dominance relations and the structure of animal societies. III. The condition for a score structure”, Bulletin of Mathematical Biophysics 15 (2): 143–148, doi:10.1007/BF02476378. [Lit] Litvakov, Boris M.; Vol’skiy, Vladimir I., 1985. ”Tournament Methods in Choice Theory,”Working Papers 558, California Institute of Technology, Division of the Humanities and Social Sciences. Dostupné z WWW: http://ideas.repec.org/p/clt/sswopa/558.html

43

[W ik1] Wikipedia, the Free Encyclopedia: Pólya enumeration theorem [online]. [citováno: 1. ledna 2011]. Dostupné z WWW: http://en.wikipedia.org/w/index.php?oldid=403769882 [W ik2] Wikipedia, the Free Encyclopedia: Tournament (mathematics) [online]. [citováno: 1. ledna 2011]. Dostupné z WWW: http://en.wikipedia.org/w/index.php?oldid=394551339 [W ol2] Wolfram MathWorld : Tournament [online]. [citováno: 1. ledna 2011]. Dostupné z WWW: http://mathworld.wolfram.com/Tournament.html Pouˇ zit´ e obr´ azky Obrázek 1: Pr˚ unik mnoˇzin Wikimedia Commons: [pˇrevzato: 1. ledna 2011]. Dostupné z WWW: http://commons.wikimedia.org/wiki/File:Venn-and.svg Obrázek 2: Sjednocen´ı mnoˇzin Wikimedia Commons: [pˇrevzato: 1. ledna 2011]. Dostupné z WWW: http://commons.wikimedia.org/wiki/File:Venn-or.svg Obrázek 3: Rozd´ıl mnoˇzin Wikimedia Commons: [pˇrevzato: 1. ledna 2011]. Dostupné z WWW: http://commons.wikimedia.org/wiki/File:Venn-not.svg Obrázek 4: Pˇr´ıklady relac´ı a zobrazen´ı Wikimedia Commons: [pˇrevzato: 1. ledna 2011]. Dostupné z WWW: http://commons.wikimedia.org/wiki/File:Zobrazeni druhy.svg Obrázek 5: Faktorizace J bez triviáln´ıch kongruenc´ı Vlastn´ı tvorba. Vytovoˇreno dne 31. ledna 2011. Obrázek 6: Cyklická trojice 44

Wolfram MathWorld : Cyclic Triple [online]. [pˇrevzato: 1. ledna 2011]. Dostupné z WWW: http://mathworld.wolfram.com/CyclicTriple.html Obrázek 7: Tranzitivn´ı trojice Wolfram MathWorld : Transitive Triple [online]. [pˇrevzato: 1. ledna 2011]. Dostupné z WWW: http://mathworld.wolfram.com/TransitiveTriple.html Obrázek 8: S´ıt’ D4 tzv. diamant schématicky Vlastn´ı tvorba. Vytovoˇreno dne 7. u ńora 2011. Pouˇ zit´ y software TeXShop Version 2.40; LATEX Editor for Mac OS X. Dostupné z WWW: http://pages.uoregon.edu/koch/texshop/ Kile Version 2.0.85; KDE Integrated LATEX Environment. Dostupné z WWW: http://kile.sourceforge.net/ Inkscape Verze 0.48.0 r9654; Editor vektorové grafiky. Dostupné z WWW: http://www.inkscape.org/ GIMP Version 2.6.10; GNU Image Manipulation Program. Dostupné z WWW: http://www.gimp.org/ Ostatn´ı Citáty jsou pˇrevzaty z WWW: http://mathes.cz/citaty.aspx a biografické informace z WWW: http://cs.wikipedia.org/wiki/.

45

Pˇr´ıloha #1

Algoritmus pro rozdˇelov´ an´ı jednoduchých s´ıt´ı na nejvˇetˇs´ı turnaje

46

Definice P.1 Mˇejme s´ıt’ N = (A; R), lze-li do n´ı vnoˇrit s´ıt’ D4 = (B; D), kde |B| = 4 ∧ |D| = 9 tzv. diamant a pˇritom neexistuje ˇza´dn´ y turnaj Ti = (Ai , Ti ) takov´ y, ˇze je moˇzné D4 = (B; J) do nˇej vnoˇrit, pak tato s´ıt’ nen´ı jednoduchá.

Obrázek 8: S´ıt’ D4 tzv. diamant schématicky

Po definici jednoduché s´ıtˇe m˚ uˇzeme pˇrej´ıt k samotnému vytvoˇren´ı a zd˚ uvodnˇen´ı algoritmu.

Algoritmus Uvaˇzujme s´ıt’ N = (A; R), rozdˇelme relaci R na dvˇe disjunktn´ı podmnoˇziny R1 ∪ R2 , kde R1 = {(x; x) ∈ R | x ∈ A}, tedy reflexivn´ı ˇca´st relace R a ˇca´st R2 = R\R1 (podobnˇe Vˇeta 3.1). Tento algoritmus má dva kroky. 1. Pˇredpokládejme, ˇze z mnoˇziny R2 vznikne n pouˇzit´ımi tohoto kroku mnoˇzina R2n . Mnoˇzinu R2n vytvoˇr´ıme jako R2n = R2n−1 \P , kde P = {(x; y) ∈ R2n−1 | @z ∈ A : [(x; z) ∈ R2n−1 ∨ (z; x) ∈ R2n−1 ] ∨ [(y; z) ∈ R2n−1 ∨ (z; y) ∈ R2n−1 ]}, tedy ˇze z mnoˇziny R2n−1 odstran´ıme uspoˇra´dané dvojice takové, ˇze obsahuj´ı prvek, kter´ y uˇz se nevyskytuje v ˇza´dné jiné uspoˇrádané dvojici. Tento krok pokraˇcuje aˇz do okamˇziku, kdy R2n−1 = R2n . Vˇsechny takto odstranˇené dvojice pak tvoˇr´ı dvouprvkové turnaje. 13 13

Tento krok vych´ az´ı z pˇredpokladu, ˇze pro jednouché turnaje existuj´ı jen tˇri druhy

47

2. Pˇredpokládejme, ˇze z mnoˇziny R2n−1 = R2n , která vznikne n pouˇzit´ımi prvn´ıho kroku na mnoˇzinu R2 , mnoˇzina Rn2 . Mnoˇzinu Rn2 vytvoˇr´ıme jako Rn2 = R2n \Q, kde Q = {(x; y) ∈ R2n | @z ∈ A : [(x; z) ∈ R2n ∨ (z; x) ∈ R2n ] ∧ [(y; z) ∈ R2n ∨ (z; y) ∈ R2n ]}, tedy ˇze z mnoˇziny R2n−1 odstran´ıme uspoˇra´dané dvojice takové, které netvoˇr´ı trojprvkové turnaje (ty lze vnoˇrit do v´ıceprvkov´ ych turnaj˚ u). Tento krok je vykonán jednou, poté je znovu vykonán n-krát prvn´ı krok. Vˇsechny takto odstranˇené dvojice pak tvoˇr´ı dvouprvkové turnaje. 14 , pak uˇz jsou v Rn+1 Algoritumus konˇc´ı v pˇr´ıpadˇe, ˇze Rn2 = Rn+1 2 2 jen uspoˇra´dané dvojice prvk˚ u, které tvoˇr´ı turnaje Ti = (Ai , Ti ), kde 15 |Ai | > 2.

jejich z´ akladn´ıch struktur - turnaje Ti = (Ai , Ti ), kde |Ai | > 2, vˇetve, sloˇzené ze za sebou poskl´ adan´ ych dvouprvkov´ ych turnaj˚ u, a spoje mezi nimi, také z dvouprvkov´ ych turnaj˚ u. Tento krok algoritmu odstraˇ nuje vˇetve. 14 Pomoc´ı tohoto kroku se odstraˇ nuj´ı spoje mezi jednotliv´ ymi turnaji Ti = (Ai , Ti ), kde |Ai | > 2, a vˇetvemi. Mohl by aplikovat pouze tento krok, ovˇsem jeho pouˇzit´ı v kombinaci s prvn´ım krokem je v´ yhodnˇejˇs´ı. 15 Rozdˇelen´ı diamantu tzv. D4 = (B; D), kde |B| = 4 ∧ |D| = 9, je t´ımto algoritmem nemoˇzné, protoˇze je nerozhodnutelné (diamant je moˇzné rozdˇelit na dva r˚ uzné trojprvkové turnaje se dvˇema spoleˇcn´ ymi prvky, ovˇsem pˇredpokládané rozdˇelen´ı je na turnaje s maxim´ alnˇe jedn´ım spoleˇcn´ ym prvkem).

48

Pˇr´ıloha #2

Axiomatizace svaz˚ u

49

Definice P2.1 Mˇejme mnoˇzinu A a binárn´ı relaci R takovou, ˇze R ⊆ A2 , relace R se naz´ yvá relac´ı uspoˇrádán´ı, jestliˇze je 1. reflexivn´ı ∀x ∈ A : xRx, 2. antisymetrická ∀x, y ∈ A : xRy ∧ yRx ⇒ x = y, 3. tranzitivn´ı ∀x, y, z ∈ A : (xRy ∧ yRz) ⇒ xRz Pro rozliˇsen´ı budeme relaci uspoˇra´dán´ı znaˇcit ≤. Mnoˇzina s relac´ı uspoˇra´dán´ı se naz´ yvá uspoˇrádaná mnoˇzina a budeme ji znaˇcit A = (A; ≤).

Definice P2.2 Mˇejme uspoˇrádanou mnoˇzinu A = (A; ≤), pak se a ∈ A naz´ yvá • nejvˇetˇs´ı prvek, jestliˇze ∀x ∈ A : x ≤ a • nejmenˇs´ı prvek, jestliˇze ∀x ∈ A : a ≤ x • maximáln´ı prvek, jestliˇze ∀x ∈ A : a ≤ x ⇒ a = x • textitminimáln´ı prvek, jestliˇze ∀x ∈ A : x ≤ A ⇒ a = x 50

Definice P2.3 Mˇejme uspoˇrádanou mnoˇzinu A = (A; ≤) a B ⊆ A, pak • se c ∈ A naz´ yvá horn´ı hranice mnoˇziny B v A, jestliˇze ∀b ∈ B : b ≤ c • se d ∈ A naz´ yvá doln´ı hranice mnoˇziny B v A, jestliˇze ∀b ∈ B : d ≤ b Definice P2.4 • Supremem mnoˇziny B rozum´ıme nejmenˇs´ı prvek c v mnoˇzinˇe vˇsech horn´ıch hranic B v A. Znaˇc´ıme supB = c. • Infimem mnoˇziny B rozum´ıme nejvˇetˇs´ı prvek d v mnoˇzinˇe vˇsech doln´ıch hranic B v A. Znaˇc´ıme supB = d. Definice P2.5 Mˇejme uspoˇrádanou mnoˇzinu A = (A; ≤), pak • se naz´ yvá horn´ı polosvaz, jestliˇze má kaˇzdá jej´ı dvouprvková mnoˇzina supremum. • se naz´ yvá doln´ı polosvaz, jestliˇze má kaˇzdá jej´ı dvouprvková mnoˇzina infimum. • se naz´ yvá svaz, jestliˇze je zároveˇ n horn´ım i doln´ım polosvazem. Máme-li svaz A = (A; ≤), pak tento svaz (Definice P2.5) je také algebrou se dvˇema binárn´ımi operacemi ∧, ∨ : A × A −→ A takov´ ymi ˇze a ∧ b = inf{a, b} a a ∨ b = sup{a, b}, tato skuteˇcnost se znaˇc´ı A = (A; ∧, ∨). [Rach]

51

O vlastnostech turnajů On Properties of Tournaments

Recommend Documents