Isomorfismo di un Grafo

Per determinare sé due grafi sono isomorfi (sequenza uguale) si deve seguire il loro percorso.

• Se entrambi si possono ridisegnare nello stesso modo sono isomorfi.
• Ci devono essere gli stessi archi, non importa sé i nodi sono diversi.

Esempio, dati i seguenti 3 grafi, la coppia G1 è isomorfa con G3

Clique (cricca)

E’ un grafo dove ogni coppia di nodi è collegata da un arco.

• Ogni nodo è connesso con tutti gli altri
• Esiste sempre almeno 1 path hamiltoniano. Qualsiasi permutazione dei nodi, porta a un path
• Il numero di cicli hamiltoniani è dato da $n!$ Quello dei cicli non equivalenti è invece dato da $\frac{n!}{2n}$

Esempio: dato il seguente grafo (clique) G composto da 6 nodi, completare le affermazioni.

• 0,1,2,3,4,5 non è un trail euleriano
• 0,1,2,3,4,5 è un path hamiltoniano
• In una clique con 7 nodi esiste un circuito euleriano
• In una clique con 7 nodi esiste un ciclo hamiltoniano

Isomorfismo Relazione

Per determinare sé una relazione è un’isomorfismo tra due grafi :

• Comparare i due grafi e vedere sé essi hanno la stessa struttura (grado dei nodi)
• In caso affermativo, verificare ogni coppia della relazione (elemento sx sostituito da dx)