Complemento di un grafo, sono tutti i grafi che non ci sono già.

Relazione complemento

C’è una relazione 1 a 1 tra il grafo e il complemento, perchè dal complemento posso tornare indietro, quindi c’è una biiezione.

Path emiltoniano:

Attraversa tutti i nodi del grafo

<aside> 💡 Cricca: grafo che ha tutti gli archi (completo) Dal nodo di partenza, posso raggiungere qualsiasi altro nodo.

</aside>

Esempio: Per trovare il numero di path in una cricca è il fattoriale numero di archi.

Permutazioni diverse possono rappresentare lo stesso ciclo, quindi sè faccio il fattoria per i cicli, conto più roba del necessario.

Divido quindi per 2n

• 2: perchè si può visitare in due sensi
• n: per eliminare le ripetizioni

Path in una cricca:

Mi posso spostare come voglio:

• scelgo due nodi