Relazioni su un Insieme:

• Totale: ogni elemento dell'insieme di partenza ha almeno una freccia uscente
• Univalente: ogni elemento dell'insieme di partenza ha al più una freccia d’uscita
• Surgettiva: ogni elemento dell'insieme di arrivo ha almeno una freccia entrante
• Iniettiva: ogni elemento dell'insieme di arrivo ha al più una freccia entrante
• Riflessiva: per ogni elemento c'è il cappio
• Anti-simmetrica: se esiste la coppia (a,b) non deve esistere la coppia (b,a)
• Transitività: se esistono le coppie (a,b) e (b,c) deve esistere la coppia (a,c)
• Simmetria: se esiste la coppia (a,b) deve esistere la coppia (b,a)
• Ordinamento: deve essere riflessiva, transitiva e anti simmetrica; inoltre deve esistere la coppia (a,b) oppure la coppia (b,a)
• Ordinamento Parziale: deve essere riflessiva, transitiva e anti simmetrica;
• Stella di Kleene: la relazione deve essere riflessiva e transitiva.

Grafi:

• Trail: non passare due volte per lo stesso arco
• Path: non passare due volte per lo stesso nodo
• Il cappio è un ciclo

Matrice d’adiacenza: