الشجرة الممتدة الصغرى: أقل مجموع لا يعني أقصر طريق

الخلاصة السريعة

في مثالنا الشجرة الممتدة الصغرى تختار A–B و B–C و C–D، ومجموعها 6. لكنها تجعل طريق A إلى D يمر بثلاث حواف مجموعها 6، بينما الحافة المباشرة A–D في الرسم الأصلي وزنها 3. الشجرة التي تحفظ أقصر الطرق من A هنا تختار A–B و B–C و A–D، ومجموع حوافها 7.

• الشجرة الممتدة تربط كل رؤوس المخطط دون دورة؛ ويصل بين كل رأسين طريق بسيط واحد. الشجرة الممتدة الصغرى تقلل مجموع أوزان الحواف المختارة، وإذا كان عدد الرؤوس n، تضم n − 1 حافة. يلزم اتصال المخطط لوجود شجرة تمتده كله. [1]
• الرسم الأصلي غير موجه: أوزان A–B و B–C و C–D تساوي 2 لكل منها، ووزن A–D يساوي 3. لا توجد حواف أخرى؛ الأوزان أعداد مجردة موجبة في مثالنا.
• أربع أشجار ممتدة ممكنة، بحذف حافة واحدة من الدورة. حذف A–D يعطي 2 + 2 + 2 = 6؛ وكل خيار آخر مجموعه 7. لذا الشجرة ذات المجموع 6 هي الصغرى الوحيدة هنا.
• داخل الشجرة الصغرى، طريق A→B→C→D وزنه 6. في الرسم الأصلي يوجد A→D بوزن 3؛ لذلك صغر مجموع الشبكة لا يحفظ أقصر طريق إلى D.
• الشجرة الأخرى تختار A–B و B–C و A–D. مجموعها 2 + 2 + 3 = 7، لكن طرقها من A إلى B و C و D أوزانها 2 و 4 و 3، وهي أقل أوزان تلك الطرق في الرسم الأصلي.
• إذا غيرنا وزن A–D إلى 2، يصبح مجموع الشجرة الأخرى 6 وتحقق الهدفين في المثال المعدل. فرق الهدفين لا يفرض اختلاف كل حلين دائمًا؛ اذكر الرسم والأوزان ونقطة البداية قبل الحكم.

حدد هل تجمع حواف الشبكة أم حواف طريق

الشجرة الممتدة تستخدم حواف المخطط لربط الرؤوس جميعًا، بحيث يوجد طريق بسيط واحد بين كل رأسين. الشجرة الصغرى تختار أقل مجموع أوزان ممكن، وكل شجرة ممتدة لرؤوس عددها n تضم n − 1 حافة. [1]

نثبت رؤوس المثال A و B و C و D. الحواف الوحيدة هي A–B بوزن 2، و B–C بوزن 2، و C–D بوزن 2، و A–D بوزن 3. لا أسهم ولا حلقات ذاتية أو حواف متوازية. المخطط متصل، والأرقام أوزان معلنة لا تقاس من طول الخط على الصفحة.

وزن شبكة مختارة هو جمع أوزان حوافها مرة لكل حافة. أما وزن طريق من A إلى نقطة أخرى فهو جمع أوزان الحواف التي يمر بها ذلك الطريق. نعني بالطريق الأقصر هنا الأقل في هذا المجموع، لا الأقل عددًا من الحواف ولا الأقصر في الرسم.

لم نعط الأرقام وحدة كيلومتر أو دقيقة أو سعرًا حقيقيًا. نستخدم المقارنة العددية نفسها للهدفين، كي يظهر الفرق بين مجموع كل الوصلات ومجموع وصلات طريق واحد. ولا نعالج قدرات نقل أو أعطالًا أو طرقًا ذات اتجاه واحد.

احصر الأشجار الأربع قبل اختيار الأقل مجموعًا

حوافنا الأربع تشكل دورة A→B→C→D→A. نحتاج في الشجرة ثلاث حواف فقط، ويترك حذف أي حافة واحدة سلسلة تصل الرؤوس الأربعة بلا دورة. لأن الرسم لا يملك سوى أربع حواف، فهذه الخيارات الأربعة هي جميع مجموعات الحواف الثلاث الممكنة.

إذا حذفنا A–D، بقيت A–B و B–C و C–D، ومجموع أوزانها 2 + 2 + 2 = 6. أما حذف إحدى الحواف ذات الوزن 2، فيترك الحافتين الأخريين من الوزن 2 والحافة A–D ذات الوزن 3، فيكون المجموع 2 + 2 + 3 = 7.

يبين الجدول الحافة المستبعدة والحواف المختارة ومجموعها. كل صف شجرة تمتد الرؤوس الأربعة، لكن صفًا واحدًا فقط يحقق المجموع 6؛ فهو الشجرة الممتدة الصغرى الوحيدة في هذا المثال. لا نحتاج تخمين الاختيار من قرب النقاط في الصورة.

تعرض الصورة الرئيسية الشجرة ذات المجموع 6 بخطوط سميكة. الخط الباهت A–D ما زال خيارًا في المخطط الأصلي، لكنه غير مختار في تلك الشجرة. إبقاؤه باهتًا يساعد على مقارنة الرسم الأصلي بالاختيار، ولا يضيفه إلى مجموع الشجرة.

افحص طريق البداية داخل الشجرة وخارجها

ابدأ من A في الشجرة الصغرى. للوصول إلى B نأخذ A→B بوزن 2، وإلى C نأخذ A→B→C بوزن 4، وإلى D نأخذ A→B→C→D بوزن 6. تلك الطرق لا تستعمل الحافة A–D لأنها ليست ضمن الشجرة المختارة.

في المخطط الأصلي، الطريق المباشر A→D متاح ووزنه 3. والطريق الآخر البسيط بين A و D هو A→B→C→D ووزنه 6. لذا أقل وزن للوصول إلى D من A هو 3، بينما الطريق في الشجرة الصغرى وزنه 6.

الفرق ليس خطأ في حساب 6، بل اختلاف المطلوب. اخترنا مجموعة وصلات تربط الرؤوس كلها بأقل مجموع، ولم نشترط أثناء الاختيار أن تحتفظ بأقل وزن لكل طريق ينطلق من A. هذا المثال ينقض افتراض أن الشجرة الأقل مجموعًا تحقق ذلك تلقائيًا.

ولا نجمع أوزان الطرق إلى B و C و D لنحصل على وزن الشبكة: بعض الحواف تظهر في أكثر من طريق. في الشجرة الصغرى الحافة A–B تدخل الطرق الثلاث، لكننا حسبنا وزنها 2 مرة واحدة عند حساب مجموع حواف الشجرة.

شجرة تحفظ أقصر الطرق من A، لكنها أعلى مجموعًا

لنختر A–B و B–C و A–D. هذه الحواف الثلاث تصل الرؤوس كلها بلا دورة، ومجموعها 2 + 2 + 3 = 7. من A يكون طريق B مباشرًا بوزن 2، وطريق C عبر B بوزن 4، وطريق D مباشرًا بوزن 3.

نقارن هذه الطرق بالبدائل في المخطط الأصلي. البديل البسيط إلى B هو A→D→C→B ووزنه 3 + 2 + 2 = 7، فيكون 2 أقل. وإلى C يوجد A→D→C بوزن 3 + 2 = 5، فيكون الطريق عبر B بوزن 4 أقل. وإلى D قارنّا 3 بالطريق الآخر ذي الوزن 6.

الجدول يقارن الطريق ووزنه داخل الشجرة الصغرى والطريق الأقصر في الرسم الأصلي. الشجرة الثانية تضم الطرق الأقصر الثلاث من A في هذا المثال، لكنها ليست الأقل مجموعًا، لأن مجموع 7 أعلى من 6.

الصورة الداخلية تعرض الحواف نفسها والأوزان نفسها، مع تغيير الحواف المختارة فقط. تركنا C–D باهتة؛ فهي موجودة في المخطط الأصلي، لكنها غير لازمة لطرق الشجرة الثانية من A. نقطة البداية A مميزة، لأن مقارنة هذه الطرق مرتبطة بها.

تغيير الأوزان قد يجعل الاختيار يحقق الهدفين

غيّر وزن A–D وحدها من 3 إلى 2، وأبقِ كل الحواف الأخرى بأوزانها 2. يصبح مجموع كل واحدة من الأشجار الأربع 6. الشجرة A–B و B–C و A–D تحقق عندئذ أقل مجموع للحواف، وتبقي أقصر الطرق من A بأوزان 2 إلى B و 4 إلى C و 2 إلى D.

إذن اختلاف الهدفين لا يعني أن الحلول لا تتطابق أبدًا، أو أن الشجرة الصغرى تكون فريدة في كل رسم. حكم التفرد والمجموع 6 والطرق 2 و 4 و 3 في الأقسام السابقة يخص الرسم الأصلي بوزن A–D الذي يساوي 3.

إذا كان المخطط غير متصل، فلا توجد شجرة ممتدة تربط رؤوسه كلها باستخدام حوافه فقط. [1]

مثلًا، إذا أضفت E بلا أي حافة إلى الرسم الأصلي، فلا تستطيع وصله ببقية الرؤوس باختيار حواف منها. لا يكفي عد أربع حواف أو إحضار شجرة للرؤوس A و B و C و D وترك E خارجها. يجب أن تشمل الشجرة كل الرؤوس المحددة في السؤال.

اكتب الهدف صراحة قبل المقارنة: أقل مجموع للحواف التي تربط الرؤوس كلها، أم أقل وزن للطرق من بداية معلومة؟ ثم احتفظ بقائمة الأوزان والرؤوس والحواف. تغيير أحدها يغيّر المسألة، فلا تنتقل نتيجة الرسم الأول إلى رسم آخر بمجرد تشابه الشكل.