خوارزمية لحساب متوسط طول المسار البسيط

Question

إعطاء رسم بياني متصل واثنين من العقد S و T، يمكن أن يكون هناك العديد من المسارات البسيطة المختلفة (بدون دورات) من S إلى T.هل هناك خوارزمية فعالة للعثور على متوسط طول هذه المسارات؟

Answer 1

أعتقد أنك تعرف بالفعل أن خوارزمية متعددة الحدود لحساب عدد المسارات البسيطة بين العقدتين سوف تعني P= NP، ويرجع ذلك هذه النتيجة إلى الشجاعة (تعقيد مشاكل التعداد والموثوقية، 1979).

تخيل

الآن، تتوقع اكتشاف تناقض، بحيث يمكنك حساب $ \ text {AVG} (g، u، v) $ في وقت متعدد الألوان.

دع $ g + l $ يكون الرسم البياني الناتج عن إضافة مسار بسيط من الطول $ l $ بين $ U $ و $ v $ في $ g $ . هذا المسار الجديد مصنوع من $ L-1 $ العقد الجديدة ولا يتداخل مع أي مسار سابق من $ u $ $ to $ v $ ، المقدمة $ l \ geq 2 $ .

بعد ذلك، $ \ text {AVG} (g + 3، u، v) - \ text {avg} (g + 2، u، v) $ = $ 1 / \ text {paths} (g، u، v) +1) $ ، والتي يمكنك الحصول عليها $ \ # \ text {paths} (g، u، v) $ في وقت متعدد الحدود. لكننا نعرف أن هذا لا يمكن أن يتوقع أن يتم ذلك في وقت متعدد الحدود، وهو تناقض.