grafo dirigido con grado de entrada máximo de un vértice

Question

yo estaba tratando de mirar en algunas aplicaciones de flujo de red cuando me encontré con este problema:

Comenzamos con un grafo dirigido, G = (V,E). Necesitamos agregar más bordes al gráfico para que tengamos \forall u,v \in V, e = (u -> v) or e = (v -> u) but not both. es decir, queremos agregar más bordes al gráfico para que cada par de vértices en el gráfico estén conectados entre sí (ya sea con un borde saliente o un borde entrante, pero no con ambos). Entonces, en total tendremos |V||V-1|/2 bordes. Mientras construimos este gráfico, necesitamos asegurarnos de que el grado de un vértice dado, digamos w es el máximo entre todos los vértices del gráfico (si es posible, dado el gráfico original). Tenga en cuenta que no podemos cambiar la orientación de los bordes en el gráfico original.

Estoy tratando de resolverlo usando el flujo de red construyendo una red sin el vértice w (y con 2 nuevos vértices para fuente, sy sumidero, t). Pero no estoy seguro de cómo representar las capacidades y la dirección del flujo en el nuevo gráfico para simplificar el problema al flujo de la red con el fin de encontrar las orientaciones de los bordes en el gráfico. Tal vez lo que estoy haciendo está mal, pero acabo de escribir si alguien puede obtener una pista de ello.

Answer 1

Al atacar este tipo de problema, tiendo a escribir un programa matemático y luego masajearlo. Claramente, debemos orientar todos los bordes faltantes que involucran w hacia w. Sea d el resultado en grado de w. Para todos los distintos i, j, deje x_{ij} = 1 si el arco i-> j aparece en la solución y deje x_{ij} = 0 si aparece el arco j-> i.

forall j. sum_i x_{ij} <= k 
forall i <> j. x_{ij} = 1 - x_{ji} 
forall i <> j. x_{ij} in {0, 1} 

de reescritura de usar x_{ij} sólo si i < j.

(*) forall j. sum_{i<j} x_{ij} + sum_{i>j} (1-x_{ji}) <= k 
forall i < j. x_{ij} in {0, 1} 

ahora (*) empieza a parecerse a las limitaciones de conservación, ya que cada variable aparece una vez negativamente y positivamente una vez. Cambiemos la desigualdad a una igualdad.

(*) forall j. x_{si} + sum_{i<j} x_{ij} + sum_{i>j} (1-x_{ji}) = k 
       ^^^^^^           ^
forall i < j. x_{ij} in {0, 1} 
forall i. x_{si} >= 0 
^^^^^^^^^^^^^^^^^^^^^ 

Estamos casi todo el camino a un flujo de LP - sólo tenemos que limpiar las constantes 1 y k. Te dejaré manejar el resto (se trata de introducir t).