Se dois gráficos são isomórficos, seus determinantes serão iguais?

Question

Gráficos de 10 vértices G1 e G2

Estou resolvendo os exercícios do capítulo 2 da Teoria dos Grafos com Algoritmos e suas Aplicações. Até agora, para isomorfismo, eu apenas escrevo todas as arestas e tento encontrar os padrões, o que para pequenos gráficos é o suficiente. Para esses 2 gráficos de 10 vértices e 30 arestas, acho que preciso de algo mais escalável. Eu tentei 'traduzir' ambos os gráficos para uma estrutura unificada, mas é claro que se um vertx mudar o nome, o gráfico também ficará diferente. Escrevi a matriz de adjacência tentando encontrar um padrão, e há uma coluna que me faz desconfiar que esses dois podem não ser isomórficos. No entanto, sempre posso alterar o nome de um vértice para fazer as colunas parecerem um pouco mais semelhantes. De qualquer forma, descobri que dois gráficos (A, B) são isomórficos se A = PBP (t) onde P é uma matriz de permutação e P (t) é sua transposta.

Uma vez que det (P) = 1 ou -1 = det (P (t)) e det (AB) = det (A) * det (B), então se A e B são isomórficos:

det (A) = 1 | -1 * det (B) * 1 | -1 det (A) = det (B)

duas matrizes de adjacência poderiam ter o mesmo determinante e não ser isomórficas? ou é a igualdade no determinante uma condição suficiente (e muito mais escalável) para o isomorfismo?

melhor,

Sergio

Answer 1

É verdade que a matriz de adjacência de grafos isomórficos terá o mesmo determinante. Na verdade, se$A = PBP^T$ para uma matriz de permutação $P$, então $$ \det(A) = \det(P) \det(B) \det(P^T) = \det(P)^2 \det(B) = \det(B). $$ Na verdade, podemos dizer mais: porque $A$ e $B$são matrizes semelhantes, eles terão os mesmos autovalores. Observe que, se duas matrizes tiverem os mesmos autovalores, elas terão automaticamente o mesmo determinante.

O inverso não é válido: se $A,B$ são as matrizes de adjacência de dois grafos e temos $\det(A) = \det(B)$, não significa necessariamente que os gráficos são isomórficos. Na verdade, mesmo que$A$ e $B$têm os mesmos autovalores, não significa necessariamente que os gráficos sejam isomórficos. Exemplos desse fenômeno são chamados de pares de gráficos isoespectrais (ou cospectrais) .

Answer 2

No.Path de comprimento 2 (2 arestas, 3 vértices) tem det 0, e o gráfico com 3 vértices e sem arestas também tem det 0.