La complejidad temporal de encontrar el diámetro de un gráfico

27

¿Cuál es la complejidad temporal de encontrar el diámetro de un gráfico ?G=(V,E)

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

El diámetro de un gráfico es el máximo del conjunto de distancias de camino más cortas entre todos los pares de vértices en un gráfico.G

No tengo idea de qué hacer al respecto, necesito un análisis completo sobre cómo resolver un problema como este.

Gigili
fuente
44
Por favor elabore un poco. ¿Por qué es este problema de interés para usted? ¿Necesita una pista, un análisis completo o una referencia? ¿Estás interesado en el peor o el peor de los casos? ¿Está dirigido ? G
Raphael
@Raphael: Obviamente no necesito una pista, necesito un análisis completo. Edité mi pregunta de todos modos.
Gigili
1
@Gigili Te refieres a en todos los casos, ¿verdad? De lo contrario, todos están subsumidos por la última posibilidad (que está en gráficos generales iguales a ) lo que la convierte en una respuesta correcta, suponiendo que al menos una respuesta se supone que es correcta. Una preocupación adicional es que en un gráfico con ciclos, no hay una ruta más larga. ¿Qué se entiende por "distancia más larga"? ΘO(|V|5)
Raphael
@Gigili ¿De dónde vienen las cuatro opciones?
uli

Respuestas:

5

Actualizar:

Esta solución no es correcta.

Lamentablemente, la solución solo es cierta (y directa) para los árboles Encontrar el diámetro de un árbol ni siquiera necesita esto. Aquí hay un contraejemplo para gráficos (el diámetro es 4, el algoritmo devuelve 3 si elige este ):v

ingrese la descripción de la imagen aquí


Si el gráfico está dirigido, esto es bastante complejo, aquí hay un documento que afirma resultados más rápidos en el caso denso que el uso de algoritmos para las rutas más cortas de todos los pares.

Sin embargo, mi punto principal es sobre el caso de que el gráfico no esté dirigido y con pesos no negativos, escuché sobre un buen truco varias veces:

  1. Elige un vérticev
  2. Encuentra tal que es máximod ( v , u )ud(v,u)
  3. Encuentre tal que sea ​​máximod ( u , w )wd(u,w)
  4. Retornod(u,w)

Su complejidad es la misma que la de las dos primeras búsquedas de amplitud sucesivas¹, es decir, si el gráfico está conectado².O(|E|)

Parecía folklore pero en este momento, todavía estoy luchando por obtener una referencia o probar su corrección. Actualizaré cuando logre uno de estos objetivos. Parece tan simple que publico mi respuesta ahora mismo, tal vez alguien la reciba más rápido.

¹ si el gráfico está ponderado, Wikipedia parece decir pero solo estoy seguro acerca de .O ( | E | log | V | )O(|E|+|V|log|V|)O(|E|log|V|)

² Si el gráfico no está conectado, obtienes pero es posible que agregar para elegir un elemento de cada componente conectado. No estoy seguro de si esto es necesario y, de todos modos, puede decidir que el diámetro es infinito en este caso.O(|V|+|E|)O(α(|V|))

jmad
fuente
Para que Mkae Dijsktra trabaje en el tiempo especificado, debe usar montones de Fibonacci, no la implementación habitual.
Suresh
8
Esta es una respuesta muy incorrecta, este algoritmo es folklore pero en árboles no en gráficos generales. PD: Puedo ver tu ejemplo de contador, pero no es una buena respuesta ser marcado como respuesta.
Tengo dos preguntas sobre la solución incorrecta. 1. ¿Esto al menos daría un rango en el que debe estar la respuesta correcta? por ejemplo, si el método encuentra el diámetro d , ¿la solución correcta estará entre d y 2d ? 2. ¿Qué sucede si agregamos otra indirección y consideramos todos los nodos encontrados por una indirección (no solo uno)? El ejemplo de contador dado en la publicación funcionaría entonces, ya que los vértices periféricos verdaderos se encuentran entre los nodos encontrados por la segunda indirección.
mafu
32

Supongo que significa el diámetro de que es el más largo del camino más corto encontrado en .GG

Se puede encontrar el diámetro encontrando primero todos los pares de caminos más cortos y determinando la longitud máxima encontrada. El algoritmo Floyd-Warshall hace esto en tiempo . El algoritmo de Johnson se puede implementar para alcanzar el tiempo .Θ(|V|3)O(|V|2log|V|+|V||E|)

Parece difícil lograr un límite de tiempo de ejecución más pequeño en el peor de los casos, ya que hay distancias a considerar y calcular esa distancia en tiempo sublineal (amortizado) cada una será difícil; ver aquí para un enlace relacionado. Tenga en cuenta este documento que utiliza un enfoque diferente y obtiene un algoritmo (ligeramente) más rápido.O(|V|2)

Rafael
fuente
2
Si recibe pagos en esos documentos, consulte Google Scholar.
Raphael
Además, vale la pena señalar esta excepción para los árboles no dirigidos , donde puede obtener dia. con solo un dfs transversal.
azam
15

También puede considerar un enfoque teórico de gráfico algebraico. El diámetro es el menor entero st la matriz tiene la propiedad de que todas las entradas de son distintas de cero. Puede encontrar por iteraciones de multiplicación de matrices. El algoritmo de diámetro requiere entonces el tiempo , donde es el límite para la multiplicación de matrices. Por ejemplo, con la generalización del algoritmo Coppersmith-Winograd por Vassilevska Williams, el algoritmo de diámetro se ejecutaría en . Para una introducción rápida, vea el Capítulo 3 en el libro de Fan Chung aquí .diam(G)tM=I+AMttO(logn)O(M(n)logn)M(n)O(n2.3727logn)

Si restringe su atención a una clase de gráfico adecuada, puede resolver el problema de APSP en un tiempo óptimo . Estas clases incluyen al menos gráficos de intervalo, gráficos de arco circular, gráficos de permutación, gráficos de permutación bipartitos, gráficos fuertemente cordales, gráficos bipartitos cordales, gráficos hereditarios de distancia y gráficos doblemente cordales. Por ejemplo, ver Dragan, FF (2005). Estimación de todos los pares de rutas más cortas en familias de gráficos restringidos: un enfoque unificado. Journal of Algorithms, 57 (1), 1-21 y sus referencias.O(n2)

Juho
fuente
2
Vale la pena señalar que este algoritmo solo funciona en el caso no ponderado.
GMB
-2

Suposiciones:
1. El gráfico no está ponderado
2. El gráfico está dirigido

O (| V || E |) complejidad de tiempo.

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

Explicación:
Verificamos el ciclo. si el gráfico contiene un ciclo, seguimos moviéndonos en el bucle, por lo que tendremos una distancia infinita. Verificamos la conexión. Si el gráfico no está conectado, eso significa vértice u desde G1 al vértice v en G2. Donde G1 y G2 son dos sub-gráficos que no están conectados. Entonces volveremos a tener una distancia infinita. Usaremos BFS para calcular la distancia máxima entre un nodo dado (u) a todos los demás nodos (v) a los que se puede acceder desde u. Luego tomaremos el máximo del diámetro previamente calculado y el resultado será devuelto por BFS. Entonces tendremos el diámetro máximo actual.

Análisis del tiempo de ejecución:

  1. O (| E |) usando DFS
  2. O (| E |) usando DFS
  3. BFS se ejecuta en tiempo O (| E |).
  4. Tenemos que llamar a la función BFS para cada vértice, por lo que el total llevará tiempo O (| V || E |).

Tiempo total = O (| v || E |) + O (| E |) + O (| E |)
Desde | V || E | > | E |
entonces tenemos tiempo de ejecución como O (| v || E |).

BFS
DFS

Nota: Esta no es una solución elegante para este problema.

sonus21
fuente
Las gráficas conectadas acíclicas son árboles, para los cuales el problema es más fácil (porque el diámetro viene dado por el camino más largo). Se ha tratado aquí y aquí , donde se dan algoritmos más rápidos. (Un recorrido recursivo o, alternativamente, dos BFS son suficientes.)
Raphael
1
@Raphael No, los gráficos acíclicos no dirigidos son árboles. Los DAG son DAG.
David Richerby
@DavidRicherby Derecha. (Aunque, técnicamente, la respuesta no dice si excluye los ciclos dirigidos o no dirigidos;)) De todos modos, esto no es más que resolver APSPP (el enfoque ingenuo), que ya ha sido cubierto para el caso general por las respuestas anteriores.
Raphael
@Raphael ¿Estás seguro de que los gráficos acíclicos son árboles? El gráfico es acíclico no significa que el gráfico siempre será un árbol. El árbol es solo un caso especial de esto. También es un algoritmo directo y la complejidad del tiempo es O (| V || E |).
sonus21
Sí estoy seguro. (Tal vez estás pensando en árboles enraizados , que tienen un sabor diferente.)
Rafael