mersenneforum.org Hamiltonian path
 Register FAQ Search Today's Posts Mark Forums Read

 2019-05-13, 09:33 #1 lukerichards     "Luke Richards" Jan 2018 Birmingham, UK 25×32 Posts Hamiltonian path Hi, One of my students gave me this problem this morning. I know very little about graph theory to know if it's possible. I'm enjoying puzzling through it at the moment so any solutions of proofs of impossibility, please cover with spoiler tags! Find a hamiltonian path* through the following network which starts at the point 'O': Code: x - x - x - x - x | | | | | x - x - x - x - x | | | | | x - x - x - x - x | | | | | x - x - x - x - x | | | | | x - x - x - O - x *must pass through every vertex ('x') exactly once.
2019-05-13, 10:06   #2
AKG

May 2019

22 Posts

Quote:
 Originally Posted by lukerichards Hi, One of my students gave me this problem this morning. I know very little about graph theory to know if it's possible. I'm enjoying puzzling through it at the moment so any solutions of proofs of impossibility, please cover with spoiler tags! Find a hamiltonian path* through the following network which starts at the point 'O': Code: x - x - x - x - x | | | | | x - x - x - x - x | | | | | x - x - x - x - x | | | | | x - x - x - x - x | | | | | x - x - x - O - x *must pass through every vertex ('x') exactly once.
you need parity argument.

Mark each x black and white like a a chessBoard (corner white preferably).
You have to start from a black square (total count 12), visit 13 white square and 11 black which is impossible.

Last fiddled with by henryzz on 2019-05-13 at 11:00

 2019-05-13, 10:34 #3 AKG   May 2019 22 Posts Tackle by parity, 13 white / 12 black. You start from black have to visit 13 white interspersed with 11 black. Not possible, Last fiddled with by henryzz on 2019-05-13 at 10:59
 2019-05-13, 10:59 #4 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 3·1,951 Posts @AKG Doesn't that only apply to cycles not paths? I have added spoilers so that others can solve.
 2019-05-13, 12:12 #5 AKG   May 2019 22 Posts That is condition, pass through 'x' only once. Answer is not concerned with which path or cycle you follow.
 2019-05-14, 01:54 #6 LaurV Romulan Interpreter     Jun 2011 Thailand 17×19×29 Posts This problem is similar to the Domino-Chess puzzle, which sucked tons of ink a century ago... All ladies from higher society used at a point in their life, at some party, to play placing dominoes on the chess board. Even nowadays, if you propose it as a social game at some party, plenty of people will argue for hours about placing dominoes on this or that direction. Try it! (be prepared with a chess board and a domino set hehe). Solving such problems by backtrack (the natural way the human mind thinks) has exponential complexity. For just a little bigger board you will need thousands of years. Unless you see the parity trick. (Yeah, I read the spoilers above, but I knew the problem and the solution long before, Graph Theory was one of my strongest points in school, we - as a group of about 10 students - and our professor did few important steps in proving the infamous (at the time) Berge's conjecture (now it is known as the "strong perfect graph theorem"). Which, I believe, it is an important step in proving that P=NP. No joke, talk to you about this in about 50 years... Last fiddled with by LaurV on 2019-05-14 at 02:04

 Similar Threads Thread Thread Starter Forum Replies Last Post a1call Puzzles 23 2016-03-23 17:46 henryzz Puzzles 13 2014-09-17 11:21 emily Hardware 20 2012-03-02 08:45 davar55 Puzzles 12 2008-02-26 21:53 jocelynl Soap Box 14 2003-09-22 20:38

All times are UTC. The time now is 01:20.

Mon Apr 12 01:20:07 UTC 2021 up 3 days, 20:01, 1 user, load averages: 1.78, 1.56, 1.51