Hasseovské diagramy
Jan Paseka
Masarykova univerzita Brno
Hasseovské diagramy ­ p.1/8

Grafické znázornění I
Uspořádanou množinu (A, ) můžeme (zejména,
je ­ li množina A konečná) znázorňovat graficky.
Hasseovské diagramy ­ p.2/8

Grafické znázornění I
Uspořádanou množinu (A, ) můžeme (zejména,
je ­ li množina A konečná) znázorňovat graficky.
Postupujeme přitom následujícím způsobem:
Hasseovské diagramy ­ p.2/8

Grafické znázornění I
Uspořádanou množinu (A, ) můžeme (zejména,
je ­ li množina A konečná) znázorňovat graficky.
Postupujeme přitom následujícím způsobem:
1. Prvky množiny A znázorníme jako body
v rovině.
Hasseovské diagramy ­ p.2/8

Grafické znázornění I
Uspořádanou množinu (A, ) můžeme (zejména,
je ­ li množina A konečná) znázorňovat graficky.
Postupujeme přitom následujícím způsobem:
1. Prvky množiny A znázorníme jako body
v rovině.
2. Je ­ li x < y pak bod x nakreslíme níže než
bod y.
Hasseovské diagramy ­ p.2/8

Grafické znázornění I
Uspořádanou množinu (A, ) můžeme (zejména,
je ­ li množina A konečná) znázorňovat graficky.
Postupujeme přitom následujícím způsobem:
1. Prvky množiny A znázorníme jako body
v rovině.
2. Je ­ li x < y pak bod x nakreslíme níže než
bod y.
3. Dva body x, y spojíme úsečkou právě tehdy, když
x < y a neexistuje žádný bod "mezi nimi", tzn.
neexistuje k  A tak, že x < k  k < y .
Hasseovské diagramy ­ p.2/8

Grafické znázornění II
Výsledný graf se pak nazývá hasseovský
diagram uspořádané množiny (A, ) .
Hasseovské diagramy ­ p.3/8

Grafické znázornění II
Výsledný graf se pak nazývá hasseovský
diagram uspořádané množiny (A, ) .
Jedná se o zjednodušený uzlový graf relace .
Hasseovské diagramy ­ p.3/8

Grafické znázornění II
Výsledný graf se pak nazývá hasseovský
diagram uspořádané množiny (A, ) .
Jedná se o zjednodušený uzlový graf relace .
Jsou vynechány šipky, které by měly být
u každého bodu.
Hasseovské diagramy ­ p.3/8

Grafické znázornění II
Výsledný graf se pak nazývá hasseovský
diagram uspořádané množiny (A, ) .
Jedná se o zjednodušený uzlový graf relace .
Jsou vynechány šipky, které by měly být
u každého bodu.
Je vynechána orientace šipek, která je
nahrazena umístěním bodu "níže" či "výše".
Hasseovské diagramy ­ p.3/8

Grafické znázornění II
Výsledný graf se pak nazývá hasseovský
diagram uspořádané množiny (A, ) .
Jedná se o zjednodušený uzlový graf relace .
Jsou vynechány šipky, které by měly být
u každého bodu.
Je vynechána orientace šipek, která je
nahrazena umístěním bodu "níže" či "výše".
Jsou vynechány "zbytečné" šipky, jejichž
existence plyne z tranzitivnosti relace  .
Hasseovské diagramy ­ p.3/8

Příklad konstrukce diagramu I
Příklad H 1. Uvažme uzlový graf uspořádané
množiny D24. Ten je znázorněn na obrázku a).
Obrázek a)
Hasseovské diagramy ­ p.4/8

Příklad konstrukce diagramu II
Příklad H 1. Protože relace uspořádání je
reflexivní, můžeme po vypuštění zelených
smyček obdržet graf na obrázku b).
Obrázek a)
Hasseovské diagramy ­ p.5/8

Příklad konstrukce diagramu II
Příklad H 1. Protože relace uspořádání je
reflexivní, můžeme po vypuštění zelených
smyček obdržet graf na obrázku b).
Obrázek b)
Hasseovské diagramy ­ p.5/8

Příklad konstrukce diagramu III
Příklad H 1. Obrázek b) je stále komplikovaný,
obsahuje nadbytečné červené šipky, tj. vzniklé
jako důsledek tranzitivity.
Obrázek b) Hasseovské diagramy ­ p.6/8

Příklad konstrukce diagramu III
Příklad H 1. Obrázek b) je stále komplikovaný,
obsahuje nadbytečné červené šipky, tj. vzniklé
jako důsledek tranzitivity. Po jejich smazání
máme obrázek c).
Obrázek c)Hasseovské diagramy ­ p.6/8

Příklady hasseovských diagramů I
Příklad H 2. Necht' A = {a, b, c} ; potom je 2A
=
{ , {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}.
Hasseovský diagram uspořádané množiny
(2A
, ) je znázorněn na obrázku a).
Č ást hasseovského diagramu uspořádané
množiny (N, | ) je znázorněna na obrázku b).
Č ást hasseovského diagramu uspořádané
množiny (N,  ) je znázorněna na obrázku c).
Hasseovské diagramy ­ p.7/8

Příklady hasseovských diagramů I
Příklad H 2. Necht' A = {a, b, c} ; potom je 2A
=
{ , {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}.
Hasseovský diagram uspořádané množiny
(2A
, ) je znázorněn na obrázku a).
Č ást hasseovského diagramu uspořádané
množiny (N, | ) je znázorněna na obrázku b).
Č ást hasseovského diagramu uspořádané
množiny (N,  ) je znázorněna na obrázku c).
Hasseovské diagramy ­ p.7/8

Příklady hasseovských diagramů II
Příklad H 2. Hasseovské diagramy
 
¤§¨
 
¤§¨
 

a) b) c)
Hasseovské diagramy ­ p.8/8