1. Escreva um algoritmo que verifique se dois grafos G1 e G2 não são isomorfos com base no número de vértices e arestas e, também, comparando a lista ordenada dos graus de seus vértices.

Passo 1

O enunciado pede um algoritmo para testar se dois grafos G1 e G2 não podem ser isomorfos usando invariantes simples: número de vértices, número de arestas e sequência de graus ordenada. O conteúdo é teoria de grafos – mais precisamente propriedades invariantes sob isomorfismo – e vamos precisar saber como contar vértices, arestas e como montar e ordenar a sequência de graus.

Passo 2

Primeiro comparamos o número de vértices. Se |V(G1)| ≠ |V(G2)|, concluímos imediatamente que não podem ser isomorfos, pois um isomorfismo preserva o tamanho dos conjuntos de vértices.
Em seguida comparamos o número de arestas. Se |E(G1)| ≠ |E(G2)|, também não são isomorfos, já que isomorfismo preserva arestas.

Passo 3

Depois calculamos, para cada grafo, o grau de cada vértice (isto é, quantas arestas incidem em cada vértice), montamos a lista de todos esses graus e ordenamos cada lista em ordem não‐decrescente.
Por fim, comparamos as duas listas ordenadas de graus. Se elas diferirem em qualquer posição, concluímos que G1 e G2 não podem ser isomorfos, pois o grau dos vértices é uma propriedade preservada em isomorfismos.

Passo 4

Se todas as comparações acima passarem (mesmos números de vértices e arestas e mesmas sequências de graus), o algoritmo não pode afirmar que não são isomorfos. Ele deve dizer que “não encontrou certificado de não‐isomorfismo” (isto é, eles podem ou não ser isomorfos, só um teste mais caro confirmaria).

Resposta

// Pseudocódigo do algoritmo
função NAO_ISOMORFOS(G1, G2):
// G1.V é o conjunto de vértices de G1, G1.E é o conjunto de arestas
// 1. Teste de número de vértices
se tamanho(G1.V) ≠ tamanho(G2.V) então
    retorne VERDADEIRO   // não são isomorfos
fim se

// 2. Teste de número de arestas
se tamanho(G1.E) ≠ tamanho(G2.E) então
    retorne VERDADEIRO   // não são isomorfos
fim se

// 3. Computar sequência de graus
criar lista graus1 vazia
para cada vértice v em G1.V faça
    graus1.adicionar(grau_de(G1, v))
fim para
ordenar(graus1)

criar lista graus2 vazia
para cada vértice v em G2.V faça
    graus2.adicionar(grau_de(G2, v))
fim para
ordenar(graus2)

// 4. Comparar sequências de graus
se graus1 ≠ graus2 então
    retorne VERDADEIRO   // não são isomorfos
fim se

// 5. Caso nenhum teste prove não‐isomorfismo
retorne FALSO  // não encontrou prova de que sejam não‐isomorfos
// Onde:
// grau_de(G, v) retorna o número de arestas incidentes em v no grafo G
// A função retorna VERDADEIRO se G1 e G2 não podem ser isomorfos, e FALSO caso contrário.

Exercícios relacionados