Partizione: una partizione di un insieme A è una famiglia $\{A_1, ..., A_m\}$ t.c.

• $A_i \subseteq A$ (sottoinsiemi di A)
• $\forall i \neq j \ A_i \cap A_j = \empty$ (disgiunti)
• $\cup_{i=1...m}A_i=A$ (la loro unione forma A)

Ricordiamo che ogni partizione $P=\{A_1, ..., A_m\}$ identifica una relazione di quivalenza $R_P:$

$$ \forall x,y \in A, \ \ \ x \ R_P \ y \ \ se \ \ \exist i, x, y \in A_i. $$

Possiamo quindi scegliere un elemento rappresentativo $a_i \in A_i$ per cui $[a_i]=A_i$, e rappresentare $P$ come tupla

$$ P=(a_1, ..., a_m) $$

La partizione nella quale ogni elemento è rappresentante di se stesso si chiama partizione identità

dove:

• $P(A)$ è l'insieme di tutte le possibili partizioni di A
• Union toglie dalla partizione P i due sottoinsiemi [x] e [y] e ne aggiunge uno nuovo: la loro unione [x] U [y] → il numero di sottoinsiemi diminuisce di 1
• Find trova l'elemento rappresentante della classe di equivalenza a cui appartiene x

Studiamo possibili implementazioni per la struttura dati PA

• Liste concatenate
  • Vantaggi: semplicità
  • Svantaggi: costo medio di ciascuna operazione $O(|A|)$
• Foreste di alberi
  • Vantaggi: costo di ciascuna operazione $O(\log |A|)$ se si effettua il bilanciamento degli alberi
  • Svantaggi: nessuno

Union e Find