Hamiltonian  Cycle  Problem

  

William Rowan Hamilton °æÀº 1800 ³â Áß¹Ý 12 ¸éüÀÇ ¸ð¾ç¿¡¼­ ¼ö¼ö²²³¢ Çϳª¸¦ Á¦½ÃÇß´Ù (±×¸² 1). °¢ ²ÀÁöÁ¡¿¡ µµ½Ã À̸§À» ÁÖ°í, ¹®Á¦´Â ¾î¶² µµ½Ã¿¡¼­ Ãâ¹ßÇÏ¿©, °£¼±µéÀ» µû¶ó¼­ ÇÑ µµ½Ã¸¦ Çѹø¸¸ ¹æ¹®ÇÏ¿©, ÃÖÃÊÀÇ Ãâ¹ß µµ½Ã·Î µ¹¾Æ¿À´Â °ÍÀÌ´Ù. 12 ¸éüÀÇ °£¼±ÀÇ ±×·¡ÇÁ´Â ±×¸² 2 ¿¡ ÁÖ¾îÁ® ÀÖ´Ù. ÇعÐÅÏÀÇ ¼ö¼ö²²³¢¸¦ ±×¸² 2 ÀÇ ±×·¡ÇÁ¿¡¼­ »çÀÌŬÀ» ãÀ» ¼ö ÀÖ´Ù¸é ¹®Á¦´Â ÇØ°áµÈ´Ù. ´Ù¸¸ °¢ Á¤Á¡Àº ÇÑ ¹ø¸¸ Æ÷ÇԵǾî¾ß ÇÑ´Ù (Ãâ¹ßÁ¡°ú ³¡³ª´Â Á¡Àº µÎ ¹ø ³ªÅ¸³ª´Â °ÍÀ» Á¦¿ÜÇÏ°í). ±×¸² 3 Àº ±× ÇØÀÌ´Ù.

±×¸² 1  ÇعÐÅÏ ÆÛÁñ

±×¸² 2  ÇعÐÅÏ ÆÛÁñÀÇ ±×·¡ÇÁ

±×¸² 3  ±×¸² 2 ÀÇ ±×·¡ÇÁ¿¡¼­ °¢ Á¤Á¡ÀÌ Çѹø¸¸ ¹æ¹®ÇÑ´Ù.

ÇعÐÅÏÀÇ ¾÷ÀûÀ» ±â¸®¾î, ÁÖ¾îÁø ±×·¡ÇÁ¿¡¼­ Ãâ¹ßÁ¡°ú Á¾·áÁ¡¸¸ µÎ ¹ø ³ªÅ¸³ª´Â °ÍÀ» Á¦¿ÜÇÏ°í´Â Á¤Á¡ÀÌ ÇÑ ¹ø¾¿¸¸ ³ªÅ¸³ª´Â »çÀÌŬÀ» ÇعÐÅÏ »çÀÌŬ (Hamiltonian cycle) À̶ó ÇÑ´Ù. ............ (ÇعÐÅÏ »çÀÌŬ°ú ÆǸſø ¹æ¹® ¹®Á¦ (Hamiltonian Cycles and the Travelling Salesperson Problem) : Richard Johnsonbaugh)

ÇعÐÅÏ (1805~1865) Àº ¾ÆÀÏ·£µåÀÇ ´ëÇÐÀÚ¿´´Ù. ±×´Â µàºê¸° ´ëÇÐÀÇ Ãµ¹®ÇÐ ±³¼ö¿´°í, ¹°¸®Çаú ¼öÇÐ ºÐ¾ß¿¡¼­ ¸¹Àº ³í¹®µéÀ» ÁýÇÊÇß´Ù. ¼öÇÐ ºÐ¾ß¿¡¼­, ÇعÐÅÏÀº »ç¿ø¹ý (quaternions) ÀÇ ¹ß¸í, ½Ç¼ö ü°èÀÇ ÀϹÝÈ­·Î ¸Å¿ì À¯¸íÇÏ´Ù. ±×ÀÇ »ç¿ø¹ýÀº Çö´ë Ãß»ó ´ë¼öÀÇ ¹ßÀü¿¡ ¿µ°¨À» ÁÖ¾ú´Ù. ÇعÐÅÏÀº º¤ÅÍ ¿ë¾î¸¦ µµÀÔÇß´Ù

term :

±×·¡ÇÁÀÌ·Ð (Graph Theory)   ¼øȸÆǸſø ¹®Á¦ (Traveling Salesman Problem)   William Rowan Hamilton

site :

The Hamiltonian Page  : Hamiltonian cycle and path problems ¿¡ °üÇÑ ¸¹Àº ÀÚ·á

Hamiltonian Cycle Problem  : Hamiltonian cycle problemÀ» Ç®±âÀ§ÇÑ source code hamilton.c