Crab graphics, algorithms, graph theory, how does this happen on the network?

Question

Can someone please help me with this problem? The solution apparently uses a network stream, but I'm not very familiar with the network stream. How does network flow help you solve this problem?

A crab is an undirected graph that has two types of vertices: 1 head and K feet and exactly K edges that connect the head to each of the legs. (1 <= K <= T, where T)

Given an undirected graph, you should find some vertex-disjoint subgraphs in it, where each of them is a crab. The goal is to select these crabs so that the total number of peaks covered by them is maximized.

Note: two graphs are non-intersecting vertices if they have no common vertex.

ex. entrance

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

Answer 1

Solving the above problem with the vertex method leads to the exponential tim algorithm, but this can be solved by maximizing flows using the Ford Fulkerson algorithm. Above, the problem can be solved using Ford Fulkerson.

• Create a path from source (0) to all nodes of the graph with capacity = t.
• Create a path from all nodes to target (1) with capacity = 1.
• Find the maximum flow of the above modified schedule using Ford Fulkerson.

Ford Fulkerson Algorithm for finding the maximum flow in a given chart

• Find the path from the source to the target on the graph.
• Find the minimum flow along the path.
• Increase the flow of all edges along the path by the minimum flow calculated above
• Keep the minimum flow of the path.

Repeat the above 4 steps until the enlargement path appears.

Explanation for Alogrithm Ford Fulkerson

Choose one possible path and determine the edge with the smallest capacity. Record this number. Highlight this number from each number along the way. This is a new ability for each arc in length. Select another route and repeat step 1 again to record the smallest capacity. Repeat until all possible paths have been exhausted. Add the smallest capacity of all routes. This is the minimum network bandwidth.

Link

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

Answer 2

Consider how you can apply network flow to this problem. It should be something like a stream going from the head of the crab to its legs. And the flow coming to the head should have a value equivalent to the number of legs, and each edge from the head to the legs of the crab should have a capacity of one.

How can we achieve this? It is definitely difficult to come to this on our own, but I hope that by seeing the example several times, you can hang it.

We need to create a new graph where the original vertices are duplicated. One set can give each vertex a chance to be a head, and another set can act like legs. With this in mind, the exact algorithm can be written like this: -

 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. 

The image below can give a decent idea of ​​how the graph is formed. Creating a new schedule

Explanation of paragraph 3: - each vertex in the headset must be connected to a source with a power of min (t, degree), because if we wanted the maximum flow on this edge to be as large as T, no more than that, that, since a crab cannot have more than t feet, and the cost of power here is also limited by the degree of the vertex to which it is connected 0. The head cannot have more legs than its degree.

Explanation of paragraph 4: - So that the pairs do not intersect, so that each vertex comes only on one crab, each leg is connected with a thickness of 1 to target 10 in the figure.

I can post the code if necessary.

Answer 3

This is a problem with the top . With a vertex-covered graph, the crab heads are the vertices of the vertex cover, and the feet are the vertices associated with these heads. Duplicated legs should be removed, while try not to remove all the legs of one crab :-)

Update:

The minimum vertex coverage is NP-complete, which is not nice :-) I think the crab lid is equivalent. At least with a minimum crab coverage, we can get a minimum vertex coverage. So, if the minimal crab is not NP-complete, then the minimal vertex coverage should also not be NP-complete.

Let us prove that with a minimal crab cover we can get a minimal vertex coverage. In the standard way, we get a vertex cover with crab heads. Assume the contrary that there is a vertex covering of a lower degree, with fewer vertices in the coating than the heads of crabs. For this vertex covering, we can construct a crab cover with the same degree, except that we are not sure if there is a crab without a leg due to the removal of duplicate legs. This may be the case if there is a head with legs that are shared with other heads, where each other head does not have another leg. In this case, we can build an even smaller vertex cover by removing these 2 heads and placing the head on this critical foot. We have a contradiction with this, therefore there is no vertex coverage with fewer vertices. Thus, the minimum crab cover is also the minimum apex cover.