ͽ¹ð¤·¤¿¡Ö¶ËÂçÍ×ÁǤθºß: ¾ÃÈñ¼ÔÍýÏÀ¤è¤ê´Êñ¡×¤«¤é¥¿¥¤¥È¥ë¤òÊѹ¹¤·¤¿¡¥¡Ö¥Ù¥¹¥È¡¦¥¨¥ì¥á¥ó¥È¤Î¸ºß: Èþ¿Í¥Û¡¼¥ë¤òµá¤á¤Æ¡×¤Ê¤É¤â¹Í¤¨¤¿¤¬¤ä¤á¤¿¡¥¤Ç¤¤ì¤ÐÄù¤Þ¤ê¤¬¤¤¤¤¤Û¤¦¤¬¤è¤¤¤Î¤À¤¬¡¤¤É¤ì¤¬Äù¤Þ¤ê¤¬¤¤¤¤¤À¤í¤¦¡¥ Á°²ó¤Îµ»ö¡ÖÁª¹¥¡×¤Ç¤Ï¡¤ÆüËܸì¤Îʸ¡Ö¤½¤Î¸Ä¿Í¤ÏÁªÂò»è x ¤òÁªÂò»è y ¤è¤ê¤â¹¥¤à¡×¤ò xPy ¤Èµ¹æ²½¤·¤¿¡¥Ã±¤Ëµ¹æ²½¤·¤¿¤À¤±¤Ç¤Ï¡¤¤â¤È¤Îʸ¤Î°ÕÌ£¤¬È´¤±Íî¤Á¤Æ¤·¤Þ¤¦¡¥¤À¤«¤é¡¤°ÕÌ£¤òºÆ¸½¤¹¤ë¤¿¤á¤Ëµ¹æ²½¤µ¤ì¤¿¤â¤Î¤Ë²þ¤á¤Æ¾ò·ï¤ò²Ý¤¹É¬Íפ¬½Ð¤ÆÍè¤ë¡¥Áª¹¥ P ¤Ë¤É¤ó¤Ê¾ò·ï¤ò²Ý¤»¤Ð¡¤xPy ¤È¤¤¤¦É½¸½¤¬¡Ö¤½¤Î¸Ä¿Í¤ÏÁªÂò»è x ¤òÁªÂò»è y ¤è¤ê¤â¹¥¤à¡×¤È¤¤¤¦°ÕÌ£¤ò¤¸¤å¤¦¤Ö¤óª¤¨¤ë¤³¤È¤¬¤Ç¤¤ë¤À¤í¤¦¤«¡©¡¡Îã¤È¤·¤Æ¡Ô¿ä°ÜÀ (transitivity)¡Õ¤ò¹Í¤¨¤Æ¤ß¤ë: Ǥ°Õ¤ÎÁªÂò»è x, y, z ¤Ë¤Ä¤¤¤Æ¡¤¡Ö¤â¤· xPy ¤È yPz ¤¬À®¤êΩ¤Æ¤Ð¡¤xPz ¤¬À®¤êΩ¤Ä¡×¤³¤È¤òÍ׵᤹¤ë¤Î¤À¡¥¤Ä¤Þ¤ê¡Öx ¤¬ y ¤è¤ê¡¤¤½¤·¤Æ y ¤¬ z ¤è¤ê¤â¹¥¤Þ¤·¤¤¤Î¤Ê¤é¤Ð¡¤x ¤¬ z ¤è¤ê¹¥¤Þ¤·¤¤¤È¼«Æ°Åª¤Ë¸À¤¨¤ë¤è¤Í¡×¤È¤¤¤¦¤ï¤±¤À¡¥Áª¹¥¤¬¤¿¤È¤¨¤Ð¿ä°ÜŪ¤Ç¤¢¤ë¤È²¾Äꤹ¤ë¤Î¤Ï¡¤¤¿¤ó¤Ë¡Ö¤è¤ê¹¥¤à¡×¤È¤¤¤¦¸ÀÍÕ¤ÎÄ̾ï¤Î°ÕÌ£¤òÈ¿±Ç¤µ¤»¤ë¤³¤È¤òͤ¨¤Æ¡¤¤½¤Î¸ÀÍդλȤ¤Êý¤ò¤è¤ê¸ÂÄꡦÌÀ³Î²½¤·¤Æ¤¤¤ë¤È¤â¸À¤¨¤ë¡¥(¡Ö¤è¤ê¹¥¤à¡×¤¬¿ä°ÜÀ¤ò¤ß¤¿¤µ¤Ê¤¯¤Æ¤âÊ¿µ¤¤Ç¤½¤Î¸ÀÍÕ¤ò»È¤¦¤Ò¤È¤â¤¤¤ë¤À¤í¤¦¤«¤é¡¥)¡Ö¤è¤ê¹¥¤à¡×¤È¤¤¤¦¸ÀÍÕ¤Ç x ÂÐ y ¤½¤·¤Æ y ÂÐ z ¤ò½ç½øÉÕ¤±¤·¤Æ¤ª¤¤Ê¤¬¤é x ÂÐ z ¤Î½ç½øÉÕ¤±¤¬¤Ç¤¤Ê¤¤¤³¤È¤Ï¤½¤Î¸ÀÍդλȤ¤Êý¤È¤·¤Æ¤ª¤«¤·¤¤¤È¤¤¤Ã¤Æ¤¤¤ë¤³¤È¤Ë¤Ê¤ë¤«¤é¡¥¤½¤¦¤¹¤ë¤³¤È¤Ë¤è¤ê¡¤¤½¤Î¸ÀÍÕ¤òȯ¤¹¤ë¼çÂΤǤ¢¤ë¸Ä¿Í¤Î»×¹Í¤Ë°ìÄê¤Î¥Ñ¥¿¥ó¤òÁÛÄꤷ¤Æ¤¤¤ë¤È¤â¤¤¤¨¤ë¡¥
¤À¤¬¤³¤³¤Ç¤Ï¡¤¿ä°ÜÀ¤è¤ê¤â¼å¤¤¡ÔÈó½Û´ÄÀ (acyclicity)¡Õ¤È¤¤¤¦¾ò·ï¤ò¹Í¤¨¤¿¤¤¡¥¤³¤ì¤Ï¡Ö¥µ¥¤¥¯¥ë¤òºî¤é¤Ê¤¤¡×¤È¤¤¤¦°ÕÌ£¤À¡¥¤¿¤È¤¨¤ÐÁªÂò»è x, y, z ¤¬¤¢¤Ã¤Æ xPy, yPz, zPx ¤È¤Ê¤Ã¤Æ¤¤¤ë¤È¤¡¤ÁªÂò»èÎó (x, y, z) ¤Ï¡Ô¥µ¥¤¥¯¥ë¡Õ¤Ç¤¢¤ë¤È¤¤¤¦¡¥x ¤¬ y ¤è¤ê¹¥¤¤Ç y ¤¬ z ¤è¤ê¹¥¤¤Ê¤Î¤Ë¡¤z ¤¬ x ¤è¤ê¹¥¤¤È¸À¤Ã¤Æ¤¤¤ë¤ï¤±¤Ç¡¤¤¤¤ï¤Ð¡Ö¤è¤ê¹¥¤¡×¤ÎÌð°õ¤¬½ä¤ê½ä¤Ã¤Æ¤â¤È¤ËÌá¤Ã¤ÆÍè¤Æ¤¤¤ë¤ï¤±¤À (±ß¼þ¾å¤Ë x, y, z ¤¬Ê¤ó¤Ç¡¤x¢ªy¢ªz¢ªx ¤ÎÌð°õ¤¬Ï¢¤Ê¤Ã¤Æ¤¤¤ë¤Î¤ò¥¤¥á¡¼¥¸¤»¤è)¡¥°ìÈÌŪ¤Ë¤Ï¡¤P ¤Ë¤ª¤±¤ë¡Ô¥µ¥¤¥¯¥ë¡Õ¤È¤Ï (¤¢¤ë͸¤ʿô) k ¸Ä¤ÎÁªÂò»è¤ÎÎó (x1, x2, ..., xk) ¤Ç¤¢¤Ã¤Æ¡¤x1Px2, x2Px3, ..., xk-1Pxk, ¤«¤Ä xkPx1 ¤È¤Ê¤ë¤â¤Î¤ÈÄêµÁ¤µ¤ì¤ë¡¥¤½¤·¤Æ¡¤Áª¹¥ P ¤¬¤¤¤«¤Ê¤ë¥µ¥¤¥¯¥ë¤â¤Õ¤¯¤Þ¤Ê¤¤¤È¤¡¤P ¤Ï¡ÔÈó½Û´ÄŪ¡Õ¤È¤¤¤¦¡¥(¥Æ¥¥¹¥È¤Ë¤è¤Ã¤Æ¤Ï¡¤P ¤¬¤¤¤«¤Ê¤ë¥µ¥¤¥¯¥ë¤â¤Õ¤¯¤Þ¤Ê¤¤¤È¤¡¤R ¤òÈó½Û´ÄŪ¤ÈÄêµÁ¤¹¤ë¡¥¤¿¤À¤· xRy ¤È¤Ï not yPx ¤Î¤³¤È¤Ç¤¢¤ë¡¥)
ÁªÂò»è¤Î½¸¹ç S ¤Î¡Ö¥Ù¥¹¥È¤ÊÍ×ÁǡפȤϤʤˤ«¡¤¤¤Á¤ó¤ÈÄêµÁ¤·¤è¤¦¡¥¤¢¤ëÁªÂò»è¤Î½¸¹ç S ¤Ë°¤¹¤ëÁªÂò»è x ¤¬Áª¹¥ P ¤Ë¤Ä¤¤¤Æ¤Î S ¤Î¡Ô¶ËÂçÍ×ÁǡդǤ¢¤ë¤È¤Ï¡¤yPx ¤È¤Ê¤ë¤è¤¦¤Ê S ¤Ë°¤¹¤ëÁªÂò»è y ¤¬Â¸ºß¤·¤Ê¤¤¤³¤È (¸À¤¤´¹¤¨¤ì¤Ð¡¤S ¤ÎǤ°Õ¤ÎÍ×ÁÇ y ¤Ë¤¿¤¤¤·¤Æ¡¤not yPx ¤¬¤Ê¤ê¤¿¤Ä¡¤¤¹¤Ê¤ï¤Á xRy ¤È¤Ê¤ë¤³¤È) ¤Ç¤¢¤ë¡¥x ¤è¤ê¹¥¤Þ¤·¤¤¤â¤Î¤¬Â¸ºß¤·¤Ê¤¤¤È¤¤¤¦¤ï¤±¤À¡¥x ¤¬ P ¤Ë¤Ä¤¤¤Æ (S ¤Î) ¶ËÂçÍ×ÁǤΤȤ¡¤x ¤Ï R ¤Ë¤Ä¤¤¤Æ¡ÔºÇÂçÍ×ÁǡդȸÀ¤¨¤ë; ¤½¤ÎÍýͳ¤ÏÌÀ¤é¤«¤À¤í¤¦¡¥ ¤À¤¤¤ÖÁ°ÃÖ¤¤¬Ä¹¤¯¤Ê¤Ã¤Æ¤·¤Þ¤Ã¤¿¡¥¥¢¥¸¥§¥ó¥À S ¤È¤ÏÁªÂò»è½¸¹ç X ¤ÎǤ°Õ¤Î¡Ö͸¤ʡ×Éôʬ½¸¹ç¤À¤Ã¤¿¡¥Ç¤°Õ¤Î¥¢¥¸¥§¥ó¥À¤¬¡Ö¥Ù¥¹¥È¡×¤ÊÁªÂò»è (Áª¹¥¤Ë¤«¤ó¤¹¤ë¶ËÂçÍ×ÁÇ) ¤ò»ý¤Ä¤«¤É¤¦¤«¤¬¤ï¤ì¤ï¤ì¤Î´Ø¿´¤À¤Ã¤¿¡¥¤¸¤Ä¤Ï¡¤¡ÖǤ°Õ¤Î¥¢¥¸¥§¥ó¥À S ¤¬ P ¤Ë¤Ä¤¤¤Æ¶ËÂçÍ×ÁǤò»ý¤Ä¤¿¤á¤ÎɬÍ×½½Ê¬¾ò·ï¤Ï¡¤P ¤¬Èó½Û´ÄŪ¤Ê¤³¤È¤Ç¤¢¤ë¡×¤È¤¤¤¦ÄêÍý¤¬À®Î©¤¹¤ë¡¥
¾ÃÈñ¼ÔÍýÏÀ¤Ë¤ª¤±¤ëºÇÂç²½¤Î´ðÁäòÍý²ò¤¹¤ë (¥È¥Ý¥í¥¸¡¼¤Î³µÇ°¤ÎÍý²ò¤¬Í׵ᤵ¤ì¤ë) ¤Î¤Ë¤¯¤é¤Ù¤ì¤Ð¡¤¤³¤ÎÄêÍý¤Î¾ÚÌÀ¤Ï´Êñ¤À¡¥¥¢¥¸¥§¥ó¥À¤ÏÁªÂòÂоݤò͸¸Ĥ·¤«¤â¤¿¤Ê¤¤¤¿¤á¤À¡¥¾Ü¤·¤¯¤ÏÀâÌÀ¤·¤Ê¤¤¤¬¡¤¡Ö·ê¡×(¤¢¤ë¤¤¤Ï¡ÖÁãÈ¢¡×) ¤Ë¡ÖƦ¡×(¤¢¤ë¤¤¤Ï¡ÖÈ·¡×) ¤òÆþ¤ì¤Æ¹Ô¤¯¡¤¤¢¤Î¡ÖÈ·¤ÎÁ㸶Íý¡×¤¬°ÅÌö¤·¤Æ¤¤¤ë¤Î¤À¡¥ ¤Þ¤º P ¤ÎÈó½Û´ÄÀ¤¬É¬Í×¾ò·ï¤Ç¤¢¤ë¤³¤È¡¤¤Ä¤Þ¤ê¡Ö¤É¤ó¤Ê¥¢¥¸¥§¥ó¥À S ¤Ç¤â¶ËÂçÍ×ÁǤò»ý¤Ä¤Ê¤é¤Ð¡¤P ¤¬Èó½Û´ÄŪ¤Ç¤¢¤ë¡×¤³¤È¤ò¡¤Âжö¤Ç¤¢¤ë¡ÖP ¤¬Èó½Û´ÄŪ¤Ç¤Ê¤±¤ì¤Ð¡¤¤¢¤ë¥¢¥¸¥§¥ó¥À S ¤Ï¶ËÂçÍ×ÁǤò»ý¤¿¤Ê¤¤¡×¤ò¼¨¤¹¤³¤È¤Ë¤è¤ê¾ÚÌÀ¤·¤è¤¦¡¥P ¤¬¥µ¥¤¥¯¥ë (x1, x2, ..., xk) ¤ò»ý¤Ä¤È¤¹¤ë¡¥¤¹¤ë¤È¡¤x1Px2, x2Px3, ..., xk-1Pxk ¤«¤é¡¤x1 ¤À¤±¤¬¶ËÂçÍ×ÁǤθõÊä¤È¤·¤Æ»Ä¤ë¡¥¤È¤³¤í¤¬ xkPx1 ¤«¤é¡¤x1 ¤â¶ËÂçÍ×ÁǤˤʤêÆÀ¤Ê¤¤¡¥¤è¤Ã¤Æ¡¤½¸¹ç S={x1, x2, ..., xk} ¾å¤Ë¶ËÂçÍ×ÁǤϸºß¤·¤Ê¤¤¡¥ ¼¡¤Ë P ¤ÎÈó½Û´ÄÀ¤¬½½Ê¬¾ò·ï¤Ç¤¢¤ë¤³¤È¡¤¤Ä¤Þ¤ê¡ÖP ¤¬Èó½Û´ÄŪ¤Ê¤é¡¤¤«¤Ê¤é¤º S ¤Ï¶ËÂçÍ×ÁǤò»ý¤Ä¡×¤³¤È¤Î¾ÚÌÀ¤ò¥¹¥±¥Ã¥Á¤·¤Æ¤ß¤è¤¦¡¥¤³¤ì¤âÂжö¡Ö¤¢¤ë S ¤¬¶ËÂçÍ×ÁǤò»ý¤¿¤Ê¤¤¤Ê¤é¤Ð¡¤P ¤ÏÈó½Û´ÄŪ¤Ç¤Ï¤Ê¤¤¡×¤ò¤·¤á¤¹¤³¤È¤Ë¤è¤ê¾ÚÌÀ¤¹¤ë¡¥S ¤¬¶ËÂçÍ×ÁǤò»ý¤¿¤Ê¤¤¤È¤¹¤ë¡¥¤Ä¤Þ¤ê¡¤S ¤Î¤É¤ó¤ÊÍ×ÁÇ x ¤Ë¤¿¤¤¤·¤Æ¤â x ¤è¤ê¹¥¤Þ¤·¤¤ (S ¤Î) ¤Ù¤Ä¤ÎÍ×ÁÇ y ¤¬Â¸ºß¤¹¤ë (yPx ¤È¤Ê¤ë)¡¥¤¤¤ÞǤ°Õ¤ÎÍ×ÁÇ x1¤ò¸ÇÄꤹ¤ë¤È¡¤¤½¤ì¤è¤ê¹¥¤Þ¤·¤¤ x2¡¤¤µ¤é¤Ë¤½¤ì¤è¤ê¹¥¤Þ¤·¤¤ x3¡¤¡Ä¡Ä¤È¤¤¤¦¶ñ¹ç¤Ë¤º¤Ã¤È S ¤Ë°¤¹¤ëÁªÂò»è¤ÎÎó¤¬Â³¤¯¤Ï¤º¤Ç¤¢¤ë¡¥¤È¤³¤í¤¬ S ¤Ë¤Ï͸¸Ĥ·¤«ÁªÂò»è¤¬¤Ê¤¤¤Î¤Ç¡¤¤³¤ì¤é¤Î¤¤¤¯¤Ä¤«¤Ï½ÅÊ£¤·¤Æ¤¤¤ë¤Ï¤º¤À¡¥¤¿¤È¤¨¤Ð x3= x7 ¤È¤¤¤Ã¤¿¶ñ¹ç¤Ë¡¥(S ¤ÎÍ×ÁǤ½¤ì¤¾¤ì¤Ë¤¿¤¤¤·¤Æ¤Ò¤È¤Ä¤Å¤Ä¡Ö·ê¡×¤¬ÍѰդµ¤ì¤Æ¤¤¤ë¤È¤¹¤ë¡¥[¾¯¤Ê¤¯¤È¤â 3 ¤Ä¤Î¡Ö·ê¡×¤ò¤¹¤°»×¤¤¤Ä¤¤¤Æ¥¤¥á¡¼¥¸¤¬Äê¤Þ¤é¤Ê¤¤ÆÉ¼Ô¤Ï¡¤¼«Ê¬¤Î¤¤¤Á¤Ð¤ó¹¥¤¤Ê¡Ö·ê¡×°ì¼ïÎà¤À¤±¤ò¥¤¥á¡¼¥¸¤»¤è¡¥] 1ÆüÌÜ¡¤2ÆüÌÜ¡¤3ÆüÌܡġĤȤè¤êÈþ¤·¤¤Í×ÁǤòµá¤á¤Ä¤Ä¡¤¤¢¤ë¡Ö¥Ñ¥¤¥×¡×¤ò¤½¤ì¤é¤Î·ê¤ËËèÆü¤Ò¤È¡Ö·ê¡×¤Å¤ÄÆÍ¤Ã¹þ¤ó¤Ç¹Ô¤¯¤È¹Í¤¨¤ì¤Ð¡¤¡ÖÈþ¿Í¥Û¡¼¥ë¤Î¸¶Íý¡×¤½¤Î¤â¤Î¤À¡ª¡¡²¿ÆüÌܤ«¤Î¤¢¤ëÆü¡¤¤¸¤Ö¤ó¤¬°ÊÁ°ÆÍ¤Ã¹þ¤ó¤À·ê¤ËºÆ¤ÓÆÍ¤Ã¹þ¤ó¤Ç¤¤¤ë¤Î¤Ëµ¤¤Å¤¯¤Ï¤º¤À¡¥¤â¤·¡Ö°ÊÁ°¡×¤È¤¤¤¦¤Î¤¬Âè°ìÆüÌܤǤ¢¤ì¤Ð¡¤¤Þ¤ë¤Ç¡Ö¤·¤¢¤ï¤»¤ÎÀĤ¤Ä»¡×¤Ç¤Ï¤Ê¤¤¤«¡ª) ¤â¤·¤½¤¦¤Ç¤¢¤ë¤Ê¤é¡¤(x6, x5, x4, x3) ¤¬¥µ¥¤¥¯¥ë¤Ë¤Ê¤ë¤¿¤á¡¤P ¤ÏÈó½Û´ÄŪ¤Ç¤Ï¤Ê¤¤¡¥ ¾åµ¤Î¾ÚÌÀ¤òÀ¼¤Ë½Ð¤·¿Þ¤ËÉÁ¤ AV (¥ª¡¼¥Ç¥£¥ª¡¦¥Ó¥¸¥å¥¢¥ë) ²½¤·¤Æ¤ß¤ë¤È¤¤¤¤¡¥¡Ö¤¢¤ë͸½¸¹ç¾å¤Ç¶ËÂçÍ×ÁǤ¬Â¸ºß¤·¤Ê¤¤¤³¤È¡×¤È¡ÖÁª¹¥¤¬¥µ¥¤¥¯¥ë¤ò¤Õ¤¯¤à¤³¤È¡×¤È¤ÎƱÃÍ´Ø·¸¤òľ´ÑŪ¤Ë¥¤¥á¡¼¥¸¤Ç¤¤ë¤è¤¦¤Ë¤Ê¤ì¤Ð¤·¤á¤¿¤â¤Î¤Ç¤¢¤ë¡¥¤â¤·¤É¤¦¤·¤Æ¤â¤½¤ì¤¬¤Ç¤¤Ê¤±¤ì¤Ð¡¤¼Ò²ñÁªÂòÍýÏÀ¤ò¾ÚÌÀ¥ì¥Ù¥ë¤Þ¤ÇÍý²ò¤¹¤ë»ñ¼Á¤Ï¤Ê¤µ¤½¤¦¤À¡¥Âç³Ø±¡¥ì¥Ù¥ë¤Î·ÐºÑÍýÏÀ¤òÍý²ò¤¹¤ë¤Î¤Ï¡¤¤â¤Ã¤È¤¿¤¤¤Ø¤ó¤«¤â¤·¤ì¤Ê¤¤¡¥ |
|
|
|
| ¥Û¡¼¥à |
|
