Como encontrar uma estrela mundial no tempo linear?

28

Considere gráficos direcionados. Chamamos um nó astro se e somente se nenhum outro nó pode ser alcançado a partir dele, mas todos os outros nós temos uma vantagem para . Formalmente:v v

v Super estrela : ⟺ovocêtdeg(v)=0 0Eundeg(v)=n-1 1

com o número de nós no gráfico. Por exemplo, no gráfico abaixo, o nó não preenchido é uma superestrela (e os outros nós não).n

A Superstar
[ fonte ]

Como você pode identificar todas as estrelas em gráficos direcionados em ? Uma representação gráfica adequada pode ser escolhida entre os candidatos habituais ; evite usar representações que movam a complexidade do problema para o pré-processamento.O(n)

Nenhuma suposição sobre densidade pode ser feita. Não assumimos que o gráfico contenha uma estrela; se não houver, o algoritmo deve reconhecê-lo.

Notação : é o número de arestas de saída de um nó, semelhante às arestas de entrada.ovocêtdegEundeg

Rafael
fonte
11
É permitido onde k é arestas ou precisamos observar apenas O ( 1 ) arestas em cada vértice? O(n+k)kO(1)
Kevin
@ Kevin Não, é um requisito estrito. Em relação à segunda pergunta: não sei se é necessário, mas você certamente não pode fazer mais. O(n)
Raphael
Você sabe a resposta? Isso pode ser feito em ? O(n)
Dave Clarke
@DaveClarke: Sim e sim.
Raphael
Você deve restringir ainda mais a representação; um algoritmo linear é impossível para uma lista de adjacência (apenas para confirmar que um vértice é uma superestrela, pode ser necessário percorrer a lista inteira em cada vértice).
Gilles 'SO- stop be evil'

Respostas:

18

Podemos eliminar todos os vértices, exceto um, verificando a existência de arestas, porque podemos eliminar uma possibilidade para cada aresta que verificamos. Em particular, se houver uma aresta passando de x para y , eliminamos x e passamos para y (como outro vértice pode ser alcançado a partir dele); caso contrário, eliminamos y (pois não pode ser alcançado a partir de x ). Quando atingirmos o último vértice, o vértice que não for eliminado deve ser comparado com o outro (verifique se a condição de superestrela é mantida: existe uma aresta de entrada, mas não de saída) até que seja eliminada ou confirmada como superestrela. Algum pseudocódigo:n1xyxyyx

vertex superstar(graph g)
    current vertex = first
    # Go through each vertex
    for each subsequent vertex in g ("next")
        # If there's an edge from this to the next, we eliminate this one [move to the new one].
        # If not, we just stay here.
        if edge exists from current to next
            candidate = next
        end if
    end for
    # Now we are on the final remaining candidate, check whether it satisfies the requirements.
    # just a rename for clarity
    candidate = current
    for each other vertex in g
        if edge from current to other exists
            return null 
        else if no edge from other to current
            return null
        end if
    end for
    return candidate
end superstar

Vamos percorrer um exemplo para ilustrar o método. Pegue essa matriz, com o vértice de origem na parte superior e o destino ao lado. 1 indica uma aresta:

12341 1-1 10 01 121 1-0 01 131 11 1-1 141 11 10 0-

Vou esmaecer os vértices que descartamos como possíveis astros. Usarei verde e vermelho para indicar as arestas que estamos vendo quando elas contêm e não contêm a aresta que estamos procurando, e azul para indicar onde já olhamos.

Começamos olhando os vértices 1 e 2.

O número verde mostra que há uma aresta de 2 a 1, portanto, eliminamos 2 e procuramos uma aresta de 3 a 1 :

1 12341 1-1 10 01 121 1-0 01 131 11 1-1 141 11 10 0-

1 12341 1-1 10 01 121 1-0 01 131 11 1-1 141 11 10 0-

Como vemos que não existe essa aresta, eliminamos 1 e consideramos 3 como nosso vértice atual. Lembre-se de que já eliminamos 2 e verifique se há uma margem de 4 para 3:

1 12341 1-1 10 01 121 1-0 01 131 11 1-1 141 11 10 0-

Há uma aresta de 4 a 3, portanto, eliminamos 4. Nesse ponto, eliminamos todos os vértices (3), com exceção de um, então verifique suas arestas e veja se ele se qualifica:

1 12341 1-1 10 01 121 1-0 01 131 11 1-1 141 11 10 0-

Há uma margem de 1 a 3, mas não o inverso; portanto, 3 ainda é um candidato.

1 12341 1-1 10 01 121 1-0 01 131 11 1-1 141 11 10 0-

Há também uma margem de 2 a 3, mas não o inverso; portanto, 3 ainda é um candidato.

1 12341 1-1 10 01 121 1-0 01 131 11 1-1 141 11 10 0-

Há uma margem de 4 para 3, mas não de 3 para 4; que completa nossa verificação das arestas de 3 e descobrimos que é, de fato, uma estrela.

n-1 1nnn-1 12×(n-1 1)3n-3O(n)Θ(n)

Kevin
fonte
8

Não é este o problema das celebridades ?

Só haverá uma estrela (celebridade) se houver uma.

UMA[Eu,j]=1 1Euj0 0

UMA[Eu,j]O(1 1)UMA[Eu,j]=1 1EuUMA[Eu,j]=0 0j

Mantenha uma lista de candidatos atuais, eliminando um por um. Uma lista vinculada deve ser suficiente.

No final, você pode verificar se o seu candidato é realmente uma estrela.

O(n)

Aryabhata
fonte
(Eu,j)
3
@ Rafael: Basta escolher os dois primeiros candidatos da lista vinculada. (cabeça e cabeça-> próxima).
Aryabhata
6

Esta resposta aborda a versão da pergunta em que era possível qualquer representação gráfica, e não a versão atual da pergunta.

  • Armazene seu gráfico como um par de lista de adjacência e lista de adjacência inversa, onde cada lista contém além do comprimento da lista, daí o número de fora e de dentro, respectivamente.

  • O(|E|)

  • 0 0n-1 1O(|N|)

Dave Clarke
fonte
Ok, vejo que permitir qualquer representação gráfica é muito fraca. Limitei a pergunta ao que pretendia.
Raphael
2

Apenas para referência, esse é um pseudocódigo de uma versão recursiva do que Kevin postou.

superstar(V, E) {
  if ( |V| == 1 ) {
    return V.pop
  }

  a = V.pop
  b = V.pop
  if ( (a,b) ∈ E ) {
    no_ss = a
    keep  = b
  }
  else {
    no_ss = b
    keep = a
  }

  s = superstar(V ++ keep)

  return ( s != null && (no_ss, s) ∈ E && !(s, no_ss) ∈ E ) ? s : null
}

hasSuperstar(V, E) = superstar(V, E) != null
Rafael
fonte