Os grafos
e
tais que
,
e
são isomorfos? E trocando-se
por
em
?
Passo 1
Beleza, vamos analisar o problema que você trouxe! Temos dois grafos,
e
, com conjuntos de vértices e arestas específicos. O que precisamos descobrir é se esses grafos são isomorfos, ou seja, se eles têm a mesma estrutura mesmo que os nomes dos vértices sejam diferentes. Além disso, vamos verificar se, ao fazer uma pequena alteração nas arestas de
, os grafos continuam isomorfos. Para resolver isso, vamos precisar entender o que é isomorfismo de grafos e como comparar as características dos grafos, como o número de vértices, arestas e o grau de cada vértice.
Passo 2
Primeiro, vamos conferir se os dois grafos têm o mesmo número de vértices e arestas. O grafo
tem 7 vértices:
, e 8 arestas:
. Já o grafo
também tem 7 vértices:
, e 8 arestas:
. Até aqui, ambos têm o mesmo número de vértices e arestas, o que é um bom começo para possivelmente serem isomorfos.
Passo 3
Agora, vamos analisar o grau de cada vértice em ambos os grafos. O grau de um vértice é o número de arestas que estão conectadas a ele.
Para o grafo
:
-
: 3 arestas ( , , ) -
: 3 arestas ( , , ) -
: 3 arestas ( , , ) -
: 1 arepa ( ) -
: 2 arepas ( , ) -
: 3 arepas ( , , ) -
: 3 arepas ( , , )
Para o grafo
:
-
: 1 arepa ( ) -
: 3 arepas ( , , ) -
: 3 arepas ( , , ) -
: 3 arepas ( , , ) -
: 3 arepas ( , , ) -
: 1 arepa ( ) -
: 2 arepas ( , )
Ambos os grafos têm vértices com graus similares: vários com grau 3, alguns com grau 2 e 1. Isso sugere que pode haver uma correspondência entre os vértices de
e
que preserve os graus, o que é essencial para serem isomorfos.
Passo 4
Vamos tentar estabelecer uma correspondência entre os vértices de
e
baseada nos graus:
- Vértices de grau 3 em
: , , , , - Vértices de grau 3 em
: , , ,
Percebemos que
tem 5 vértices de grau 3, enquanto
tem 4. Isso já é um sinal de que os grafos não são isomorfos, porque o número de vértices de cada grau precisa ser igual em ambos os grafos para existir uma correspondência perfeita.
Passo 5
Mesmo assim, vamos continuar um pouco mais para confirmar. Vamos tentar mapear os vértices de
para
:
-
(grau 3) poderia mapear para , , ou -
(grau 3) poderia mapear para outro desses - E assim por diante…
Mas já notamos que sobraria um vértice de grau 3 em
sem correspondente em
. Isso reforça a ideia de que não há uma correspondência isomórfica completa entre os grafos.
Passo 6
Agora, vamos verificar a segunda parte do problema: E se trocarmos a aresta
por
em
? Isso significa que a nova lista de arestas de
ficaria:
Vamos verificar novamente os graus dos vértices em
:
-
: 1 arepa ( ) -
: 3 arepas ( , , ) -
: 3 arepas ( , , ) -
: 2 arepas ( , ) -
: 3 arepas ( , , ) -
: 1 arepa ( ) -
: 2 arepas ( , , )
Agora, os graus não mudaram muito, mas ainda há uma discrepância no número de vértices de grau 3 entre
e
.
tem 5 vértices de grau 3, enquanto
tem 3. Portanto, mesmo após a alteração, os grafos não são isomorfos.
Resposta
Os grafos
e
não são isomorfos, e mesmo após trocar a aresta
por
em
, eles continuam não isomorfos.