Os grafos G e H tais que V(G)=a, b, c, d, e, f, g, A(G)=a b, b c, c d, c f, f e, g f, g a, g b, V(H)=h, i, j, k, l, m, n e A(H)=h k, n j, j k, l k, l m, l i, i j, i n são isomorfos? E trocando-se h k por h n em A(G) ?

Passo 1

Beleza, vamos analisar o problema que você trouxe! Temos dois grafos, G e H, 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 H, 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 G tem 7 vértices: a, b, c, d, e, f, g, e 8 arestas: ab, bc, cd, cf, fe, gf, ga, gb. Já o grafo H também tem 7 vértices: h, i, j, k, l, m, n, e 8 arestas: hk, nj, jk, lk, lm, li, ij, in. 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 G:
  • a: 3 arestas ( ab, ga, gb)
  • b: 3 arestas ( ab, bc, gb)
  • c: 3 arestas ( bc, cd, cf)
  • d: 1 arepa ( cd)
  • e: 2 arepas ( fe, ef)
  • f: 3 arepas ( cf, fe, gf)
  • g: 3 arepas ( gf, ga, gb)
Para o grafo H:
  • h: 1 arepa ( hk)
  • i: 3 arepas ( li, ij, in)
  • j: 3 arepas ( nj, jk, ij)
  • k: 3 arepas ( hk, jk, lk)
  • l: 3 arepas ( lk, lm, li)
  • m: 1 arepa ( lm)
  • n: 2 arepas ( nj, in)
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 G e H que preserve os graus, o que é essencial para serem isomorfos.

Passo 4

Vamos tentar estabelecer uma correspondência entre os vértices de G e H baseada nos graus:
  • Vértices de grau 3 em G: a, b, c, f, g
  • Vértices de grau 3 em H: i, j, k, l
Percebemos que G tem 5 vértices de grau 3, enquanto H 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 G para H:
  • a (grau 3) poderia mapear para i, j, k ou l
  • b (grau 3) poderia mapear para outro desses
  • E assim por diante…
Mas já notamos que sobraria um vértice de grau 3 em G sem correspondente em H. 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 hk por hn em A(H)? Isso significa que a nova lista de arestas de H ficaria:
A(H') = hn, nj, jk, lk, lm, li, ij, in
Vamos verificar novamente os graus dos vértices em H':
  • h: 1 arepa ( hn)
  • i: 3 arepas ( li, ij, in)
  • j: 3 arepas ( nj, jk, ij)
  • k: 2 arepas ( jk, lk)
  • l: 3 arepas ( lk, lm, li)
  • m: 1 arepa ( lm)
  • n: 2 arepas ( nj, in, hn)
Agora, os graus não mudaram muito, mas ainda há uma discrepância no número de vértices de grau 3 entre G e H'. G tem 5 vértices de grau 3, enquanto H' tem 3. Portanto, mesmo após a alteração, os grafos não são isomorfos.

Resposta

Os grafos G e H não são isomorfos, e mesmo após trocar a aresta hk por hn em A(H), eles continuam não isomorfos.

Exercícios relacionados