Det är ett användbart verktyg som fullständigt beskriver den tillhörande delordningen. Därför kallas det också ett beställningsdiagram. Det är mycket enkelt att konvertera en riktad graf av en relation på en mängd A till ett ekvivalent Hasse-diagram. Därför måste följande punkter komma ihåg när du ritar ett Hasse-diagram.
- Topparna i Hasse-diagrammet betecknas med punkter snarare än med cirklar.
- Eftersom en partiell ordning är reflexiv, måste därför varje hörn av A vara relaterad till sig själv, så kanterna från en vertex till sig själv tas bort i Hasse-diagrammet.
- Eftersom en partiell ordning är transitiv, har vi därför aRc närhelst aRb, bRc. Eliminera alla kanter som antyds av den transitiva egenskapen i Hasse-diagrammet, d.v.s. Ta bort kant från a till c men behåll de andra två kanterna.
- Om ett vertex 'a' är förbundet med vertex 'b' med en kant, d.v.s. aRb, så visas vertex 'b' ovanför vertex 'a'. Därför kan pilen utelämnas från kanterna i Hasse-diagrammet.
Hasse-diagrammet är mycket enklare än den riktade grafen för delordningen.
vad är en dubbel java
Exempel: Betrakta mängden A = {4, 5, 6, 7}. Låt R vara relationen ≦ på A. Rita den riktade grafen och Hasse-diagrammet för R.
Lösning: Relationen ≦ på mängden A ges av
R = {{4, 5}, {4, 6}, {4, 7}, {5, 6}, {5, 7}, {6, 7}, {4, 4}, {5, 5} , {6, 6}, {7, 7}}
Den riktade grafen för relationen R är som visas i fig.
För att rita Hasse-diagrammet i partiell ordning, tillämpa följande punkter:
- Ta bort alla kanter som antyds av reflexiv egenskap, dvs.
(4, 4), (5, 5), (6, 6), (7, 7) - Ta bort alla kanter som antyds av transitiv egenskap, dvs.
(4, 7), (5, 7), (4, 6) - Byt ut cirklarna som representerar hörnen med prickar.
- Utelämna pilarna.
Hasse-diagrammet är som visas i fig.
Övre gräns: Betrakta B som en delmängd av en delvis ordnad mängd A. Ett element x ∈ A kallas en övre gräns för B om y ≦ x för varje y ∈ B.
Nedre gräns: Betrakta B som en delmängd av en delvis ordnad mängd A. Ett element z ∈ A kallas en nedre gräns för B om z ≦ x för varje x ∈ B.
Exempel: Betrakta satsen A = {a, b, c, d, e, f, g} som visas i fig. Låt också B = {c, d, e}. Bestäm den övre och nedre gränsen för B.
Lösning: Den övre gränsen för B är e, f och g eftersom varje element i B är '≦' e, f och g.
De nedre gränserna för B är a och b eftersom a och b är '≦' alla element i B.
Minsta övre gräns (SUPREMUM):
Låt A vara en delmängd av en delvis ordnad mängd S. Ett element M i S kallas en övre gräns för A om M efterträder varje element i A, d.v.s. om vi för varje x i A har x<=m< p>
Om en övre gräns för A går före varannan övre gräns för A, kallas den för A:s högsta och betecknas med Sup (A)
sträng till datum
Största nedre gräns (INFIMUM):
Ett element m i en poset S kallas en nedre gräns för en delmängd A av S om m föregår varje element i A, d.v.s. om vi för varje y i A har m<=y < p>
Om en nedre gräns för A efterträder varannan nedre gräns för A, kallas den för A:s infimum och betecknas med Inf (A)
Exempel: Bestäm den minsta övre gränsen och den största nedre gränsen för B = {a, b, c} om de finns, för den poset vars Hasse-diagram visas i fig.
Lösning: Den minsta övre gränsen är c.
Den största nedre gränsen är k.