Je uporabno orodje, ki v celoti opiše pripadajoči delni red. Zato se imenuje tudi diagram urejanja. Zelo enostavno je pretvoriti usmerjen graf relacije na množici A v enakovredni Hassejev diagram. Zato si je treba pri risanju Hassejevega diagrama zapomniti naslednje točke.
- Oglišča v Hassejevem diagramu so označena s točkami in ne s krogi.
- Ker je delni vrstni red refleksiven, mora biti vsako oglišče A povezano samo s seboj, zato so robovi od oglišča do samega sebe izbrisani v Hassejevem diagramu.
- Ker je delni red tranzitiven, imamo torej vedno, ko aRb, bRc, aRc. Odstranite vse robove, ki jih implicira tranzitivna lastnost v Hassejevem diagramu, tj. Izbrišite rob od a do c, vendar obdržite druga dva robova.
- Če je oglišče 'a' povezano z ogliščem 'b' z robom, tj. aRb, potem se oglišče 'b' pojavi nad ogliščem 'a'. Zato lahko puščico na robovih v Hassejevem diagramu izpustimo.
Hassejev diagram je veliko enostavnejši od usmerjenega grafa delnega reda.
primer: Razmislite o množici A = {4, 5, 6, 7}. Naj bo R relacija ≦ na A. Nariši usmerjen graf in Hassejev diagram za R.
rešitev: Relacija ≦ na množici A je podana z
R = {{4, 5}, {4, 6}, {4, 7}, {5, 6}, {5, 7}, {6, 7}, {4, 4}, {5, 5} , {6, 6}, {7, 7}}
Usmerjeni graf relacije R je prikazan na sliki:
primerek java
Za risanje Hassejevega diagrama delnega reda uporabite naslednje točke:
- Izbrišite vse robove, ki jih implicira refleksivna lastnost, tj.
(4, 4), (5, 5), (6, 6), (7, 7) - Izbrišite vse robove, ki jih implicira tranzitivna lastnost, tj.
(4, 7), (5, 7), (4, 6) - Zamenjajte kroge, ki predstavljajo oglišča, s pikami.
- Izpustite puščice.
Hassejev diagram je prikazan na sliki:
Zgornja meja: Naj bo B podmnožica delno urejene množice A. Element x ∈ A imenujemo zgornja meja B, če je y ≦ x za vsak y ∈ B.
Spodnja meja: Naj bo B podmnožica delno urejene množice A. Element z ∈ A imenujemo spodnja meja B, če je z ≦ x za vsak x ∈ B.
primer: Upoštevajte, da je poset A = {a, b, c, d, e, f, g} urejen, kot je prikazano na sl. Naj bo tudi B = {c, d, e}. Določite zgornjo in spodnjo mejo B.
rešitev: Zgornja meja B je e, f in g, ker je vsak element B '≦' e, f in g.
c polje nizov
Spodnji meji B sta a in b, ker sta a in b '≦' vsak element B.
Najmanjša zgornja meja (SUPREMUM):
Naj bo A podmnožica delno urejene množice S. Element M v S imenujemo zgornja meja A, če M nasledi vsak element iz A, tj. če imamo za vsak x v A x<=m< p>
Če je zgornja meja A pred vsako drugo zgornjo mejo A, se imenuje supremum A in je označena s Sup (A)
java pretvori niz v int
Največja spodnja meja (INFIMUM):
Element m v stranski množici S imenujemo spodnja meja podmnožice A od S, če je m pred vsakim elementom od A, tj. če imamo za vsak y v A m<=y < p>
Če spodnja meja A nasledi vsako drugo spodnjo mejo A, potem se imenuje infimum A in je označena z Inf (A)
primer: Določite najmanjšo zgornjo in največjo spodnjo mejo za B = {a, b, c}, če obstajata, poravnave, katere Hassejev diagram je prikazan na sliki:
rešitev: Najmanjša zgornja meja je c.
Največja spodnja meja je k.