Gostaria de perguntar se já existe um resultado publicado sobre isso:
Pegamos todos os caminhos diferentes possíveis entre cada par de nós de dois gráficos regulares conectados (com grau , digamos, e número de nós n ) e anotamos seus comprimentos. Claro que esse número de caminhos distintos é exponencial. Minha pergunta é: se ordenarmos os comprimentos e compará-los (as listas obtidas pelos dois gráficos) e eles forem exatamente iguais, podemos dizer que os dois gráficos são isomórficos?
Obviamente, mesmo que seja um resultado, não podemos usá-lo para responder ao isomorfismo do gráfico, pois o número de caminhos distintos é exponencial, como dito
Por caminhos distintos , refiro-me a caminhos com pelo menos um nó diferente, obviamente.
Obrigado a priori por sua ajuda.
Respostas:
Acredito que a resposta para sua pergunta seja "não" porque uma condição equivalente implicaria uma solução de tempo polinomial para a IG.
Para , a matriz de adjacência do gráfico G , observe que o número de caminhos de i até j de comprimento k é ( A k ) i , j (com repetição de vértices e arestas permitidas). Para dois gráficos G 1 e G 2 (com matrizes de adjacência A 1 e A 2 ) e k ≥ 1 , se você classificou os elementos de A k 1 e A k 2 , em seguida, paraA G i j k (Ak)i,j G1 G2 A1 A2 k≥1 Ak1 Ak2 seja isomórfico a G 2 , é uma condição necessária que as listas sejam idênticas para todos os k .G1 G2 k
Eu acredito que sua conjectura é equivalente a:
Se as listas ordenadas de elementos de e A d 2 são idênticas para k = 1 a n - 1 (limite superior no caminho mais longo com vértices não repetidos), G 1 e G 2 são isomórficos.Ak1 Ad2 k=1 n−1 G1 G2
Admito duas possíveis falhas no meu argumento. Primeiro, é totalmente possível que o GI tenha um algoritmo de tempo polinomial e que acabamos de descobrir juntos, agora mesmo (viva, somos famosos!). Eu acho isso altamente improvável. Segundo (e muito mais provável), o que propus não é realmente equivalente à sua conjectura.
Pensamento final. Você já tentou isso para todos, digamos, gráficos 3-regulares para o tamanho 8 ou mais? Eu pensaria que, se sua conjectura é falsa, deve haver um contra-exemplo em gráficos tridimensionais de tamanho relativamente pequeno.
fonte
Como você está apenas comparando os comprimentos dos caminhos (e, enquanto isso, esquecendo a que par de nós eles correspondem se eu o entendi bem), acho que gráficos muito semelhantes devem fornecer um contra-exemplo: no final, você está apenas contando o número de caminhos de comprimento fixo e independentemente dos vértices que eles vinculam. Por exemplo, acho que esses gráficos são um contra-exemplo: http://www.mathe2.uni-bayreuth.de/markus/REGGRAPHS/GIF/06_3_3-2.gif e http://www.mathe2.uni-bayreuth.de/ markus / REGGRAPHS / GIF / 06_3_3-1.gif
Se não me engano (contar caminhos é tedioso), ambos têm 9 caminhos de comprimento 1, 18 caminhos de comprimento 2, 48 caminhos de comprimento 3, 30 caminhos de comprimento 4, 30 caminhos de comprimento 4 e 36 caminhos de comprimento 5
fonte
fonte