Máxima de flujo y un mínimo de corte en completar los gráficos

Question

La pregunta es la siguiente:

Definimos en el grafo completo $K_n$ con los vértices {$v_1, v_2, ... , v_n$} las siguientes instrucciones: para cada j>i, el borde de la $v_i v_j$ es dirigido de $v_i$ $v_j$si |i-j| es impar, y de $v_j$ $v_i$si |i-j| es incluso. Podemos definir la capacidad de función de c($v_i v_j$)=|i-j|, y establecer $v_1$ como el origen y el $v_n$ como el receptor. Encontrar un flujo máximo y corte mínimo.

Obviamente la idea es usar el Max-Min de flujo de corte Teorema. Sin embargo, me encuentro con algunas dificultades cuando se intenta implicar, y me temo que es principalmente debido a la falta de comprensión. Mi idea de la solución comenzó con la informática $val(f)$ (el valor de la corriente). Cada borde conectado a la pileta, n por lo tanto será negetive si se sale de ella, y positivo si se entra en ella. Así que tengo:

$val(f)=\sum_{x=1}^{n-1}(-1)^{n-x+1}*(n-x)=\frac{1}{4}(2*(-1)^n*n-(-1)^n+1)$

Pero entonces, si n es impar me sale que el valor es negetive. Estoy haciendo la suma de malo? Cómo puedo encontrar un accesorio de la fuente del disipador de corte para un negetive valor de la corriente? Es incluso posible? Y cuando n es par, llego $n/2$. Aún así es difícil encontrar un accesorio de la fuente del disipador de corte con la misma capacidad, al menos yo no puedo pensar en un método para hacerlo.

Cualquier sugerencias/correcciones/ideas serán muy apreciados.

Actualización: me las arreglé para encontrar la solución para el extraño $n$. He definido el siguiente flujo: para cada $1<x<n$, donde x es par, me permiten el flujo de x a n a estar en plena capacidad (y ninguno de n). Además, puedo añadir un flujo de 1 para cada x en plena capacidad. Por último, quiero agregar un flujo entre cada x y (n-x+1) (que va a ir en la dirección de la menor de uno), a plena capacidad. Luego me muestran que el flujo de he descrito es factible ya que tiene la conservación de las restricciones para cada x (el impar de vértices además de 1 y n no tienen flujo proveniente de ellos o en ellos, todo a 0). Una vez hecho esto, es obvio que la capacidad de corte de todos los vértices además de n es el mismo que el de val(f) de este flujo, y por lo tanto es una máxima de flujo y un mínimo de corte. El valor de acuerdo a la suma es $\frac{1}{4}(n-1)^2$.

Todavía lucho con incluso n. Puedo ver que para cada n he comprobado (hasta 10), hubo un flujo factible en donde todos los impares vértices dio su plena capacidad en n (y ninguno fuera de él, por supuesto). Sin embargo, cada una de las muchas rutas adicionales para hacer factible. Hay un cierto patrón para estas rutas, pero no lo encuentro. Voy muy agradezco si alguien me puede orientar el patrón de estos caminos que seguir, que permiten un flujo factible.

Answer 1

Parece que he conseguido resolverlo.

Hemos dividido el caso incluso para n, y las impares de n. La idea en general es mostrar que, en ambos casos, hay un flujo factible en donde cada arista dirigida a los n flujos, con plena capacidad, mientras que ninguno sale de n. Si un flujo es factible, es obviamente un flujo máximo y corte mínimo de mismo valor (más allá de cómo intutive es que el flujo es máximo en ese caso, el flujo de tener el mismo valor que el corte de todos los vértices además de n, y por lo tanto tenemos un corte mínimo y máximo de flujo.

Impar n:

Ponemos todos los incluso los vértices para ir a $n$, a plena capacidad. Nos pusimos $1$ a ir a todos los incluso los vértices a plena capacidad. Hemos creado una plena capacidad de flujo entre cada vértice $x$, y del otro, incluso vértice $n-x+1$. Todas las otras corrientes son cero. Como podemos ver no hay impar de vértices entre 1 y n ha sido afectado, por lo que sólo tenemos que asegurar que para cada vértice $x, 1<x<n$, $f^+(v)-f^-(v)=0$. Y en efecto: $+(n-x)-(x-1)-(n-x+1-x)=0$. Por lo tanto, este flujo es factible.

En este caso, $val(f)=cap(S,T)=\sum_{x=1}^{\frac{n-1}{2}}(n-2x)=\frac14(n-1)^2$

Incluso n:

Aquí se pone un poco más complicado. Definimos todos impar de vértices $x, 1<x<n$ a un flujo de a $n$ a plena capacidad. A continuación, $1$ también las corrientes a plena capacidad, a cada una de las $x-1, 1<x-1<n$ (al $x-1$ es, obviamente, incluso). A su vez, $x-1$ corrientes a plena capacidad a $x$, y en la capacidad restante a $2$, que se convierte en los flujos de nuevo con la misma capacidad restante a $x$, que luego se distribuye a esta capacidad para dos para cada una de las $x-2i, 1<x-2i<x$. En este caso volveremos a conseguir ese $f^+(v)-f^-(v)=0$ Y por lo tanto el flujo es factible.

En este caso,$val(f)=cap(S,T)=\sum_{x=1}^{\frac{n}{2}}(n-(2x-1))=\frac{n^2}{4}$.