encontrar todos los vértices en un gráfico con un grado menor que sus vecinos

Question

Estoy tratando de escribir un algoritmo que encuentre el conjunto de todos los vértices en un gráfico con un grado menor que sus vecinos. Mi enfoque inicial es encontrar el grado de cada vértice, luego trabajar en la lista y comparar el grado de cada vértice con el (los) grado (s) de sus vecinos. Desafortunadamente, parece que podría llevar mucho tiempo. ¿Hay alguna forma más eficiente de encontrar este conjunto?

Answer 1

Quizás " esto parece que podría llevar mucho tiempo " ;, pero hay una mejor manera de descubrirlo :-)

Suponga que ha almacenado su gráfico como una lista de adyacencia. Para encontrar el conjunto que está buscando, necesariamente tiene que mirar todos los bordes, por lo que tenemos un límite inferior de & # 937; (| E |) para el algoritmo. Encontrar el grado de cada vértice lleva tiempo O (| E |) (porque observa cada borde exactamente una vez; otra prueba es usar el hecho de que & # 8721; d (v) = 2 | E |). Comparar el grado de cada vértice con todos sus vecinos también toma solo O (| E |) tiempo (nuevamente, para cada borde, solo hace una comparación). Esto significa que su algoritmo se ejecuta en tiempo O (| E |) (aproximadamente 2 | E | '' pasos '', pero el número preciso de instrucciones de la CPU depende de su implementación), que cumple con el límite inferior. Por lo tanto, su "fuerza bruta" El algoritmo, en el peor de los casos, es esencialmente (hasta una pequeña constante) lo más rápido posible , por lo que no vale la pena seguir optimizándolo.

Si está haciendo esto para una aplicación del mundo real y de hecho encuentra que su algoritmo está tomando demasiado tiempo, entonces use un generador de perfiles para encontrar qué partes optimizar. No es del todo obvio que la optimización de la segunda fase del algoritmo es crucial.

Answer 2

Un comentario: si está trabajando con gráficos no dirigidos (gracias, Brian R . Bondy ), una vez que haya determinado que un vértice tiene un grado menor que el de todos sus vecinos, no necesita verificarlos, ya que ninguno de ellos tendrá esa propiedad. Considera usar ese conocimiento para ayudarte y acelerar las cosas.

Answer 3

Me imagino un enfoque codicioso para un gráfico no dirigido de la siguiente manera:

let Q = all nodes which haven't been checked (initialize all V)
let Q* = all nodes which satisfy the required condition (initialize to empty)
start with an arbitrary node, v in Q
while Q is not empty
    let minDeg be the minimum degree of all v's neighbors
    if degree(v) < minDeg
        add v to Q*
        remove all neighbors of v from Q
        remove v from Q
        set v = new arbitrary node, v in Q
    else
        remove v from Q
        set v = v's neighbor in Q of minimum degree

Este algoritmo puede ser un poco más eficiente porque en cada iteración, encuentra un nodo satisfactorio o comprueba un nuevo nodo de menor grado y elimina un nodo del gráfico.

En el peor de los casos, será equivalente a su algoritmo de fuerza bruta. Sin embargo, en promedio, creo que debería funcionar mejor.