Verifica_Isomorfismo

Algoritmo que usa a biblioteca NetworkX para identificar se dois grafos são isomorfos. O código mostra a quantidade de vértices, arestas e a distribuição de graus dos dois grafos. Após isso ele testa se são ou não isomorfos.

fcojose

python

2 years ago

2.1 kB

Indexable

Never

import networkx as nx

# Definir os grafos A, B e C como objetos Graph
G_A = nx.Graph()
G_B = nx.Graph()

# Adicionar as arestas do Grafo G
G_A.add_edges_from([(0, 1), (0, 4), (0, 3), (1, 0), (1, 2), (2, 1), (2, 3), (2, 6), (3, 2), (3, 0), (4, 0), (4, 5), (4, 7), (5, 4), (5, 6), (6, 2), (6, 5), (6, 7),                     (7, 6), (7, 4)])

# Adicionar as arestas do Grafo H
G_B.add_edges_from([(0, 1), (0, 4), (0, 3), (1, 0), (1, 2), (1, 5), (2, 1), (2, 3), (3, 2), (3, 0), (4, 0), (4, 5), (4, 7), (5, 1), (5, 4), (5, 6), (6, 5), (6, 7), (7, 6), (7, 4)])

G1_G2_isomorphic = nx.is_isomorphic(G_A, G_B)


# Função para calcular a distribuição de graus
def degree_distribution(graph):
    degrees = dict(graph.degree())
    distribution = {}
    for degree in degrees.values():
        if degree in distribution:
            distribution[degree] += 1
        else:
            distribution[degree] = 1
    return distribution


# Informações detalhadas sobre cada grafo
print("Grafo A: {} vértices, {} arestas, distribuição de graus: {} \n".format(G_A.number_of_nodes(),
                                                                              G_A.number_of_edges(),
                                                                              degree_distribution(G_A)))
print("Grafo B: {} vértices, {} arestas, distribuição de graus: {} \n".format(G_B.number_of_nodes(),
                                                                              G_B.number_of_edges(),
                                                                              degree_distribution(G_B)))

if G1_G2_isomorphic:
    print("Grafo A, Grafo B e Grafo C são isomórficos entre si.\n")
else:
    if G1_G2_isomorphic:
        print("Grafo A e Grafo B são isomórficos.\n")
        gm = nx.isomorphism.GraphMatcher(G_A, G_B)
        if gm.is_isomorphic():
            print("Função de isomorfismo encontrada:")
            print(gm.mapping)
        print()
    else:
        print("Grafo A e Grafo B não são isomórficos.\n")