|
|
back to boardWho can give me some hints? Posted by adrian 9 Oct 2010 18:38 I thought it for a long time,but I still do not know how to do it. Hint Posted by vgu 9 Oct 2010 20:36 1) If we know the degree of the vertices, we can determine: is such graph exist. 2) Write a full search. You will quickly find an answer. You can sent this code and get AC or look at the answer and found a pattern. Re: Hint Posted by svr 9 Oct 2010 22:11 1)Havel-Hakimi algorithm 2) Hypothesis(my): sequence n/2 n/2 ... 3 3 2 2 1 1 0 0 realizable for each n P.S. In timus there is a problem about full search: monkey aplly full search on keyboard. When it create theorem. Edited by author 09.10.2010 22:30 Re: Hint svr, your hypothesis is true. It's obvious if we draw the adjacency matrix of these graphs (for even N): N = 4: 0 0 0 1 0 0 1 1 0 1 0 0 1 1 0 0 N = 6: 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 1 1 0 0 1 0 0 0 0 1 1 0 0 0 1 1 1 0 0 0 N = 8: 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 0 0 0 0 1 1 1 1 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 |
|
|