A complexidade do tempo para encontrar o diâmetro de um gráfico

27

Qual é a complexidade temporal de encontrar o diâmetro de um gráfico G=(V,E) ?

  • O(|V|2)
  • O(|V|2+|V||E|)
  • O(|V|2|E|)
  • O(|V||E|2)

O diâmetro de um gráfico G é o máximo do conjunto das menores distâncias do caminho entre todos os pares de vértices em um gráfico.

Não tenho idéia do que fazer, preciso de uma análise completa sobre como resolver um problema como esse.

Gigili
fonte
4
Por favor, elabore um pouco. Por que esse problema é do seu interesse? Você precisa de uma dica, uma análise completa ou uma referência? Você está interessado no pior ou no tempo médio? é Gdirigido?
Raphael
@ Rafael: Obviamente não preciso de uma dica, preciso de uma análise completa. Eu editei minha pergunta de qualquer maneira.
Gigili 10/03/12
11
@Gigili Você quer dizer em todos os casos, certo? Caso contrário, todos serão incluídos na última possibilidade (que está em gráficos gerais iguais a O ( | V | 5 ) ), o que a torna uma resposta correta, assumindo que pelo menos uma resposta esteja correta. Uma preocupação adicional é que, em um gráfico com ciclos, não há caminho mais longo. O que se entende por "maior distância"? ΘO(|V|5)
Raphael
@Gigili De onde vêm as quatro opções?
221 uli

Respostas:

5

Atualizar:

Esta solução não está correta.

Infelizmente, a solução é verdadeira (e direta) para árvores! Encontrar o diâmetro de uma árvore nem precisa disso. Aqui está um contra-exemplo para gráficos (o diâmetro é 4, o algoritmo retorna 3 se você escolher este ):v

insira a descrição da imagem aqui


Se o gráfico for direcionado, isso é bastante complexo, eis alguns trabalhos que reivindicam resultados mais rápidos no caso denso do que usar algoritmos para os caminhos mais curtos de todos os pares.

No entanto, meu ponto principal é sobre o caso de o gráfico não ser direcionado e com pesos não negativos, ouvi um truque interessante várias vezes:

  1. Escolha um vértice v
  2. Encontre modo que d ( v , u ) seja máximovocêd(v,u)
  3. Encontre modo que d ( u , w ) seja máximoWd(você,W)
  4. Retorno d(você,W)

Sua complexidade é igual a duas primeiras buscas sucessivas¹, ou seja, se o gráfico estiver conectado².O(|E|)

Parecia folclore, mas, no momento, ainda estou lutando para obter uma referência ou provar sua correção. Atualizarei quando atingir um desses objetivos. Parece tão simples que eu posto minha resposta agora, talvez alguém entenda mais rápido.

¹ se o gráfico for ponderado, a wikipedia parece dizer mas só tenho certeza sobre O ( | E | log | V | ) .O(|E|+|V|registro|V|)O(|E|registro|V|)

² Se o gráfico não estiver conectado, você obtém mas pode ser necessário adicionar O ( α ( | V | ) ) para selecionar um elemento de cada componente conectado. Não tenho certeza se isso é necessário e, de qualquer maneira, você pode decidir que o diâmetro é infinito neste caso.O(|V|+|E|)O(α(|V|))

jmad
fonte
Para trabalhar com o Dijsktra no tempo limite especificado, você precisa usar pilhas de Fibonacci, não a implementação usual.
Suresh
8
Esta é uma resposta fortemente errada, esse algoritmo é folclórico, mas em árvores, não em gráficos gerais. PS: Eu posso ver seu exemplo contrário, mas não é uma boa resposta ser marcada como resposta.
Eu tenho duas perguntas sobre a solução errada. 1. Isso daria pelo menos um intervalo em que a resposta correta deve estar? por exemplo, se o método encontrar o diâmetro d , a solução correta estará entre d e 2d ? 2. O que acontece se adicionarmos outro indireção e considerarmos todos os nós encontrados por um indireção (não apenas um)? O contra-exemplo dado no post funcionaria, pois os vértices periféricos verdadeiros estão entre os nós encontrados pelo segundo indireto.
Mafu
32

Presumo que significa que o diâmetro de que é o maior caminho mais curto encontrado em G .GG

A localização do diâmetro pode ser feita localizando primeiro todos os caminhos mais curtos do par e determinando o comprimento máximo encontrado. O algoritmo de Floyd-Warshall faz isso em . O algoritmo de Johnson pode ser implementado para obter O ( | V | 2 log | V | + | V |Θ(|V|3) .O(|V|2log|V|+|V||E|)

Um limite de tempo de execução menor, na pior das hipóteses, parece difícil de obter, pois existem distâncias ) a serem consideradas e o cálculo dessas distâncias no tempo sublinear (amortizado), cada um será difícil; vejaaquipara um limite relacionado. Observeesteartigo que usa uma abordagem diferente e obtém um algoritmo (um pouco) mais rápido.O(|V|2)

Rafael
fonte
2
Se você receber pagamentos nesses papéis, consulte o Google Scholar.
Raphael
Além disso, vale ressaltar essa exceção para árvores não direcionadas , onde é possível obter dia. com apenas um dfs transversal.
21916
15

Você também pode considerar uma abordagem teórica de gráfico algébrico. O diâmetro é a menor inteiro t r a matriz M = I + A tem a propriedade de que todas as entradas de H t é diferente de zero. Você pode encontrar t por O ( log n ) iterações da multiplicação de matrizes. O algoritmo de diâmetro requer tempo O ( M ( n ) log n ) , onde M ( n )diam(G)tM=Eu+UMAMttO(registron)O(M(n)registron)M(n)é o limite para multiplicação de matrizes. Por exemplo, com a generalização do algoritmo de Coppersmith-Winograd por Vassilevska Williams, o algoritmo de diâmetro seria executado em . Para uma rápida introdução, consulte o Capítulo 3 no livro de Fan Chung aqui .O(n2,3727registron)

Se você restringir sua atenção a uma classe de gráfico adequada, poderá resolver o problema do APSP no tempo ideal de . Essas classes incluem pelo menos gráficos de intervalo, gráficos de arco circular, gráficos de permutação, gráficos de permutação bipartidos, gráficos fortemente cordais, gráficos bipartidos cordais, gráficos hereditários à distância e gráficos duplamente cordais. Por exemplo, veja Dragan, FF (2005). Estimando todos os pares de caminhos mais curtos em famílias de gráficos restritos: uma abordagem unificada. Jornal de Algoritmos, 57 (1), 1-21O(n2) e suas referências.

Juho
fonte
2
Vale ressaltar que esse algoritmo funciona apenas no caso não ponderado.
GMB 23/01
-2

Pressupostos:
1. O gráfico não é ponderado
2. O gráfico é direcionado

Complexidade temporal O (| V || E |).

Algoritmo:

ComputeDiameter(G(V,E)):
  if ( isCycle( G(v,E) ) ) then
     return INFINITY
  if ( not isConnected( G(V,E) )) then
     return INFINITY
  diameter = 0
  for each vertex u in G(V,E):
     temp = BFS(G,u)
     diameter = max( temp , diameter )
  return diameter

Explicação:
Verificamos o ciclo. se o gráfico contiver ciclo, continuaremos movendo-nos no loop, e assim teremos uma distância infinita. Verificamos se está conectado. Se o gráfico não estiver conectado, significa o vértice u de G1 ao vértice v em G2. Onde G1 e G2 são dois subgráficos que não estão conectados. Então, teremos uma distância infinita novamente. Usaremos o BFS para calcular a distância máxima entre um determinado nó (u) e todos os outros nós (v) que são acessíveis a partir de u. Então, tomaremos o máximo do diâmetro previamente calculado e o resultado retornado pelo BFS. Então, teremos o diâmetro máximo atual.

Análise do tempo de execução:

  1. O (| E |) usando DFS
  2. O (| E |) usando DFS
  3. O BFS é executado no tempo O (| E |).
  4. Temos que chamar a função BFS para cada vértice, para que o total demore O (| V || E |).

Tempo total = O (| v || E |) + O (| E |) + O (| E |)
Desde | V || E | > | E |
então temos o tempo de execução como O (| v || E |).

DFS do BFS

Nota: Esta não é uma solução elegante para este problema.

sonus21
fonte
Gráficos acíclicos conectados são árvores, para as quais o problema é mais fácil (porque o diâmetro é dado pelo caminho mais longo). Foi tratado aqui e aqui , onde são fornecidos algoritmos mais rápidos. (Uma travessia recursiva ou, alternativamente, duas BFS são suficientes).
Raphael
11
@Raphael Não, os gráficos não direcionados acíclicos são árvores. DAGs são DAGs.
David Richerby 10/09/15
@DavidRicherby Right. (Embora, tecnicamente, a resposta não diga se exclui ciclos direcionados ou não direcionados.;)) De qualquer forma, isso nada mais é do que resolver o APSPP (a abordagem ingênua), que já foi abordada no caso geral por respostas anteriores.
Raphael
@ Rafael Você tem certeza de que os gráficos acíclicos são árvores? O gráfico é acíclico não significa que o gráfico sempre será uma árvore. A árvore é apenas um caso especial disso. Também é um algoritmo direto e a complexidade do tempo é O (| V || E |).
sonus21
Sim eu tenho certeza. (Talvez você está pensando em enraizadas árvores, que são um sabor diferente.)
Raphael