Koenigsberg  Bridge  Problem

 

18¼¼±â µ¿(ÔÔ)ÇÁ·ÎÀ̼¾ÀÇ ¼öµµ Äê´ÏÈ÷½ºº£¸£Å© (ÇöÀçÀÇ Ä®¸®´Ñ±×¶óµå) ¿¡ ÀÖ´ø ÇÁ·¹°Ö°­(Ë°)ÀÇ ´Ù¸®°Ç³Ê±â¸¦ Á¦Àç·Î ÇÑ ÃʱâÀÇ À§»ó±âÇÏÇÐ ¹®Á¦ÀÌ´Ù.  Äê´ÏÈ÷½ºº£¸£Å©´Â ÇÁ·¹°Ö°­¿¡ ÀÇÇØ °ú °°ÀÌ A,B,C,DÀÇ 4Áö¿ªÀ¸·Î ³ª´©¾îÁö°í, À̵é Áö¿ªÀ» ÀÕ´Â 7°³ÀÇ ´Ù¸® a,b,c,d,e,f,g°¡ ³õ¿© ÀÖ¾ú´Ù. ±×·±µ¥ ÀÌ 7°³ÀÇ ´Ù¸®¿¡ ´ëÇØ ¡°°°Àº ´Ù¸®¸¦ µÎ ¹ø °Ç³Ê´Â ÀÏ ¾øÀÌ ÀÌµé ´Ù¸®¸¦ ¸ðµÎ °Ç³Ê¶ó¡±´Â ¹®Á¦°¡ ´©±º°¡¿¡ ÀÇÇØ ÃâÁ¦µÇ¾ú´Ù. ÀÌ°ÍÀº ¡®ÇѺױ׸®±â¡¯ÀÇ ¹®Á¦À̸ç, À§»ó±âÇÏÇÐÀÇ ±âÃÊÀûÀÎ ¹®Á¦·Î¼­ À¯¸íÇÏ´Ù ........ ÀÌ ¹®Á¦¿¡¼­ °¢ Áö¿ªÀ» Á¡À¸·Î, ´Ù¸®¸¦ ¼±À¸·Î ³ªÅ¸³»¾î Á¡ A,B,C,D´Â °¢ Áö¿ªÀÌ°í, ¼±Àº 7°³ÀÇ ´Ù¸®ÀÌ´Ù. Á¡ A¸¦ Ãâ¹ßÇÏ¿© ¼±À» µû¶ó ¿¬ÇÊÀ» ¶¼Áö ¾Ê°í ¾î´À ¼±µµ ÇÑ ¹ø¸¸ Áö³ªµµ·Ï ±×¸± ¼ö ÀÖ´Ù¸é, ÀÌ ¹®Á¦´Â ÇØ°áµÇ´Â ¼ÀÀÌ´Ù. ±×·¯³ª ÀÌ°ÍÀº ºÒ°¡´ÉÇÏ´Ù´Â °ÍÀÌ ½ºÀ§½ºÀÇ ¼öÇÐÀÚ L.¿ÀÀÏ·¯¿¡ ÀÇÇØ ¹àÇôÁ³´Ù. ........ (Äê´ÏÈ÷½ºº£¸£Å©ÀÇ ´Ù¸®°Ç³Ê±â ¹®Á¦ : Yahoo)

±×·¡ÇÁ ÀÌ·Ð (Graph Theory) ÀÇ Ã¹ ³í¹®Àº 1736 ³â ·¹¿À³ªµå ¿ÀÀÏ·¯ (Leonhard Euler) ÀÇ °ÍÀ̾ú´Ù. ±× ³í¹®Àº ÇöÀç Äê´Ð½ºº£¸£±× (Königsberg) ´Ù¸® ¹®Á¦¿¡ ´ëÇÑ ÇعýÀ» Æ÷ÇÔÇÑ ÀϹÝÀûÀÎ ±×·¡ÇÁ ÀÌ·ÐÀ» Á¦½ÃÇÏ¿´´Ù. Äê´Ð½ºº£¸£±× (Königsberg, Áö±Ý ·¯½Ã¾ÆÀÇ Ä®¸®´Ñ±×¶óµå) ¿¡ ÀÖ´Â ÇÁ·¹°Ö °­¿¡ ÀÖ´Â µÎ °³ÀÇ ¼¶ÀÌ ±×¸² 7 °ú °°ÀÌ ´Ù¸®¿¡ ÀÇÇØ °¢°¢ ¿¬°áµÇ¾î ÀÖ°í °­µÏµµ ´Ù¸®·Î ¿¬°áµÇ¾î ÀÖ´Ù. ¹®Á¦´Â ¾î¶² À§Ä¡ - A, B, C, ¶Ç´Â D - ¿¡¼­ Ãâ¹ßÇÏ¿© ; °¢°¢ÀÇ ´Ù¸®¸¦ ÇÑ ¹ø¸¸ °Ç³Ê¼­ ; Ãâ¹ßÁ¡À¸·Î µ¹¾Æ¿À´Â °ÍÀÌ´Ù.

±×¸² 7  Äê´Ð½ºº£¸£±× ´Ù¸®

±×¸² 8  Äê´Ð½ºº£¸£±× ´Ù¸®ÀÇ ±×·¡ÇÁ ¸ðµ¨

ÀÌ ´Ù¸®ÀÇ ±¸¼ºÀº ±×¸² 8 °ú °°ÀÌ ±×·¡ÇÁ·Î ¸ðµ¨È­ÇÒ ¼ö ÀÖ´Ù. Á¤Á¡Àº À§Ä¡¸¦ ³ªÅ¸³»°í °£¼±Àº ´Ù¸®¸¦ ³ªÅ¸³½´Ù. Äê´Ð½ºº£¸£±× ´Ù¸® ¹®Á¦´Â ±×¸² 8 ÀÇ ±×·¡ÇÁ¿¡¼­ ¸ðµç ¿¡Áö¿Í ¸ðµç Á¤Á¡ÀÌ ´Ù Æ÷ÇԵǾî ÀÖ´Â »çÀÌŬÀ» ã´Â ¹®Á¦·Î º¯ÇüµÈ´Ù. ¿ÀÀÏ·¯ÀÇ ¾÷ÀûÀ» ±â¸®¾î ±×·¡ÇÁ G ¾ÈÀÇ ¸ðµç Á¤Á¡°ú ¸ðµç ¿¡Áö°¡ Æ÷ÇԵǴ »çÀÌŬÀ» ¿ÀÀÏ·¯ »çÀÌŬ (Euler cycle) À̶ó ºÎ¸¥´Ù. ¼­·ÐÀÇ ³íÀǷκÎÅÍ, ±×¸² 8 ÀÇ ±×·¡ÇÁ ¾È¿¡´Â Á¤Á¡ A ¿¡ ºÎ¼ÓµÈ ¸ð¼­¸®¼±ÀÌ È¦¼öÀ̹ǷΠ¿ÀÀÏ·¯ »çÀÌŬÀº ¾ø´Ù (»ç½Ç, ±×¸² 8 ÀÇ ±×·¡ÇÁ¿¡¼­, ¸ðµç Á¤Á¡Àº Ȧ¼ö °³ÀÇ °£¼±ÀÌ ºÎ¼ÓµÇ¾î ÀÖ´Ù).

............ (°æ·Î¿Í »çÀÌŬ (Paths and Cycles) : Richard Johnsonbaugh)

term :

±×·¡ÇÁ ÀÌ·Ð (Graph Theory)   ¼øȸÆǸſø ¹®Á¦ (Traveling Salesman Problem)   ÇعÐÅÏÀÇ »çÀÌŬ ¹®Á¦ (Hamiltonian Cycle Problem)   Äê´ÏÈ÷½ºº£¸£Å©ÀÇ ´Ù¸®°Ç³Ê±â ¹®Á¦ (Koenigsberg Bridge Problem)

site :

Koenigsberg Bridge Problem

video :

2ȸ »ýÈ° ¼Ó ±âÇÏÇмöÇÐÀ¸·Î Ǫ´Â ¼¼»óÀÇ ºñ¹Ð - YTN »çÀ̾𽺠: ¹Ú°æ¹Ì ¼öÇнºÅ丮ÅÚ·¯ È«ÀÍ´ë±³¼ö, 2013/11/21...... µ¿¿µ»ó 19ºÐºÎÅÍ ¼³¸íÇÔ

 

¼¼±âÀÇ ¼öÇÐÀÚµé : ¼öÇÐÀ¸·Î Ǫ´Â ¼¼»óÀÇ ºñ¹Ð - YTN »çÀ̾ð½º: ¹Ú°æ¹Ì ¼öÇнºÅ丮ÅÚ·¯ È«ÀÍ´ë±³¼ö, 2014/06/18 .... µ¿¿µ»ó 14ºÐºÎÅÍ ¼³¸íÇÔ