Localizando vértices duplos em gráficos

22

Seja um gráfico. Para um vértice x V , definir N ( x ) para ser o (aberto) vizinhança de x em L . Ou seja, N ( x ) = { y VG=(V,E)xVN(x)xG . Defina dois vértices u , v em G comogêmeosse u e v tiverem o mesmo conjunto de vizinhos, ou seja, se N ( u ) = N ( v ) .N(x)={yV|{x,y}E}u,vGuvN(u)=N(v)

Dado um gráfico em n vértices e m arestas como entrada, com que rapidez podemos encontrar um par de gêmeos em G , se esse par existir?GnmG

Podemos verificar se dois vértices dados são gêmeos em tempo, comparando suas vizinhanças. Um algoritmo simples é encontrar gêmeos, portanto, é verificar, para cada par de vértices, se são gêmeos. Isso leva tempo O ( n 3 ) (e também encontra todos os pares de gêmeos). Existe uma maneira significativamente mais rápida de encontrar (se houver) um par de gêmeos no gráfico? Existe trabalho conhecido na literatura que resolva esse problema?O(n)O(n3)

gphilip
fonte
Você pode percorrer bairros e adicioná-los a uma hashtable. Relacionados: cstheory.stackexchange.com/q/3390/236
Radu Grigore
1
Este é o exercício 2.17 aqui books.google.co.uk/…
Radu GRIGore
Alguém com poderes de edição deve corrigir a definição de gêmeos. (Veja os comentários sobre a resposta de TheMachineCharmer, ou a definição no livro I ligada.)
Radu Grigore

Respostas:

21

Gêmeos em um gráfico são apenas módulos de tamanho 2. A decomposição modular de um gráfico pode ser encontrada em . A árvore de decomposição modular representa implicitamente todos os módulos do gráfico e consiste em três tipos de nós internos: série, nós paralelos e primos, e as folhas consistem em nós individuais. Um conjunto de pelo menos dois vértices S V é um módulo se, e somente se, for algum nó na árvore ou a união de algum conjunto de filhos de uma série ou nó paralelo.O(n+m)SV

Então, para encontrar um par de nós gêmeos, se eles existirem, podemos construir a árvore de decomposição modular em . Então observe as folhas, se o pai de qualquer folha for um nó em série ou paralelo, esse nó deverá ter pelo menos dois filhos que formam um par gêmeo. Portanto, o tempo total de execução é linear.O(n+m)

http://en.wikipedia.org/wiki/Modular_decomposition

Serviço Travis
fonte
Obrigado também por me apresentar a Decomposição Modular!
Gphilip
12

O problema é equivalente a determinar se existem duas linhas iguais na matriz gráfica. Podemos construir três linhas de matriz gráfica. O tempo compleixty será O (n ^ 2)

MikleB
fonte
6
A mesma idéia nas listas de adjacência fornece . O(m+n)
Radu Grigore
Agora estou matando uma mosca;)
Hsien-Chih Chang,
2
Isso pode ser generalizado um pouco. Se reformularmos o problema como "Dado (onde aqui f ( x ) : = N ( x ) ) encontre x 1 , x 2 distintos , de modo que f ( x 1 ) = f ( x 2 ) ", então para Y totalmente ordenado, uma abordagem é avaliar f ( x ) para cada x Xf:X>Yf(x):=N(x)x1x2f(x1)=f(x2)Yf(x)xX, classifique-os e verifique a lista classificada quanto a duplicatas. O trie é efetivamente classificado como radical.
Peter Taylor
8

EDIT: as soluções @MikleB e @Travis são muito inteligentes. Desculpe pela resposta exagerada.


Parece que o problema pode ser reduzido ao problema de multiplicação de matrizes na matriz de adjacência do gráfico, substituindo a multiplicação por EQU (ou seja, NXOR) e a adição por AND. Por isso, se existe um par de gémeos no gráfico, em seguida, a matriz resultante Uma Um T não será a matriz de identidade, e os índices ( i , j ) , onde o valor de i , j não zero é são exactamente os nós duplo par .AAAT(i,j)ai,j

Que eu saiba, o problema da multiplicação de matrizes pode ser resolvido em tempo com α 2.376 pelo algoritmo Coppersmith – Winograd . Se forem necessárias soluções práticas, qualquer algoritmo de multiplicação de matrizes que funcione bem na prática é bom.O(nα)α2.376

Hsien-Chih Chang 張顯 之
fonte
Impressionante isso funciona! : DI acho que será suficiente para avaliar apenas metade superior da . O que você acha? A2
Pratik Deoghare 10/01
1
@TheMachineCharmer: Obrigado :) Sim, se o gráfico não for direcionado.
Hsien-Chih Chang
Sim. Exatamente! :)
Pratik Deoghare
5

Por causa do sistema maluco deste site, não posso comentar diretamente, mas tenho algumas observações sobre as respostas existentes.

Tenho certeza de que as necessidades de soluções de Hsien-Chih Chang para corrigir a A A T .A2AAT

A observação 4 de TheMachineCharmer está de volta à frente (contra-exemplo: [0,0,1], [0,1,0], [0,1,1] tem determinante 0, mas não gêmeos). Se existirem gêmeos, o determinante é zero.

Peter Taylor
fonte
Não vejo problema com o . Algum exemplo? btw, sistema neste site não é louco! :)A2
Pratik Deoghare
A2AAT
O sistema pode não ser louco, mas talvez seja contra-intuitivo os pôsteres da primeira vez. Você pode responder, mas não comentar ... mas seus comentários foram bons o suficiente para justificar a postagem. Depois de criar mais reputação, acho que você achará o sistema bastante viciante.
hardmath
3
Ser capaz de responder, mas não comentar, é uma loucura. Obriga os novos usuários a escolher entre não ser útil ou responder no lugar errado.
Peter Taylor
3

Este tópico é bastante antigo; no entanto, ninguém parece ter adotado a abordagem mais elegante e simples. Classifique Lexicograficamente a lista de adjacências em O (n + m) e verifique se há duplicatas (consulte Aho, Hopcroft, Ullman, 74 '). Você pode usar a decomposição modular, mas isso é um exagero total.

Nathan Lindzey
fonte
2

Esse tópico é antigo e a pergunta do OP foi respondida, mas eu gostaria de adicionar outro algoritmo para encontrar todos esses pares em tempo linear. Ninguém mencionou o refinamento de partição !

Este algoritmo encontra as classes de equivalência de gêmeos falsos. O algoritmo baseia-se em um procedimento eficiente que refina uma partição. Dado um conjunto Se uma partição P = {X1, ..., Xn}. refine(P, S) = {X1 ^ S, X1 - S, X2 ^ S, X2 - S, ..., Xn ^ S, Xn - S}. ^indica interseção -definida e diferença definida. Uma partição é estável se não puder mais ser refinada. Esse procedimento leva tempo O (| S |) (consulte o artigo da Wikipedia sobre refinamento de partição), por isso é rápido.

Algorithm:

P = {V} // initial partition consists of the vertex set
for every vertex v:
    P = refine(P, N(v)) // refine with the open neighborhood of v

O tempo total é O (| V | + | E |). É simples de programar também.

saadtaame
fonte
1

Algumas observações que podem ajudar

  1. a,bVabcdcN(a)dN(b)

  2. |N(a)||N(b)|ab

  3. bN(a)ab

  4. Se existirem gêmeos, o determinante da matriz de adjacência é zero.

Ideia extravagante:

  1. Crie uma árvore binária completa com height = | V |.
  2. Então comece a ler uma linha da matriz de adjacência.
  3. Se você encontrar 0, vire à esquerda, caso contrário, vire à direita.
  4. Quando você alcança uma folha, armazene seu vértice lá.
  5. Faça isso para todas as linhas. Então, no final, cada folha terá vizinhos.

Roubado do algoritmo de compressão Inspired by Huffman! :)

Pratik Deoghare
fonte
2
ab
1
N(a)b=N(b)a