algorithm - representations - graphs java

Gráfico dirigido con un grado máximo de un vértice

Question

Estaba tratando de ver algunas aplicaciones del flujo de red cuando me encontré con este problema:

Comenzamos con un gráfico dirigido, G = (V,E) . Necesitamos agregar más bordes al gráfico de modo 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 del 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 bordes |V||V-1|/2 . 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 vértice w (y con 2 vértices nuevos 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, dejar x_{ij} = 1 si el arco i-> j aparece en la solución y dejar que 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}

Vuelva a escribir para usar x_{ij} solo 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 (*) comienza a parecerse a las restricciones de conservación, ya que cada variable aparece una vez negativamente y una vez de manera positiva. 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 en el camino hacia un LP de flujo, solo necesitamos limpiar las constantes 1 k . Te dejaré manejar el resto (se trata de introducir t).