Cheatsheet

Relazione	Descrizione
Totale	Per ogni elemento in A, c'è una connessione con almeno un elemento in B
Univalente	Per ogni elemento in A, c'è al massimo una connessione (0 o 1) con un elemento in B
Surgettiva	Per ogni elemento in B, c'è una connessione con almeno un elemento in A
Iniettiva	Per ogni elemento in B, c'è al massimo una connessione (0 o 1) con un elemento in A
Biietiva	Tutte le precedenti
Riflessiva	Ogni elemento è in relazione con sé stesso (ha un cappio) (l'identità è contenuta nella relazione)
Transitiva	Se esiste una relazione (a,b), e (b,c), esiste anche una relazione (a,c) Include anche la relazione vuota
Antisimmetrica	Non c'è mai una relazione che va da a a b e contemporaneamente da b ad a (Non ci sono mai frecce opposte) È tollerato lo stesso elemento (cappio)
Simmetrica	Per ogni relazione (a,b), esiste una relazione (b,a) Per ogni elemento, ci sono 2 archi, uno da ed uno verso un altro elemento
Composizione	2 relazioni sono composte quando l'elemento di arrivo per la prima diventa l'elemento di partenza per la seconda Avendo (a,b) e (b,c) in R, R composto R (R;R) è ((a,b),c), ovvero (a,c)
R*, chiusura di Kleene	La composizione di una relazione con sé stessa infinite volte (zero incluso) È riflessiva e transitiva Contiene l'identità (R0)
R+, chiusura positiva	R* ma senza 0 incluso
Chiusura riflessiva	Data una relazione R ed un insieme A, è l'unione dell'identità di A con la relazione R
Chiusura simmetrica	Data una relazione R, è l'unione di R ed R opposto
Chiusura transitiva	Data una relazione R, si unisce a questa la chiusura positiva fino a far diventare la funzione transitiva
Ordinamento parziale	Una relazione Riflessiva, Transitiva ed Antisimmetrica
Ordinamento totale	Ordinamento parziale + ogni (a, b) appartenente al prodotto cartesiano; (a,b) o (b,a) appartiene ad R Ogni coppia di elementi appartiene alla relazione R: ogni elemento è in relazione con ogni altro elemento; C'è una freccia per ogni elemento su ogni elemento Se è totale, non è parziale

Grafo

Relazione	Descrizione
Walk/Cammino	Un collegamento da un nodo di partenza ad uno di arrivo
Trail	Un collegamento da un nodo di partenza ad uno di arrivo MA senza passare 2 volte per lo stesso arco (o collegamento)
Path	Un collegamento da un nodo di partenza ad uno di arrivo MA senza passare 2 volte per lo stesso NODO (o pallino/elemento) Non si deve passare 2 volte per lo stesso elemento
Walk chiuso	Un walk che permette di partire da un nodo e ritornare allo stesso ed ha lunghezza maggiore di 0
Circuito	È un walk chiuso che è anche un trail (non si passa per lo stesso arco 2 volte)
Ciclo	È un circuito che è anche un path (non si passa per lo stesso nodo 2 volte)
Aciclico	Quando il grafo NON presenta un ciclo
Connesso	Quando ogni nodo è "raggiunto" da almeno un arco (se è orientato: sia in uscita che in entrata)
Fortemente connesso	Da ogni nodo, esiste un walk verso ogni altro nodo
Componenti fortemente connesse	Sottografi fortemente connessi (notare che ogni nodo può arrivare a sé stesso, quindi ogni nodo preso singolarmente è una componente fortemente connessa)
Universale	Quando un nodo è vicino a tutti gli altri
DAG	Grafo Aciclico Orientato

Induzione (pecché non bastava prima)