algorithm - sirven - Gráficos de Cangrejo, Algoritmos, Teoría de Gráficos, ¿Cómo fluye esta red?

teoria de grafos ejercicios resueltos

Question

¿Puede alguien ayudarme con este problema? Aparentemente, la solución está utilizando el flujo de red, pero no estoy muy familiarizado con el flujo de la red. ¿Cómo te ayuda el flujo de red a resolver esto?

Un cangrejo es un gráfico no dirigido que tiene dos tipos de vértices: 1 cabeza y K pies, y exactamente K bordes que unen la cabeza a cada una de las patas. (1 <= K <= T, donde se da T)

Dado un gráfico no dirigido, tienes que encontrar en él algunos subgrafos de vértices separados donde cada uno es un cangrejo. El objetivo es seleccionar esos cangrejos de tal manera que se maximice el número total de vértices cubiertos por ellos.

Nota: dos gráficos son vertex-disjoint si no tienen ningún vértice en común.

ex. entrada

8 2 7
1 4
2 4
3 4
5 4
5 8
5 7
5 6

Answer 1

Ese es un problema de cobertura de vértices . Con la cubierta de vértice de un gráfico, las cabezas de cangrejo son vértices de una cubierta de vértice y los pies son vértices conectados a estas cabezas. Se deben quitar los pies duplicados, teniendo cuidado de no quitar todos los pies de un cangrejo :-)

Actualizar:

La tapa de vértice mínima es un NP-completo, lo que no es bueno :-) Creo que la cubierta de cangrejo es equivalente. Al menos tener un mínimo de cobertura de cangrejo podemos obtener una cobertura mínima de vértices. Entonces, si el cangrejo mínimo no está en NP-completo, entonces la cobertura mínima del vértice tampoco debería ser NP completa.

Demostremos que con un mínimo de cobertura de cangrejo podemos obtener una cobertura de vértice mínima. De manera estándar, obtenemos cobertura de vértice con cabezas de cangrejo. Supongamos, al contrario, que hay una cobertura de vértice de grado inferior, con menos vértices en cobertura que las cabezas de cangrejo. Para esa cubierta de vértice podemos construir una cubierta de cangrejo con el mismo grado, excepto que no estamos seguros si hay un cangrejo sin pie debido a la eliminación de los pies duplicados. Eso solo puede ser el caso si hay una cabeza con pies que se comparten con otras cabezas donde la otra cabeza no tiene otro pie. En ese caso, podemos construir una cobertura de vértice aún más pequeña quitando estas 2 cabezas y asentando la cabeza en ese pie crítico. Con eso tenemos una contradicción, por lo que no hay cobertura de vértices con menos vértices. Así que la cobertura mínima de cangrejo es también una cobertura mínima de vértices.

Answer 2

La solución del problema anterior mediante el enfoque de cobertura de vértices da como resultado un algoritmo de timbre exponencial, pero esto se puede resolver maximizando los flujos utilizando el algoritmo Ford Fulkerson. El problema anterior se puede resolver con el Ford Fulkerson.

1. Cree una ruta desde el origen (0) a todos los nodos del gráfico con capacidad = t.
2. Cree una ruta desde todos los nodos hasta el objetivo (1) con capacidad = 1.
3. Encuentre un flujo máximo del gráfico modificado anterior usando Ford Fulkerson.

Algoritmo de Ford Fulkerson para encontrar el flujo máximo en el gráfico dado

1. Encuentre un camino desde el origen hasta el objetivo en el gráfico.
2. Encuentra el flujo mínimo a lo largo de la ruta.
3. Aumenta el flujo de todos los bordes a lo largo de la ruta por flujo mínimo calculado anteriormente
4. Almacenar el flujo mínimo de la ruta.

Repita los 4 pasos anteriores hasta que no sea posible un camino de aumento.

Explicación para Ford Fulkerson Alogrithm

Elija un camino posible e identifique el borde con la capacidad más pequeña. Registre este número. Reste este número de cada número en esa ruta. Esta es la nueva capacidad para cada arco largo de la ruta. Elija otra ruta y repita el paso 1 una vez más, registre la capacidad más pequeña. Repita hasta que se agoten todas las rutas posibles. Agregue las capacidades más pequeñas de todas las rutas. Esta es la capacidad de carga mínima de la red

Referencia

http://anandtechblog.blogspot.in/search/label/Ford%20Fulkerson%20algorithm

Answer 3

Piense cómo se puede aplicar el flujo de red a este problema. Debería ser algo así como un flujo que pasa de la cabeza del cangrejo a sus pies. Y el flujo que llega a la cabeza debe tener un valor equivalente al número de pies y cada borde desde la cabeza hasta los pies del cangrejo debe tener una capacidad.

¿Cómo podemos lograr eso? Definitivamente es difícil llegar a esto por uno mismo, pero espero que después de ver el ejemplo varias veces, puedas aprender esto.

Tenemos que crear un nuevo gráfico donde los vértices originales estén duplicados. Un conjunto puede dar a cada vértice la oportunidad de ser cabeza y otro conjunto puede actuar como pies. Teniendo esto en cuenta, el algoritmo preciso se puede escribir de la siguiente manera:

1. We create a new graph where original vertices are duplicated (vertex i  becomes 2*i (head set) and 2*i+1  (feet set)    ).

2.For i and j vertices connected in original graph make sure that 2*i and 2*j+1 plus 2*j and 2*i+1 gets connected in new graph with capacity 1.

3.source vertex (S) is connected to each 2*i vertex(head set) with capacity min(T, degree).
4. Each 2*i+1(feet set) vertex is connected to target vertex (T) with capacity 1
5. Maxflow is the answer.

La siguiente imagen puede dar una idea decente de cómo se forma el gráfico. Nueva formación de gráficos

Explicación del punto 3: - cada vértice en el auricular debe estar conectado con la fuente con capacidad mínima (t, grado) porque si quisiéramos tener un flujo máximo en este borde para ser tan grande como T, no más que eso porque porque el cangrejo no puede tener más de t pies y el valor de la capacidad aquí también está limitado por el grado de vértice al que está conectado el 0. Una cabeza no puede tener más pies que su grado.

Explicación del punto 4: - Para asegurar que los pares estén separados para que cada vértice venga solo en un cangrejo, cada pie está conectado con la capacidad 1 al objetivo 10 en la figura.

Puedo publicar el código si es necesario.