Příklady
(řešené)
1. Relaci R
znázorněnou na uzlovém grafu doplňte tak, že vytvoříte lineárně
uspořádanou množinu.
Řešení:
Z grafu plyne K = {1, x, 3, z, 5}, R = {(3,1), (z, x), (5, z)}.
Lineárně uspořádanou množinu (K, R) vytvoříme, jestliže v množině K bude
definována relace lineárního uspořádání. Přičemž lineární uspořádání je
relace, která splňuje vlastnosti:
a) antisymetrie, b) tranzitivnosti, c) konektivnosti.
Tzn.
a)

a, b

K :
[a ≠ b

(a, b)

R] => (b,
a)

R,
b)

a,
b, c

K :
[(a,b)

R

(b,c)

R] =>
(a,c)

R,
c)

a,
b

K
: a ≠ b => [(a, b)

R V (b,
a)

R].
Relace je současně antisymetrická a souvislá (tj. konektivní),
pak

a, b

K : a ≠
b => [(a, b)

R

(b,
a)

R].
Na uzlovém grafu znázorníme uvedenou vlastnost tak, že každé dva různé
uzly jsou spojeny právě jednou orientovanou hranou, přičemž vzhledem k
řešení úlohy musí být zachována tranzitivnost. Ostatní vlastnosti
relace R nejsou splněny, tzn. že R není ani reflexivní, ani
antireflexivní; na uzlovém grafu se musí objevit alespoň jedna, nejvýše
však čtyři smyčky.
Relace splňující uvedené podmínky jsou např. tyto:
R
1 = {(5,z), (3,1), (z,x), (5,x), (5,1), (1,x),
(1,z), (5,3), (3,z), (3,x), (x,x)},
(K,R
1) = {5,3,1,z,x}

R
2 =
{(6,z),(3,1),(z,x),(6,x),(5,3),(5,1)(z,3),(z,1),(3,x),(x,1),(x,x),(z,z)},
(K, R
2) = {5,z,3,x,1}
2.
V množině A =
{k,l,m,n} je definována relace U = {(m,n), (l,l), (I, k), (k,n),
(l,n)}. Určete všechny její vlastnosti a nazvěte ji. Bude-li to možné,
doplňte ji minimálním počtem uspořádaných dvojic tak, aby vznikla
relace lineárního uspořádání. Zapište ji.
Řešení:
Relaci U určenou výčtem prvků znázorníme uzlovým grafem:
Relace není reflexivní (nejsou smyčky u všech uzlů).
Relace není antireflexivní (je smyčka alespoň u jednoho uzlu).
Relace není symetrická (např. ke hraně (m,n) není (n,m)).
Relace je antisymetrická (každé dva různé uzly jsou spojeny nejvýše
jednou hranou).
Relace je tranzitivní (podmínka definice je splněna).
Relace není konektivní (každé dva různé uzly nejsou spojeny alespoň
jednou hranou).
Relace U je relací uspořádání.
Máme-li vytvořit relaci lineárního uspořádání, pak relace U musí být i
konektivní. Tato vlastnost bude splněna doplněním uspořádaných dvojic
mezi uzly k, m a I, m; tím vzniknou 3 nové relace U
1
až U
3.
a) U
1 =
{(m,n),(l,l),(l,k),(k,n),(l,n),(l,m),(k,m)}, (A,U
1)
= {l,k,m,n}; I je první a n poslední prvek (A,U
1);
b) U
2 =
{(m,n),(l,l),(l,k),(k,n),(l,n),(l,m),(m,k)}, (A,U
2)
= {I,m,k,n}; I je první a n poslední prvek (A,U
2);
c) U
3 =
{(m,n),(l,l),(l,k),(k,n),(m,l),(m,k),(l,n)}, (A,U
3)
= {m,I,k,n}; m je první a n poslední prvek (A,U
3).
Neřešené
úlohy :
1. Rozhodněte o
typu relace uspořádání R, jestliže R

M x M, kde M = {3,4,5,6},
R = {(4,3),(5,3),(5,4),(6,6),(3,3)}
2. Rozhodněte
o typu relace uspořádání R, jestliže R

M x M, kde M = {3,4,5,6},
R = {(6,3),(6,5),(5,4),(6,4)}
3. Rozhodněte
o typu relace uspořádání R, jestliže R

M x M, kde M = {3,4,5,6},
R = {(4,4),(5,5),(6,6),(3,5),(3,3)}
4. Rozhodněte
o typu relace uspořádání R, jestliže R

M x M, kde M = {3,4,5,6},
R = {(5,5),(5,4),(3,5),(3,4),(6,5),(6,4),(6,3)}
5. Rozhodněte
o typu relace uspořádání R, jestliže R

M x M, kde M = {3,4,5,6},
R = {(6,5),(3,6),(3,5),(4,6),(4,5),(4,3)}
6. Rozhodněte
o typu relace uspořádání R, jestliže R

M x M, kde M = {3,4,5,6},
R = {(3,3),(4,4),(5,5),(6,6),(5,4),(5,3),(5,6),(4,3),(4,6),(6,3)}
7. Ověřte, zda relace U = {(4,1), (2,4),
(3,4), (2, 3),
(3,1), (2,1)} v množině M = {1,2,3,4} je ostré lineární uspořádání;
je-li tomu tak, zapište ostře lineárně uspořádanou množinu.
8. V množině T = {1,2,3,4,5} vytvořte
relaci R lineárního
uspořádání. Tuto relaci znázorněte na uzlovém grafu a zapište ji výčtem
prvků.
9.
Uzlové grafy následujících relací doplňte tak, aby představovaly relace
ostrého lineárního a lineárního uspořádání.

10. V množině L jednociferných lichých
přirozených čísel
zapište relaci lineárního uspořádání U, vytvořte lineárně
uspořádanou množinu (L,U).
11.
Vytvořte relaci U lineárního uspořádání v množině A = {3,4,5,6,7},
víte-li, že prvek 6 je prvním a prvek 3 třetím prvkem (A, R).
12.
Zapište výčtem prvků všechny relace U ostrého lineárního uspořádání v
množině M = {x
N,
x | 4}. Je každé z těchto uspořádání dobré?
13.
Vytvořte alespoň tři relace ostrého lineárního uspořádání v množině A =
{x
C;
x | 5} a graficky je znázorněte.
14.
V množině A = {k, I, m, n, o} vytvořte relaci ostrého lineárního R1
a lineárního uspořádání R2; zapište (A,
R2).
15.
V množině B = {x
C;
2 ≤ x < 7} vytvořte všechny relace ostrého lineárního
uspořádání, platí-li, že sudé číslo předchází před lichým a větší sudé
před menším sudým.
16. V množině A = {1,2,..., 6} je
definována relace T =
{(2, 2), (1, 5), (3, 2), (3,3), (4,4), (1,1), (6, 5), (6,6), (5,5)}.
Určete všechny její vlastnosti a pojmenujte ji.
17. Co musí splňovat množina M, abychom ji
mohli nazvat uspořádanou množinou?
18. Nechť (A, R) je lineárně uspořádaná
množina. Jak se nazývá prvk a

A , jestliže
platí :

x

A
: x ≠ a => a

x
19. Nechť (A, R) je lineárně uspořádaná množina.
Jak se nazývá prvk a

A
, jestliže platí :

x

A
: x ≠ a => x

a
Řešení
:
1. Relace uspořádání.
2. Relace ostrého uspořádání.
3. Relace neostrého uspořádání.
4. Relace lineárního uspořádání.
5. Relace ostrého lineárního uspořádání.
6. Relace neostrého lineárního uspořádání.
7.
Relace U je AR, AS, T,
K; M = {2,3,4,1} je ostře lineárně uspořádaná
množina. K
řešení úlohy můžete využít uzlového grafu.
8. Např.: R = {(3,1), (3,2), (3,4), (3,5),
(4,1), (4, 2), (4,5), (2,1), (2, 5), (1,5), (2,2)}.

9.
a) Nemá řešení, daná relace již není tranzitivní,
b) Např.: ostré lineární
uspořádání
lineární uspořádání

10. L = {1,3,5,7,9}; např.:
U = {(3,1), (3,5), (3, 7), (3,9), (9,1), (9,5), (9,7), (5,1), (7,1),
(7,5), (5,5)},
(L, U) = {3,9,7,5,1}.
11. Např.: U = {(6, 3), (6,4), (6,5), (6,
7), (4,3), (4,5), (4, 7), (3,5), (3,7), (5, 7), (4,4)}.
12.
U1 = {(l,2), (1,4),
(2,4)}, |
U2 = {(1,2), (1,4),
(4,2)}, |
U3 = {(2,1),(2,4),(1,4)}, |
U4 = {(2,1), (2,4),
(4,1)}, |
U5 = {(4,1),(4,2),
(2,1)}, |
U6 = {(4,1),(4,2),
(1,2)}. |
13. A = {1, -1,5, -5}, tj. např.:

14. R
2 = R
1
{(l, l), (k,
k)} tj. (A,R
2) = {o,n,m,l,k}.
15. R
1 = {(2,3),
(2,5), (4,5), (4,3), (6,3), (6,5), (6,4), (6,2), (4,2), (3,5)},.....
R
2 = {(2,3), (2,5), (4,5), (4,3), (6,3), (6,5),
(6,4), (6,2), (4,2), (5,3)}.
16. Vlastnosti relace
T: R, AS,
T;
T je relace neostrého uspořádání.
17. V množině M musí být definována relace
uspořádání.
18. První prvek množiny A.
19. Poslední prvek množiny A.