To je koristan alat koji u potpunosti opisuje pridruženi djelomični poredak. Stoga se naziva i dijagram narudžbe. Vrlo je jednostavno pretvoriti usmjereni graf relacije na skupu A u ekvivalentni Hasseov dijagram. Stoga se pri crtanju Hasseovog dijagrama moraju zapamtiti sljedeće točke.
- Vrhovi u Hasseovom dijagramu označeni su točkama, a ne krugovima.
- Budući da je djelomični poredak refleksivan, stoga svaki vrh od A mora biti povezan sa samim sobom, tako da se rubovi od vrha do samog sebe brišu u Hasseovom dijagramu.
- Budući da je djelomični poredak tranzitivan, stoga kad god aRb, bRc, imamo aRc. Uklonite sve rubove koji su implicirani tranzitivnim svojstvom u Hasseovom dijagramu, tj. Izbrišite rub od a do c, ali zadržite druga dva ruba.
- Ako je vrh 'a' povezan s vrhom 'b' bridom, tj. aRb, tada se vrh 'b' pojavljuje iznad vrha 'a'. Stoga se strelica može izostaviti s rubova u Hasseovom dijagramu.
Hasseov dijagram mnogo je jednostavniji od usmjerenog grafa parcijalnog reda.
Primjer: Promotrimo skup A = {4, 5, 6, 7}. Neka je R relacija ≦ na A. Nacrtajte usmjereni graf i Hasseov dijagram od R.
Riješenje: Relacija ≦ na skupu A dana je izrazom
R = {{4, 5}, {4, 6}, {4, 7}, {5, 6}, {5, 7}, {6, 7}, {4, 4}, {5, 5} , {6, 6}, {7, 7}}
java arraylist
Usmjereni graf relacije R je prikazan na slici:
Za crtanje Hasseovog dijagrama djelomičnog reda primijenite sljedeće točke:
- Izbrišite sve rubove implicirane refleksivnim svojstvom, tj.
(4, 4), (5, 5), (6, 6), (7, 7) - Izbrišite sve rubove implicirane tranzitivnim svojstvom, tj.
(4, 7), (5, 7), (4, 6) - Zamijenite krugove koji predstavljaju vrhove točkama.
- Izostavite strelice.
Hasseov dijagram je prikazan na slici:
Gornja granica: Zamislite da je B podskup djelomično uređenog skupa A. Element x ∈ A naziva se gornja granica od B ako je y ≦ x za svaki y ∈ B.
Donja granica: Zamislimo da je B podskup djelomično uređenog skupa A. Element z ∈ A naziva se donja granica B ako je z ≦ x za svaki x ∈ B.
Primjer: Razmotrimo poredak A = {a, b, c, d, e, f, g} poredanim prikazanim na sl. Također neka je B = {c, d, e}. Odredite gornju i donju granicu B.
fusnote markdown
Riješenje: Gornja granica B je e, f i g jer je svaki element B '≦' e, f i g.
Donje granice B su a i b jer su a i b '≦' svaki element B.
Najmanja gornja granica (SUPREMUM):
Neka je A podskup djelomično uređenog skupa S. Element M u S naziva se gornjom granicom od A ako M slijedi svaki element od A, tj. ako, za svaki x u A, imamo x<=m< p>
Ako gornja granica od A prethodi svakoj drugoj gornjoj granici od A, tada se naziva supremum od A i označava se sa Sup (A)
preimenuj u linux direktoriju
Najveća donja granica (INFIMUM):
Element m u posebnom skupu S naziva se donja granica podskupa A od S ako m prethodi svakom elementu od A, tj. ako, za svaki y u A, imamo m<=y < p>
Ako donja granica A slijedi svaku drugu donju granicu A, tada se naziva infimumom A i označava se s Inf (A)
Primjer: Odredite najmanju gornju granicu i najveću donju granicu B = {a, b, c} ako postoje, uporedno postavljenog skupa čiji je Hasseov dijagram prikazan na slici:
Riješenje: Najmanja gornja granica je c.
Najveća donja granica je k.