We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Problem Definition
A crab is an undirected graph which has two kinds of vertices: 1 head, and K feet , and exactly K edges which join the head to each of the feet.( 1≤K≤T , where T is given)
Given an undirected graph, you have to find in it some vertex-disjoint subgraphs where each one is a crab. The goal is to select those crabs in such a way that the total number of vertices covered by them is maximized.
Algorithm
First above, we put forward an algorithm that gives the answer of this tricky question. We will prove its property later. The algorithm states as below.
We have the original diagram as shown in Fig.1(There are only four nodes for simplicity)
We transform the picture into the one below by expanding the i^th node to the node pair of 〖2i〗^th,〖2i+1〗^th. And the edges of that crab between node (i,j) is now transformed into the edges of (2i,2j+1),(2j,2i+1), we set the capacity as 1.
Then we add the Sender and Receiver nodes. We set the capacity from Sender to 2i as T, and we set the capacity from 2i+1 to Receiver as 1.
Here we compute this max-flow problem and get the answer.
Proof.
Before proofing, we set some rules for easier illustration.
We denote the answer of the crab problem as Crab Answer, and call the answer of the max-flow problem as the Max-Flow Answer.
In fact, both question may have several different answers (in the combinatory sense), but in fact any of them only have one answer as the consequence, which is no more than a number, S.
What we want to do is to prove that given a Crab Answer, we can construct from it a Max-Flow answer, so that we can prove these two question have the same consequence S.
In order to prove this claim, we know that we should have a Crab Answer first. For example, in Fig3. We have got the Crab Answer. We know the Crab Answer has the following properties:
The head is connected to several legs and the number of legs won’t surpass K.
The different crabs do not share any nodes.
The number of vertices is maximized.
We will use these properties in the following proof.
However, we can change it into an available flow solution like in Fig4. The construction of an available flow solution goes like this:
For each crab, we let the flow from its head to its legs.
We also choose a flow from one of its legs to its head.
We will let the according flow from Sender to the heads, and those from the heads and legs to the Receiver.
Since the crabs are vertex-disjoint and the leg number can be no less than 1, so it is always effective.
Now we’ve constructed an available flow, and for the first constraint of a Crab Answer, the flow from Sender to any of the 2i node won’t exceed K. So the flow constraint is well obeyed.
In this way, we proved that, the Crab Answer will get a sequence CC no more than the Max-Flow Answer FC, since an available answer will never exceed the maximum answer. CC≤FC.
Then we will prove the Max-Flow Answer also will not exceed the Crab Answer. FC≤CC. In this proof, we will use the third constraint of the Crab Answer.
In fact, the available flow we’ve constructed above will always be a valid flow. And more insight into it will also prove that it is also a max flow.
In order to prove this, we will use the conclusion that Largest flow, FC is equal to the Smallest cut, SC. So we want to prove that this available flow is also a cut. If we’ve proved that the available flow is a cut, then we have CC≥AC=FC.
Suppose it is not a cut, then there should exist a path between the Sender and Receiver, we denote this path as S→2i→2j+1→R, and this path do not include any path that’s already used. Using the constraint of Crab Answer, we know that the node of 2j+1 won’t be head or leg, the paths from heads or legs to the Receive are all already used. So2j+1 should be a blank node.
Then the node of 2i can only be three kinds of vertices.
Blank node
In this way, there exists a path between two blank nodes, which is not acceptable because this disobeys the third constraint of Crab Answer.
Leg node
In this case, if number of legs≥2, then no matter if the leg node is connected to the second layer head node or not, we can always get it disconnected from that node by using other leg nodes to connect the second layer header node if needed Then we can detach the leg and form a new crab of this leg node and blank node, which disobeys the third law of Crab Answer.
However, if number of legs=1, then we can call either of the two nodes as head, and the new blank node can also be included, which disobeys the third law of a Crab Answer.
Head node
In this case, in order to make sure the path won’t counteract with that from the S to 2i, the legs of that header shouldn’t have been fully occupied, in this way, we can add the blank node as the header’s legs, which also disobeyed the third law of a Crab Answer.
In this sense, we know that the Crab Answer can be transformed into a Cut, which guarantees that CC≥FC, and in 1), we’ve got CC≤FC. So CC=FC.
In this way, we know that the crab consequence is the same with the max-flow consequence.
Codes (in C++)
include
include
using namespace std;
const int Maxn=300;
int pre[Maxn];
int v[Maxn];
int g[Maxn][Maxn];
int f[Maxn][Maxn];
int min(const int val1,const int val2)
{
return val1
}
int maxFlow()
{
for(int i=0;i
{
for(int i=0;i que;
pre[s]=s;
v[s]=0x7fffffff;
que.push(s);
while(!que.empty())
{
queTop=que.front();
que.pop();
for(int i=0;i
{
if(pre[i]<0)
{
if(g[queTop][i]>f[queTop][i])
{
v[i]=min(g[queTop][i]-f[queTop][i],v[queTop]);
pre[i]=queTop;
que.push(i);
Crab Graphs
You are viewing a single comment's thread. Return to all comments →
Theoretical Analysis of the Crab Problem
Problem Definition A crab is an undirected graph which has two kinds of vertices: 1 head, and K feet , and exactly K edges which join the head to each of the feet.( 1≤K≤T , where T is given) Given an undirected graph, you have to find in it some vertex-disjoint subgraphs where each one is a crab. The goal is to select those crabs in such a way that the total number of vertices covered by them is maximized.
Algorithm First above, we put forward an algorithm that gives the answer of this tricky question. We will prove its property later. The algorithm states as below. We have the original diagram as shown in Fig.1(There are only four nodes for simplicity) We transform the picture into the one below by expanding the i^th node to the node pair of 〖2i〗^th,〖2i+1〗^th. And the edges of that crab between node (i,j) is now transformed into the edges of (2i,2j+1),(2j,2i+1), we set the capacity as 1. Then we add the Sender and Receiver nodes. We set the capacity from Sender to 2i as T, and we set the capacity from 2i+1 to Receiver as 1. Here we compute this max-flow problem and get the answer.
Proof. Before proofing, we set some rules for easier illustration. We denote the answer of the crab problem as Crab Answer, and call the answer of the max-flow problem as the Max-Flow Answer. In fact, both question may have several different answers (in the combinatory sense), but in fact any of them only have one answer as the consequence, which is no more than a number, S. What we want to do is to prove that given a Crab Answer, we can construct from it a Max-Flow answer, so that we can prove these two question have the same consequence S. In order to prove this claim, we know that we should have a Crab Answer first. For example, in Fig3. We have got the Crab Answer. We know the Crab Answer has the following properties: The head is connected to several legs and the number of legs won’t surpass K. The different crabs do not share any nodes. The number of vertices is maximized.
We will use these properties in the following proof. However, we can change it into an available flow solution like in Fig4. The construction of an available flow solution goes like this: For each crab, we let the flow from its head to its legs. We also choose a flow from one of its legs to its head. We will let the according flow from Sender to the heads, and those from the heads and legs to the Receiver.
Since the crabs are vertex-disjoint and the leg number can be no less than 1, so it is always effective.
Now we’ve constructed an available flow, and for the first constraint of a Crab Answer, the flow from Sender to any of the 2i node won’t exceed K. So the flow constraint is well obeyed.
In this way, we proved that, the Crab Answer will get a sequence CC no more than the Max-Flow Answer FC, since an available answer will never exceed the maximum answer. CC≤FC.
In fact, the available flow we’ve constructed above will always be a valid flow. And more insight into it will also prove that it is also a max flow.
In order to prove this, we will use the conclusion that Largest flow, FC is equal to the Smallest cut, SC. So we want to prove that this available flow is also a cut. If we’ve proved that the available flow is a cut, then we have CC≥AC=FC.
Suppose it is not a cut, then there should exist a path between the Sender and Receiver, we denote this path as S→2i→2j+1→R, and this path do not include any path that’s already used. Using the constraint of Crab Answer, we know that the node of 2j+1 won’t be head or leg, the paths from heads or legs to the Receive are all already used. So2j+1 should be a blank node.
Then the node of 2i can only be three kinds of vertices. Blank node In this way, there exists a path between two blank nodes, which is not acceptable because this disobeys the third constraint of Crab Answer. Leg node In this case, if number of legs≥2, then no matter if the leg node is connected to the second layer head node or not, we can always get it disconnected from that node by using other leg nodes to connect the second layer header node if needed Then we can detach the leg and form a new crab of this leg node and blank node, which disobeys the third law of Crab Answer. However, if number of legs=1, then we can call either of the two nodes as head, and the new blank node can also be included, which disobeys the third law of a Crab Answer. Head node In this case, in order to make sure the path won’t counteract with that from the S to 2i, the legs of that header shouldn’t have been fully occupied, in this way, we can add the blank node as the header’s legs, which also disobeyed the third law of a Crab Answer. In this sense, we know that the Crab Answer can be transformed into a Cut, which guarantees that CC≥FC, and in 1), we’ve got CC≤FC. So CC=FC.
In this way, we know that the crab consequence is the same with the max-flow consequence.
Codes (in C++)
include
include
using namespace std;
const int Maxn=300; int pre[Maxn]; int v[Maxn]; int g[Maxn][Maxn]; int f[Maxn][Maxn];
int min(const int val1,const int val2)
{
return val1 }
int maxFlow()
{
for(int i=0;i {
for(int i=0;i que;
pre[s]=s;
v[s]=0x7fffffff; que.push(s);
while(!que.empty())
{
queTop=que.front();
que.pop();
for(int i=0;i {
if(pre[i]<0) {
if(g[queTop][i]>f[queTop][i])
{
v[i]=min(g[queTop][i]-f[queTop][i],v[queTop]); pre[i]=queTop; que.push(i);
}
int main()
{
int C; cin >> C; for(int i=0;i