Igor.Ivanich's blog

Find a Hamiltonian Cycle when each vertex of the graph has degree >= N / 2
By Igor.Ivanich, 15 years ago, In English


Hi everyone,

I'm new to Codeforces, Seems a very nice place for training.
BTW, I'm trying to solve this problem
http://acm.sgu.ru/problem.php?contest=0&problem=122
I've search for the Dirac's Theorm which states that there is a hamiltonian cycle.
But how should I build the path?


Cheers


Igor

  • Vote: I like it
  • +11
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
15 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
What I did was to start from a complete graph and an arbitrary cycle like 1,2, ..., n. Then for each edge not in the original graph I deleted it and if it altered the cycle I repaired the cycle.
→ Reply
  • 15 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it
    Thanks for the response, Could u please explain more how do u update the cycle?
    → Reply
    • 15 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it
      Let the cycle you had be v1, v2, ..., vn and you have deleted edge between vn and v1. Now for each vertex put a candy on it if it's adjacent to v1 in the current graph. Also put a candy on vertex vi if vi - 1 is adjacent to vn. Because n ≤ deg(v1) + deg(vn) and there are n - 1 vertices capable of receiving candy you can prove by Pigeon Hole Principle (although its obvious) that there exists a vertex which has received two candies. Suppose vi has received 2 candies. This means that v1 is adjacent to vi and vi - 1 is adjacent to vn. So you can build a new Hamiltonian cycle like this: v1, v2, ..., vi - 1, vn, vn - 1, ..., vi, v1.
      → Reply