Il grafo dell'isomorfismo può essere descritto come un grafo in cui un singolo grafo può avere più di una forma. Ciò significa che due grafici diversi possono avere lo stesso numero di bordi, vertici e stessa connettività dei bordi. Questi tipi di grafici sono noti come grafici di isomorfismo. L'esempio di un grafico di isomorfismo è descritto come segue:
Il grafico sopra contiene le seguenti cose:
- Lo stesso grafico è rappresentato in più di una forma.
- Quindi, possiamo dire che questi grafici sono grafici di isomorfismo.
Condizioni per l'isomorfismo dei grafi
Due grafici qualsiasi saranno detti isomorfismo se soddisfano le seguenti quattro condizioni:
- Ci sarà un numero uguale di vertici nei grafici dati.
- Ci sarà un numero uguale di archi nei grafici dati.
- Ci sarà una uguale quantità di sequenza di gradi nei grafici forniti.
- Se il primo grafo sta formando un ciclo di lunghezza k con l'aiuto dei vertici {v1, v2, v3, …. vk}, allora anche un altro grafo deve formare lo stesso ciclo della stessa lunghezza k con l'aiuto dei vertici {v1, v2, v3, …. vk}.
Nota: la sequenza dei gradi di un grafico può essere descritta come una sequenza dei gradi di tutti i vertici in ordine crescente.
Punti importanti
- Affinché due grafici qualsiasi siano un isomorfismo, le condizioni necessarie sono le quattro condizioni sopra definite.
- Non è necessario che le condizioni sopra definite siano sufficienti per dimostrare che i grafici dati sono isomorfi.
- Se due grafici soddisfano le quattro condizioni sopra definite, anche in questo caso, non è necessario che i grafici siano sicuramente isomorfismi.
- Se il grafico non soddisfa alcuna condizione, allora possiamo dire che i grafici sicuramente non sono un isomorfismo.
Condizioni sufficienti per l'isomorfismo del grafico
Se vogliamo dimostrare che due grafici qualsiasi sono isomorfismi, ci sono alcune condizioni sufficienti che forniremo per garantire che i due grafici siano sicuramente isomorfismi. Quando i due grafici avranno eliminato con successo tutte e quattro le condizioni di cui sopra, solo allora controlleremo quei grafici in condizioni sufficienti, descritte come segue:
- Se i grafi complementari di entrambi i grafi sono isomorfismi, allora questi grafi saranno sicuramente un isomorfismo.
- Se le matrici adiacenti di entrambi i grafici sono le stesse, allora questi grafici saranno un isomorfismo.
- Se i grafici corrispondenti di due grafici vengono ottenuti eliminando alcuni vertici di un grafico e le loro immagini corrispondenti in altre immagini sono isomorfismi, solo allora questi grafici non saranno un isomorfismo.
Quando due grafici soddisfano una qualsiasi delle condizioni di cui sopra, allora possiamo dire che quei grafici sono sicuramente isomorfismi.
Esempi di isomorfismo del grafico
Esistono molti esempi di isomorfismo dei grafi, descritti come segue:
Esempio 1:
In questo esempio, abbiamo mostrato se i seguenti grafici sono isomorfismi.
Soluzione: Per questo, controlleremo tutte e quattro le condizioni di isomorfismo del grafo, che sono descritte come segue:
Condizione 1:
- Nel grafico 1, c'è un numero totale di 4 vertici, cioè G1 = 4.
- Nel grafico 2, c'è un numero totale di 4 vertici, cioè G2 = 4.
Qui,
C'è un numero uguale di vertici in entrambi i grafici G1 e G2. Quindi questi grafici soddisfano la condizione 1. Ora controlleremo la seconda condizione.
Condizione 2:
- Nel grafico 1, c'è un numero totale di 5 spigoli, ovvero G1 = 5.
- Nel grafico 2, c'è un numero totale di 6 spigoli, cioè G2 = 6.
Qui,
Non c'è un numero uguale di spigoli in entrambi i grafici G1 e G2. Quindi questi grafici non soddisfano la condizione 2. Ora non possiamo verificare tutte le restanti condizioni.
Poiché questi grafici violano la condizione 2. Quindi questi grafici non sono un isomorfismo.
∴ Il grafico G1 e il grafico G2 non sono grafici di isomorfismo.
Esempio 2:
In questo esempio, abbiamo mostrato se i seguenti grafici sono isomorfismi.
Soluzione: Per questo, controlleremo tutte e quattro le condizioni di isomorfismo del grafo, che sono descritte come segue:
cosa sono i selettori nei css
Condizione 1:
- Nel grafico 1, c'è un numero totale di 4 vertici, cioè G1 = 4.
- Nel grafico 2, c'è un numero totale di 4 vertici, cioè G2 = 4.
- Nel grafico 3, c'è un numero totale di 4 vertici, cioè G3 = 4.
Qui,
C'è un numero uguale di vertici in tutti i grafici G1, G2 e G3. Quindi questi grafici soddisfano la condizione 1. Ora controlleremo la seconda condizione.
Condizione 2:
- Nel grafico 1, c'è un numero totale di 5 spigoli, ovvero G1 = 5.
- Nel grafico 2, c'è un numero totale di 5 spigoli, cioè G2 = 5.
- Nel grafico 3, c'è un numero totale di 4 spigoli, cioè G2 = 4.
Qui,
- C'è un numero uguale di archi in entrambi i grafici G1 e G2. Quindi questi grafici soddisfano la condizione 2.
- Ma non c'è un numero uguale di spigoli nei grafici (G1, G2) e G3. Quindi i grafici (G1, G2) e G3 non soddisfano la condizione 2.
Poiché i grafici (G1, G2) e G3 violano la condizione 2. Quindi possiamo dire che questi grafici non sono un isomorfismo.
∴ Il grafico G3 non è né isomorfismo con il grafico G1 né con il grafico G2.
Poiché i grafici, G1 e G2 soddisfano la condizione 2. Quindi possiamo dire che questi grafici possono essere un isomorfismo.
∴ I grafici G1 e G2 possono essere un isomorfismo.
Verificheremo ora la terza condizione per i grafici G1 e G2.
Condizione 3:
- Nel grafico 1, il grado della successione s è {2, 2, 3, 3}, cioè G1 = {2, 2, 3, 3}.
- Nel grafico 2, il grado della successione s è {2, 2, 3, 3}, cioè G2 = {2, 2, 3, 3}.
Qui
In entrambi i grafici G1 e G2 è presente lo stesso numero di sequenze di gradi. Quindi questi grafici soddisfano la condizione 3. Ora controlleremo la quarta condizione.
Condizione 4:
Il grafico G1 forma un ciclo di lunghezza 3 con l'aiuto dei vertici {2, 3, 3}.
Anche il grafico G2 forma un ciclo di lunghezza 3 con l'aiuto dei vertici {2, 3, 3}.
Qui,
Mostra che entrambi i grafici contengono lo stesso ciclo perché entrambi i grafici G1 e G2 formano un ciclo di lunghezza 3 con l'aiuto dei vertici {2, 3, 3}. Quindi questi grafici soddisfano la condizione 4.
Così,
- I grafici G1 e G2 soddisfano tutte le quattro condizioni necessarie sopra.
- Quindi G1 e G2 potrebbero essere un isomorfismo.
Ora verificheremo condizioni sufficienti per dimostrare che i grafici G1 e G2 sono un isomorfismo.
Verifica delle condizioni sufficienti
Come abbiamo imparato, se i grafi complementari di entrambi i grafici sono isomorfismi, i due grafici saranno sicuramente un isomorfismo.
Disegneremo quindi i grafici complemento di G1 e G2, che sono descritti come segue:
Nei grafici del complemento di G1 e G2 sopra, possiamo vedere che entrambi i grafici sono isomorfismi.
∴ I grafici G1 e G2 sono isomorfismi.
Esempio 3:
In questo esempio, abbiamo mostrato se i seguenti grafici sono isomorfismi.
Soluzione: Per questo, controlleremo tutte e quattro le condizioni di isomorfismo del grafo, che sono descritte come segue:
Condizione 1:
- Nel grafico 1, ci sono 8 numeri totali di vertici, cioè G1 = 8.
- Nel grafico 2, ci sono 8 numeri totali di vertici, cioè G2 = 8.
Qui,
C'è un numero uguale di vertici in entrambi i grafici G1 e G2. Quindi questi grafici soddisfano la condizione 1. Ora controlleremo la seconda condizione.
Condizione 2:
- Nel grafico 1, il numero totale di spigoli è 10, ovvero G1 = 10.
- Nel grafico 2, il numero totale di spigoli è 10, ovvero G2 = 10.
Qui,
C'è un numero uguale di archi in entrambi i grafici G1 e G2. Quindi questi grafici soddisfano la condizione 2. Ora controlleremo la terza condizione.
Condizione 3:
- Nel grafico 1, il grado della sequenza s è {2, 2, 2, 2, 3, 3, 3, 3}, cioè G1 = {2, 2, 2, 2, 3, 3, 3, 3} .
- Nel grafico 2, il grado della sequenza s è {2, 2, 2, 2, 3, 3, 3, 3}, cioè G2 = {2, 2, 2, 2, 3, 3, 3, 3} .
Qui
In entrambi i grafici G1 e G2 è presente lo stesso numero di sequenze di gradi. Quindi questi grafici soddisfano la condizione 3. Ora controlleremo la quarta condizione.
Condizione 4:
- Il grafico G1 forma un ciclo di lunghezza 4 con l'aiuto dei vertici di grado 3.
- Il grafico G2 non forma un ciclo di lunghezza 4 con l'aiuto dei vertici perché i vertici non sono adiacenti.
Qui,
codici colore Java
Entrambi i grafici G1 e G2 non formano lo stesso ciclo con la stessa lunghezza. Quindi questi grafici violano la condizione 4.
Poiché i grafici G1 e G2 violano la condizione 4. Quindi, a causa della violazione della condizione 4, questi grafici non saranno un isomorfismo.
∴ I grafici G1 e G2 non sono un isomorfismo.