graph-theory – ¿Es esta optimización de ordenamiento de vértices NP-Hard?

Pregunta:

¿Podría ayudarme a demostrar que el siguiente problema es NP-hard?

Problema. Dado un gráfico no dirigido $ G = (V, E) $ , encuentre un orden de los nodos tal que $ \ sum \ limits_ {v \ in V} | succ (v) | \ times | pred (v) | $ es mínimo .

Dado un orden en los nodos y un nodo $ v \ en V $ , $ pred (v) $ (resp. $ Succ (v) $ ) denota el conjunto de vecinos de $ v $ con orden inferior (resp. Superior).

Respuesta:

Considere su problema restringido a tres gráficos regulares. Considere algún orden de los vértices. Defina un vértice dividido para que sea un vértice $ v $ de modo que tanto $ succ (v) $ como $ pred (v) $ no estén vacíos y defina un vértice no dividido para que sea cualquier otro vértice. Observe que en una gráfica de 3 regulares, el valor de $ | succ (v) | \ times | pred (v) | $ es $ 0 $ si $ v $ es un vértice no dividido y es $ 2 $ en caso contrario.

Por lo tanto, $ \ sum \ limits_ {v \ in V} | succ (v) | \ times | pred (v) | = 2n _ {\ text {split}} $ donde $ n _ {\ text {split}} $ es el número de vértices divididos.

Por lo tanto, en gráficos regulares de 3, resolver su problema (minimizar la suma) es equivalente a elegir un orden para minimizar el número de vértices divididos.

El siguiente teorema nos dice que resolver su problema en una gráfica tridimensional $ G $ es equivalente a resolver Max Cut en $ G $. Por lo tanto, dado que Max Cut en gráficos de 3 regulares es NP-hard, también lo es su problema.

Teorema Si $ G = (V, E) $ es un gráfico regular 3 con $ n $ vértices, entonces existe un orden de los vértices tal que el número de vértices divididos es como máximo $ k $ si y solo si $ G $ tiene un tamaño de corte de al menos $ \ frac {3} {2} n – k $.

Primera direccion

Primero, suponga que existe un orden de los vértices tal que el número de vértices divididos sea como máximo $ k $. Luego dividimos $ V $ en dos conjuntos $ A $ y $ B $ de la siguiente manera:

  1. Coloque todos los vértices no divididos (debajo del orden) en $ A $ y $ B $ colocando los vértices con 3 sucesores en $ A $ y los vértices con 3 predecesores en $ B $.
  2. Agregue provisionalmente todos los vértices divididos (debajo del orden) en $ A $.
  3. Repita los pasos 4 y 5 hasta que falle el paso 4:
  4. Identifique un vértice dividido $ v $ que tenga más vecinos en su conjunto actual ($ A $ o $ B $) que en el otro
  5. Mueva $ v $ al otro conjunto

La partición de $ V $ en $ A $ y $ B $ es un corte, y cada ocurrencia de los pasos 4 y 5 aumenta el tamaño de ese corte, por lo que este procedimiento terminará. A continuación, calculamos el tamaño del corte resultante.

Observe también que cada vértice dividido $ v $ en $ A $ (o $ B $) tiene como máximo un vecino en $ A $ (o $ B $) porque de lo contrario este vértice se habría identificado en el paso 4 en la iteración final del bucle. Por lo tanto, el número de aristas que inciden en los vértices divididos que están dentro de $ A $ o dentro de $ B $ está acotado arriba por el número de vértices divididos (que sabemos que es como máximo $ k $).

A continuación, considere cualquier borde $ (u, v) $ que no incida en un vértice dividido. Esta arista debe estar entonces entre dos vértices no divididos. Suponga que wlog que $ u $ es anterior a $ v $ en el pedido. Entonces, dado que $ u $ es un vértice no dividido con un sucesor, debe darse el caso de que $ u $ en realidad tenga 3 sucesores y, de manera similar, $ v $ debe tener 3 predecesores. Podemos concluir de esto que $ u $ se coloca en $ A $ y $ v $ se coloca en $ B $ y, por lo tanto, $ (u, v) $ no es una ventaja dentro de $ A $ o dentro de $ B $.

Por lo tanto, concluimos que el número total de aristas dentro de $ A $ o dentro de $ B $ es como máximo $ k $. Entonces, el tamaño del corte (es decir, el número de bordes que no están dentro de $ A $ y no dentro de $ B $) es al menos $ | E | – k = \ frac {3} {2} n – k $.

Segunda direccion

Ahora suponga que existe un corte de tamaño al menos $ \ frac {3} {2} n – k $. Suponga que esto corta particiones $ V $ en conjuntos $ A $ y $ B $. Luego construimos un orden de los vértices en $ V $ colocando los vértices en $ A $ primero y los vértices en $ B $ después. Afirmamos que el número de vértices divididos bajo este orden es como máximo $ k $.

Considere cualquier incidente de borde en un vértice en $ A $. Si esta arista es $ (u, v) $ con $ u \ en A $ y $ v \ en B $ entonces $ v $ es un sucesor de $ u $ ya que todos los vértices en $ B $ son después de todos los vértices en $ A PS Por lo tanto, las aristas entre $ A $ y $ B $ no contribuyen con ningún predecesor a ningún vértice en $ A $. El único otro incidente de borde posible en un vértice en $ A $ es un borde dentro de $ A $. Tal ventaja aporta un predecesor a exactamente uno de sus puntos finales. Por lo tanto, el total de todos los $ v \ en A $ del número de predecesores de $ v $ es como máximo el número de aristas dentro de $ A $, por lo que el número de vértices en $ A $ con un predecesor es como máximo el número de aristas dentro de $ A $. Dado que cada vértice dividido en $ A $ es un vértice en $ A $ con un predecesor, el número de vértices divididos en $ A $ es como máximo el número de aristas dentro de $ A $.

Se puede usar una lógica análoga para mostrar que el número de vértices divididos en $ B $ es como máximo el número de aristas dentro de $ B $. Entonces, el número total de vértices divididos bajo este orden es como máximo el número de aristas dentro de $ A $ o dentro de $ B $. Dado que el corte tiene al menos $ \ frac {3} {2} n – k = | E | – k $ aristas entre $ A $ y $ B $, debe tener como máximo $ k $ aristas dentro de $ A $ o dentro de $ B $. Concluimos que el número de vértices divididos bajo el orden construido es como máximo $ k $.

Leave a Comment

Your email address will not be published.

Scroll to Top

istanbul avukat

-

web tasarım