11396  Claw Decomposition
Moderator: Board moderators

 New poster
 Posts: 10
 Joined: Sun Jan 20, 2008 8:19 am
11396  Claw Decomposition
I did not understand the define of claw.
so is the following graph a claw?
the first graph
1 2
1 3
1 4
4 5
4 6
the second graph
1 2
1 3
1 4
2 5
3 6
4 7
and can anyone give me some hint of the algorithm?
thx.
so is the following graph a claw?
the first graph
1 2
1 3
1 4
4 5
4 6
the second graph
1 2
1 3
1 4
2 5
3 6
4 7
and can anyone give me some hint of the algorithm?
thx.
Output:
Code: Select all
YES
YES
NO
NO
.
Although none of your graphs would appear in the testdata. because the problem statement says all graphs has only vertices of degree 3.
HINT: All vertices has degree 3. So, If a vertex is the center of a claw, what can we conclude about its neighbors? What about the neighbors of a vertex which is not the center of a claw?
NO
.
Although none of your graphs would appear in the testdata. because the problem statement says all graphs has only vertices of degree 3.
HINT: All vertices has degree 3. So, If a vertex is the center of a claw, what can we conclude about its neighbors? What about the neighbors of a vertex which is not the center of a claw?
Well, a program which gets accepted would output 'YES' for both graphs, but none of those graphs are eligible to appear in the testdata, and If their shape is not claw.DP wrote:Output:Code: Select all
YES YES

 New poster
 Posts: 10
 Joined: Sun Jan 20, 2008 8:19 am
thx.your hinit.Hadi wrote:NO
NO
.
Although none of your graphs would appear in the testdata. because the problem statement says all graphs has only vertices of degree 3.
HINT: All vertices has degree 3. So, If a vertex is the center of a claw, what can we conclude about its neighbors? What about the neighbors of a vertex which is not the center of a claw?
Re: 11396  Claw Decomposition
Oh man this question is so confusing. How do one even know that this is a bipartite graph problem?
Can someone try to explain the question a bit? like give an example of a valid graph
Can someone try to explain the question a bit? like give an example of a valid graph
Re: 11396  Claw Decomposition
I got accepted with a bipartite check algorithm, but I'm still rather unsure about the correctness of the algorithm. Logically, in order to prove that a solution exists iff the graph is bipartite, one would have to show that:
I) if the graph is bipartite, we can indeed construct a solution
II) if the graph is not bipartite, we cannot construct a solution
For I) (our graph is bipartite) , I came up with the following observations:
a) The center of a claw must have a degree 3.
b) (using the fact that a bipartite graph is 2 colourable)
It makes sense that the centers of the claws must all have the same colour in our colouring. (Let's say we find a center x with edges to y1, y2, y3. Now, if we eliminate the subgraph containing those edges, in the remaining graph y1, y2, y3 have degree < 3. Thus, by observation a), they can't be centers. The only nodes we can guarantee that they still have degree 3, are the ones with the same colour as x.
However, I can't figure out how one would construct a solution
For II (not a bipartite graph), the only observation I made was that:
 The graph contains an odd length cycle. Furthermore, given the construction of the colouring algorithm, there exists a cycle of length 3.
I'm not sure this is enough to prove that there isn't a solution.
Could anyone help me figure out how to prove this? Some intuitive proof would also help. Thank you in advance!
I) if the graph is bipartite, we can indeed construct a solution
II) if the graph is not bipartite, we cannot construct a solution
For I) (our graph is bipartite) , I came up with the following observations:
a) The center of a claw must have a degree 3.
b) (using the fact that a bipartite graph is 2 colourable)
It makes sense that the centers of the claws must all have the same colour in our colouring. (Let's say we find a center x with edges to y1, y2, y3. Now, if we eliminate the subgraph containing those edges, in the remaining graph y1, y2, y3 have degree < 3. Thus, by observation a), they can't be centers. The only nodes we can guarantee that they still have degree 3, are the ones with the same colour as x.
However, I can't figure out how one would construct a solution
For II (not a bipartite graph), the only observation I made was that:
 The graph contains an odd length cycle. Furthermore, given the construction of the colouring algorithm, there exists a cycle of length 3.
I'm not sure this is enough to prove that there isn't a solution.
Could anyone help me figure out how to prove this? Some intuitive proof would also help. Thank you in advance!
Wrong Answer : 11396  Claw Decomposition
Need Help I am getting Wrong Answer
My Logic: For every connected components there will two independents set of size 3 then answer will be YES
otherwise NO.
am i right?
My Logic: For every connected components there will two independents set of size 3 then answer will be YES
otherwise NO.
am i right?
Re: 11396  Claw Decomposition
This is my code for 11396Claw Decomposition. It shows wrong answer. Please give me some test cases in which my code fails.
http://pastebin.com/d0JAVYHx
http://pastebin.com/d0JAVYHx

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 11396  Claw Decomposition
bradd123, don't assume that the graph is connected.
Check input and AC output for thousands of problems on uDebug!
Re: 11396  Claw Decomposition
I also tried the bipartite check algorithm .
But it keeps showing me wrong answer ..
Here is my code ..
http://pastebin.com/FqQTasKs
Please Help...
But it keeps showing me wrong answer ..
Here is my code ..
http://pastebin.com/FqQTasKs
Please Help...