Le relazioni descrivono legami tra oggetti: «x è minore di y», «l'utente u appartiene al gruppo g», «la pagina p contiene un collegamento alla pagina q». La matematica discreta le studia in modo astratto, e scopre che poche proprietà bastano a classificarle. Riconoscerle permette di capire subito che tipo di struttura si ha davanti e quali algoritmi si possono usare.
Definizione
Una relazione binaria R da un insieme A a un insieme B è un sottoinsieme del prodotto cartesiano A × B. Se la coppia (a, b) appartiene a R si scrive a R b e si dice che a è in relazione con b. Quando A = B si parla di relazione su A.
Esempio: su A = {1, 2, 3, 4}, la relazione «divide» contiene le coppie (a, b) in cui a divide b:
R = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)}
Tre modi di rappresentarla
- Elenco di coppie, come sopra.
- Matrice booleana: una tabella con righe e colonne indicizzate dagli elementi, con 1 dove la coppia è nella relazione.
- Grafo orientato: un nodo per elemento, una freccia da a verso b per ogni coppia (a, b).
La matrice della relazione «divide» su {1, 2, 3, 4}:
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 |
| 2 | 0 | 1 | 0 | 1 |
| 3 | 0 | 0 | 1 | 0 |
| 4 | 0 | 0 | 0 | 1 |
Le proprietà fondamentali
Riflessiva
R è riflessiva se ogni elemento è in relazione con sé stesso: a R a per ogni a. Nella matrice, la diagonale è tutta di 1; nel grafo, ogni nodo ha un cappio. «Divide» è riflessiva, perché ogni numero divide sé stesso. «Minore di» non lo è.
Simmetrica
R è simmetrica se a R b implica b R a. La matrice è uguale alla sua trasposta; nel grafo ogni freccia ha la sua freccia di ritorno. «Essere fratelli» è simmetrica (se si escludono i casi limite), «essere connessi in una rete senza direzione» pure. «Divide» non lo è: 2 divide 4 ma 4 non divide 2.
Antisimmetrica
R è antisimmetrica se a R b e b R a insieme implicano a = b. In altre parole, tra due elementi distinti c'è al più una delle due frecce. «Divide» sugli interi positivi è antisimmetrica, così come «≤».
Attenzione: antisimmetrica non vuol dire «non simmetrica». La relazione di uguaglianza è sia simmetrica sia antisimmetrica. Una relazione può anche non essere né l'una né l'altra.
Transitiva
R è transitiva se a R b e b R c implicano a R c. Nel grafo: ogni volta che c'è un percorso di due frecce, c'è anche la freccia diretta. «Divide» è transitiva, «≤» pure. «Essere amico di» in generale non lo è.
Riassunto su alcuni esempi
| Relazione | Rifl. | Simm. | Antisimm. | Trans. |
|---|---|---|---|---|
| = su ℤ | sì | sì | sì | sì |
| ≤ su ℤ | sì | no | sì | sì |
| < su ℤ | no | no | sì | sì |
| divide su ℤ⁺ | sì | no | sì | sì |
| stesso resto mod 5 | sì | sì | no | sì |
| differiscono di 1 | no | sì | no | no |
Verificare le proprietà con il codice
Con la relazione memorizzata come insieme di coppie, i controlli sono traduzioni dirette delle definizioni:
def riflessiva(R, A):
return all((a, a) in R for a in A)
def simmetrica(R):
return all((b, a) in R for (a, b) in R)
def transitiva(R):
return all((a, d) in R
for (a, b) in R for (c, d) in R if b == c)
Il controllo di transitività esamina tutte le coppie di coppie, quindi su relazioni grandi è costoso; per quelle si usano rappresentazioni a matrice e algoritmi dedicati.
Chiusure
Se una relazione non ha una proprietà, si può aggiungere il minimo numero di coppie necessario a fargliela avere. Il risultato si chiama chiusura.
- Chiusura riflessiva: si aggiungono tutte le coppie (a, a).
- Chiusura simmetrica: per ogni (a, b) si aggiunge (b, a).
- Chiusura transitiva: si aggiungono coppie finché ogni percorso ha la sua scorciatoia.
La chiusura transitiva ha un'interpretazione molto concreta: se R dice «il modulo a importa direttamente il modulo b», la sua chiusura transitiva dice «a dipende, direttamente o indirettamente, da b». Lo stesso vale per «il gruppo g è membro del gruppo h» nei sistemi di gestione dei permessi: calcolare chi eredita cosa significa calcolare una chiusura transitiva. In un'analisi dei permessi è proprio lì che spesso si scoprono accessi che nessuno aveva assegnato esplicitamente. L'algoritmo di Warshall la calcola su una matrice n × n con tre cicli annidati, in tempo proporzionale a n³.
In sintesi
- Una relazione binaria è un insieme di coppie ordinate, rappresentabile come matrice o grafo orientato.
- Riflessiva: diagonale piena; simmetrica: matrice uguale alla trasposta.
- Antisimmetrica non significa non simmetrica: l'uguaglianza è entrambe le cose.
- Transitiva: ogni percorso di due passi ha la sua scorciatoia diretta.
- La chiusura transitiva risponde a domande su dipendenze e permessi ereditati.
