Diagrama Hasse este un fel de diagrama. folosit pentru a reprezenta un set finit parțial comandat sub forma unei imagini a contracției sale tranzitorii. Mai precis, pentru un set parțial comandat (S. ≤), diagrama reprezintă fiecare element al lui S ca noduri în plan și segmente sau curbe care merg de la elementul x la elementul y. dacă x ≤ y și nu există niciun element z. pentru care x ≤ z ≤ y. Aceste curbe se pot intersecta, dar nu trebuie să treacă prin vârfuri, cu excepția cazului în care acestea sunt capetele liniei. O astfel de diagramă cu vârfuri etichetate determină în mod unic ordinea parțială.
Pentru prima dată în mod sistematic, acest tip de vizualizare a fost descris de Birkhoff în 1948 [1]. De asemenea, el a dat numele în onoarea lui Helmut Hasse folosind astfel de diagrame. dar aceste cifre se regăsesc în lucrări anterioare, de exemplu, în manual matematicianul francez Henri Vogt (acesta. Henri Vogt), ediția 1895. [2]
Deși diagrama Hasse este un mijloc simplu și intuitiv clar pentru lucrul cu un set finit parțial comandat. este foarte dificil să desenați un grafic "bun" care să fie convenabil pentru percepția vizuală pentru un set destul de non-trivial datorită numărului mare de posibile opțiuni de afișare. O tehnică simplă care implică pornirea cu elemente minime și desenarea elementelor suprapuse duce în mod sistematic deseori la rezultate slabe - simetria și structurile interne sunt ușor de pierdut.
De exemplu, setul Boolean de patru elemente, includerea operațiune ordonată ⊆ poate fi reprezentat de oricare dintre cele patru menționate mai jos diagrame (fiecare subgrup este prevăzut cu o etichetă codate binar, care arată elementul corespunzător conține un subset - 1 sau nu - 0):
Prima diagramă prezintă structura nivelurilor. A doua diagramă are aceeași structură de nivel, dar pe ea unele margini sunt alungite pentru a sublinia că cubul tridimensional este unirea a două cele tridimensionale. A treia diagrama arată o anumită simetrie internă. În a patra diagramă, vârfurile sunt aranjate ca o matrice de 4 × 4.
Diagrama Hasse a unei rețele de subgrupuri a grupului dihedral D i h 4 nu are marginile intersectate.
Unele proprietăți ale ordinelor parțiale relative la planaritatea diagramei Hasse (adică posibilitatea extragerii acesteia fără intersecția marginilor):
- Dacă ordinea parțială este o latură. atunci ea poate fi trasată fără intersecții dacă și numai dacă dimensiunea ordinii este de cel puțin două [3] [4].
- Dacă ordinea parțială are cel puțin un element minim sau maxim, atunci într-un timp liniar se poate verifica dacă există o diagramă fără intersecții [5].
- Determinați dacă o comandă parțială poate fi reprezentată de o diagramă plană Hasse, în cazul general, problema NP-completă [6].
- Dacă sunt date coordonatele y ale elementelor dintr-o ordine parțială, atunci diagrama lui Hasse care păstrează coordonatele date poate fi găsită într-un timp liniar, cu condiția să existe doar o astfel de diagramă [7]. În special, dacă o anumită ordine are niveluri, este posibil într-un timp liniar să se determine dacă există o diagramă Hasse fără intersecții, pentru care înălțimea fiecărui vârf este proporțională cu rangul său.
Articole similare
Trimiteți-le prietenilor: