Diagramma di Hasse

Da Wikipedia, l'enciclopedia libera.

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

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[modifica | modifica sorgente]

  • 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:
Lattice of the divisibility of 60.svg
  • 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:
Lattice of partitions of an order 4 set.svg

Perché si usano i diagrammi di Hasse[modifica | modifica sorgente]

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 uv.

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:

  • aa (riflessività)
  • se ab e bc allora ac (transitività)
  • se ab e ba 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 uu. 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:

Lattice of partitions of an order 4 set redundant.svg

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[modifica | modifica sorgente]

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[modifica | modifica sorgente]

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}[modifica | modifica sorgente]

Hypercubeorder binary.svg     Hypercubecubes binary.svg     Hypercubestar binary.svg

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 etichettate 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 2S 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.

Altri progetti[modifica | modifica sorgente]

Collegamenti esterni[modifica | modifica sorgente]

matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica