Het is een handig hulpmiddel, dat de bijbehorende deelbestelling volledig beschrijft. Daarom wordt het ook wel een besteldiagram genoemd. Het is heel gemakkelijk om een gerichte grafiek van een relatie op een verzameling A om te zetten in een equivalent Hasse-diagram. Daarom moeten bij het tekenen van een Hasse-diagram de volgende punten worden onthouden.
- De hoekpunten in het Hasse-diagram worden aangegeven met punten in plaats van met cirkels.
- Omdat een gedeeltelijke orde reflexief is, moet elk hoekpunt van A gerelateerd zijn aan zichzelf, dus worden de randen van een hoekpunt naar zichzelf verwijderd in het Hasse-diagram.
- Omdat een gedeeltelijke orde transitief is, hebben we dus telkens wanneer aRb, bRc, aRc. Elimineer alle randen die worden geïmpliceerd door de transitieve eigenschap in het Hasse-diagram, dat wil zeggen: verwijder de rand van a tot c maar behoud de andere twee randen.
- Als een hoekpunt 'a' is verbonden met hoekpunt 'b' door een rand, dat wil zeggen aRb, dan verschijnt het hoekpunt 'b' boven hoekpunt 'a'. Daarom kan de pijl in het Hasse-diagram aan de randen worden weggelaten.
Het Hasse-diagram is veel eenvoudiger dan de gerichte grafiek van de deelorde.
Java versus c++
Voorbeeld: Beschouw de verzameling A = {4, 5, 6, 7}. Zij R de relatie ≦ op A. Teken de gerichte graaf en het Hasse-diagram van R.
Oplossing: De relatie ≦ op de verzameling A wordt gegeven door
R = {{4, 5}, {4, 6}, {4, 7}, {5, 6}, {5, 7}, {6, 7}, {4, 4}, {5, 5} , {6, 6}, {7, 7}}
De gerichte grafiek van de relatie R is zoals weergegeven in figuur:
Om het Hasse-diagram van gedeeltelijke orde te tekenen, past u de volgende punten toe:
- Verwijder alle randen die worden geïmpliceerd door reflexieve eigenschap, d.w.z.
(4, 4), (5, 5), (6, 6), (7, 7) - Verwijder alle randen die worden geïmpliceerd door transitieve eigenschappen, d.w.z.
(4, 7), (5, 7), (4, 6) - Vervang de cirkels die de hoekpunten vertegenwoordigen door stippen.
- Laat de pijlen weg.
Het Hasse-diagram is zoals weergegeven in figuur:
Bovengrens: Beschouw B als een deelverzameling van een gedeeltelijk geordende verzameling A. Een element x ∈ A wordt een bovengrens van B genoemd als y ≦ x voor elke y ∈ B.
Ondergrens: Beschouw B als een deelverzameling van een gedeeltelijk geordende verzameling A. Een element z ∈ A wordt een ondergrens van B genoemd als z ≦ x voor elke x ∈ B.
Voorbeeld: Beschouw de poset A = {a, b, c, d, e, f, g} die moet worden besteld, weergegeven in Fig. Stel ook dat B = {c, d, e}. Bepaal de boven- en ondergrens van B.
Oplossing: De bovengrens van B is e, f en g omdat elk element van B '≦' e, f en g is.
De ondergrenzen van B zijn a en b omdat a en b '≦' alle elementen van B zijn.
Minste bovengrens (SUPREMUM):
Laat A een deelverzameling zijn van een gedeeltelijk geordende verzameling S. Een element M in S wordt een bovengrens van A genoemd als M elk element van A opvolgt, dat wil zeggen als we voor elke x in A x hebben<=m< p>
Als een bovengrens van A voorafgaat aan elke andere bovengrens van A, dan wordt deze het supremum van A genoemd en aangegeven met Sup (A)
int naar string-conversie in Java
Grootste ondergrens (INFIMUM):
Een element m in een poset S wordt een ondergrens van een deelverzameling A van S genoemd als m aan elk element van A voorafgaat, dat wil zeggen als we voor elke y in A m hebben<=y < p>
Als een ondergrens van A elke andere ondergrens van A opvolgt, wordt deze het infimum van A genoemd en wordt deze aangegeven met Inf (A)
Voorbeeld: Bepaal de kleinste bovengrens en de grootste ondergrens van B = {a, b, c} als ze bestaan, van de poset waarvan het Hasse-diagram wordt getoond in figuur:
Oplossing: De kleinste bovengrens is c.
De grootste ondergrens is k.