Diagramma di Hasse

Nella teoria degli ordini, un diagramma di Hasse è un modo per rappresentare graficamente un insieme finito parzialmente ordinato. Prende nome da Helmut Hasse (1898–1979).

In sostanza, dato un insieme S come sopra, si rappresenta ogni membro di S come vertice e si traccia una linea che va da x a y se x < y e non esiste z tale che x < z < y. In questo caso si dice che y copre x o che y è un successore immediato di x. Inoltre è richiesto che i vertici siano posizionati in modo che ogni segmento incontri esattamente due vertici: i due estremi. Ogni diagramma di questo tipo (poiché i vertici sono etichettati) determina unicamente un ordinamento parziale ma esistono più diagrammi corrispondenti ad un dato ordine.

Esempi

• L'insieme A = { 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60 } di tutti i divisori di 60 è parzialmente ordinato in base alla divisibilità ed ha il seguente diagramma di Hasse:

• L'insieme di tutte e quindici le partizioni dell'insieme { 1, 2, 3, 4 } parzialmente ordinato secondo i "raffinamenti" (una partizione con meno elementi è minore di una partizione con più elementi), ha il seguente diagramma di Hasse:

Perché si usano i diagrammi di Hasse

Se si prova a creare una rappresentazione visuale di un insieme parzialmente ordinato (S, ≤) si può procedere in vari modi. Si potrebbe cominciare creando un grafo dove ogni nodo del grafo è un elemento in S e ogni arco (u, v) nel grafo rappresenta la relazione u ≤ v.

Procedendo in questo modo quando si prova a disegnare il grafo si noterà che la rappresentazione risultante è molto "affollata", in effetti questa rappresentazione si porta dietro molte ridondanze. Si richiamano le proprietà di un ordinamento parziale:

• a ≤ a (riflessività)
• se a ≤ b e b ≤ c allora a ≤ c (transitività)
• se a ≤ b e b ≤ a allora a = b (antisimmetricità)

Nel grafo originale si ha una quantità di archi - cicli su ogni nodo del grafo - nella forma (u, u) poiché la proprietà riflessiva significa che u ≤ u. Questo è vero per ogni elemento in S altrimenti non sarebbe un ordinamento parziale.

Si può provare a creare il grafo come sopra ma eliminando i cicli dell'insieme parzialmente ordinato ({1,2,3,4}, ≤) dove un partizione più piccola è minore di una partizione più grande. Si otterrà quindi il seguente grafo:

Anche questo grafo contiene informazioni ridondanti. Riferendosi ancora alla proprietà transitiva dell'ordinamento parziale, nel grafo precedente sono presenti gli archi (a,c), (a,b) e (b,c). Non occorre avere anche l'arco (a,c) perché gli altri due archi implicano che il terzo esista.

A questo punto è sufficiente avere un arco tra un elemento dell'insieme ed il suo immediato predecessore. Non occorre avere archi verso gli altri predecessori per via della proprietà transitiva né gli anelli per via della proprietà riflessiva.

Utilizzando quanto esposto sopra si otterrebbe la prima immagine dell'esempio e quindi diventa utile definire il diagramma di Hasse in modo da escludere automaticamente i casi elencati precedentemente.

Relazione di copertura

Simbolicamente tutti gli archi di un diagramma di Hasse dovrebbero essere nella forma (x, y) dove x < y (questa relazione più stretta serve ad escludere gli anelli) e che non esista un elemento z nell'insieme tale che x < z < y (in questo modo si escludono gli archi supplementari dovuti alla transitività).

Questa relazione è conosciuta come relazione di copertura ed il diagramma di Hasse è spesso definito in base a questa relazione. Un elemento y si dice che copre x se y è l'immediato successore di x. L'ordinamento parziale (stretto) è quindi la chiusura transitiva di questa relazione di copertura

Il diagramma di Hasse di S può essere definito in modo astratto come l'insieme delle coppie ordinate (x, y) tali che y copre x quindi il diagramma di Hasse è l'inverso della relazione di copertura.

Trovare un "buon" diagramma di Hasse

Anche se i diagrammi di Hasse sono semplici e costituiscono un buono strumento per rappresentare insiemi parzialmente ordinati finiti, è abbastanza complesso disegnare un "buon" diagramma di Hasse. Questo accade perché in generale esistono molti (infiniti) modi per disegnare un diagramma di Hasse di un dato insieme parzialmente ordinato. Una semplice tecnica consiste nel cominciare con gli elementi minimi di un ordine e poi aggiungere gli elementi più grandi, spesso però produce scarsi risultati: si perdono facilmente le strutture interne dell'ordine.

Il seguente esempio dimostra il problema. Si consideri l'insieme delle parti di S = {a, b, c, d}, per esempio l'insieme di tutti i sottoinsiemi di S scritto come ${\mathcal {P}}(S)$. Questo insieme delle parti può essere facilmente ordinato mediante l'inclusione del sottoinsieme $\subseteq$. Di seguito sono rappresentati tre modi per disegnare un diagramma di Hasse per questo ordine: S = {a,b,c,d}

Sono state omesse le etichette di questi diagrammi per risparmiare spazio ma dovrebbe essere semplice assegnare un sottoinsieme di S ai vari vertici. Il diagramma più a sinistra è probabilmente il più vicino al modo nativo di costruire i diagrammi: i cinque livelli del grafo rappresentano il numero di elementi che contiene il sottoinsieme di ogni livello. Occorre notare che esistono molti modi differenti di assegnare insiemi di un elemento al secondo livello ma questo assegnamento determina l'etichettatura di tutti gli altri elementi. Il fatto che è possibile etichettare i diagrammi in modi diversi, dipende dal fatto che l'insieme parzialmente ordinato di questo esempio è un automorfismo — in molti modi differenti.

L'esempio precedente diversi diagrammi dello stesso ordine e come ogni rappresentazione può riflettere differenti aspetti della sottostante struttura matematica. Il primo diagramma evidenzia il numero di elementi di un livello di ogni vertice. Il terzo diagramma enfatizza la simmetria interna della struttura. L'esempio centrale è formato da due cubi (il cubo è il diagramma di un insieme triplo {a,b,c}); evidenziando quindi la relazione tra l'insieme delle parti 2^S e l'ordine indotto dal prodotto di reticoli 2 × 2^{{a, b, c}}.

Sono stati proposti vari algoritmi per disegnare meglio questi diagrammi ma un buon diagramma richiede comunque assistenza umana. Anche un essere umano ha bisogno di pratica per disegnare diagrammi esplicativi.

Bibliografia

• K. A. Baker, P. Fishburn e F. S. Roberts, Partial orders of dimension 2, in Networks, vol. 2, n. 1, 1971, pp. 11–28, DOI:10.1002/net.3230020103.
• R Bertolazzi, G. Di Battista, C. Mannino e R. Tamassia, Optimal upward planarity testing of single-source digraphs, in Proc. 1st European Symposium on Algorithms (ESA '93), Lecture Notes in Computer Science, vol. 726, Springer-Verlag, 1993, pp. 37–48, DOI:10.1007/3-540-57273-2_42.
• Garrett Birkhoff, Lattice Theory, Revised, American Mathematical Society, 1948.
• Hubert Chan, A parameterized algorithm for upward planarity testing, in Proc. 12th European Symposium on Algorithms (ESA '04), Lecture Notes in Computer Science, vol. 3221, Springer-Verlag, 2004, pp. 157–168.
• G. Di Battista e R. Tamassia, Algorithms for plane representation of acyclic digraphs, in Theoretical Computer Science, vol. 61, 2–3, 1988, pp. 175–178, DOI:10.1016/0304-3975(88)90123-5.
• Ralph Freese, Automated lattice drawing, in Concept Lattices, Lecture Notes in Computer Science, vol. 2961, Springer-Verlag, 2004, pp. 589–590. An extended preprint is available online: [1].
• Ashim Garg e Roberto Tamassia, Upward planarity testing, in Order, vol. 12, n. 2, 1995a, pp. 109–133, DOI:10.1007/BF01108622.
• Ashim Garg e Roberto Tamassia, On the computational complexity of upward and rectilinear planarity testing, in Graph Drawing (Proc. GD '94), LectureNotes in Computer Science, vol. 894, Springer-Verlag, 1995b, pp. 286–297, DOI:10.1007/3-540-58950-3_384.
• Michael Jünger e Sebastian Leipert, Level planar embedding in linear time, in Graph Drawing (Proc. GD '99), Lecture Notes in Computer Science, vol. 1731, 1999, pp. 72–81, DOI:10.1007/3-540-46648-7_7, ISBN 978-3-540-66904-3.
• Henri Gustav Vogt, Leçons sur la résolution algébrique des équations, Nony, 1895, p. 91.

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file sul diagramma di Hasse

Collegamenti esterni

• Hasse, diagramma di, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
• (EN) Eric W. Weisstein, Diagramma di Hasse, su MathWorld, Wolfram Research.
• (EN) Implementazione dei fondamenti dei diagrammi di Hasse, su causaergosum.net. URL consultato il 23 agosto 2005 (archiviato dall'url originale il 7 aprile 2005).