Diskuse s wikipedistou:Pavel Jelínek/Moje pískoviště

Více informací o této stránce

12 je **největší prvek** svazu. 2 i 3 jsou **minimální prvky** (tj. nic jim nepředchází), ale svaz nemá **nejmenší prvek**, který by předcházel všem ostatním.
		12
		↑
		6
	↗		↖
2				3

5 je největší dolní závora, tj. **supremum**, prvků 10 a 15. *Nejmenší* horní závora prvků 10 a 15 (**infimum**) neexistuje, i když existují dvě *minimální* horní závory, 60 i 90. Svaz proto není úplný. Navíc prvky 15 a 7 nemají žádnou horní závoru. Jejich jediná (a tedy největší) dolní závora je 1.
60				90
↑	↗		↖	↑
10				15	14
	↖		↗		↑
		5			7
		↑		↗
		1

Pojem „orientovaný graf $(V,E)$ s množinou uzlů $V$ a množinou hran $E$ “ přesně splývá s pojmem „binární relace $E$ na množině $V$ “, a to jak formálním zápisem jako uspořádaná dvojice, tak i v tom, jakých podob mohou tyto struktury nabývat. Orientovaný graf je, stejně jako částečné uspořádání, příkladem abstraktní struktury, takže za množinu vrcholů (tj. „nosnou množinu struktury“) lze zvolit libovolné matematické objekty.

Označíme-li proto pojmem „tranzitivní graf“ takový orientovaný graf, který s každou hranou $(u,v)$ (tj. šipkou z vrcholu $u$ do vrcholu $v$ ) a hranou $(v,w)$ obsahuje i „tranzitivní hranu“ $(u,w)$ , pak „ostré částečné uspořádání“ je přesně totéž, co „tranzitivní acyklický orientovaný graf“. I s pojmem „tranzitivní ireflexivní orientovaný graf“, protože existuje-li cyklus jakékoli délky z $u$ do $u$ , díky tranzitivitě graf obsahuje i $(u,u)$ , takže není ireflexivní.

Každou ostře částečně uspořádanou množinu lze zobrazit jako graf, v němž do každého vrcholu vedou šipky z vrcholů, které mu ostře předchází. Hrany, které z ostatních vyplývají díky tranzitivitě, se pro přehlednost často neznázorňují, např. šipka 1→4, 2→12 a 1→12 na diagramu vpravo.

Naopak každému orientovanému grafu (tj. množině vrcholů a šipek), který neobsahuje cyklus, lze doplnit „tranzitivní“ hrany, a tak získat ostré částečné uspořádání; neostré dále doplněním „reflexivních“ hran.

Z toho plyne, že jakákoli acyklická množina vrcholů a šipek popisuje částečné uspořádání. To ilustruje, jak mnoha podob mohou nabývat částečná uspořádání na konečných i nekonečných množinách.

Zahajte diskusi ke stránce Wikipedista:Pavel Jelínek/Moje pískoviště

Diskusní stránky jsou místa, kde lidé diskutují o tom, jak vytvořit co nejlepší Wikipedii. Tuto diskusní stránku můžete použít k zahájení diskuse s ostatními o tom, jak zlepšit stránku Wikipedista:Pavel Jelínek/Moje pískoviště.

Zahájit diskusi

Přidat téma