خوارزمية الحذف العكسي

الموسوعة الحرة

خوارزمية الحذف العكسي هي خوارزمية في نظرية المخططات تُستخدم للحصول على شجرة امتداد دنيا من مخطط متصل ذي أوزان حواف معينة . ظهرت هذه الخوارزمية لأول مرة في بحث كروسكال (1956) ، ولكن يجب عدم الخلط بينها وبين خوارزمية كروسكال التي وردت في البحث نفسه. إذا كان المخطط غير متصل، فإن هذه الخوارزمية ستجد شجرة امتداد دنيا لكل جزء غير متصل منه. تُسمى مجموعة أشجار الامتداد الدنيا هذه بالغابة الممتدة الدنيا، والتي تحتوي على كل رأس في المخطط.

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

  • ابدأ بالرسم البياني G، الذي يحتوي على قائمة من الحواف E.
  • انتقل عبر E بترتيب تنازلي لأوزان الحواف.
  • لكل حافة، تحقق مما إذا كان حذف الحافة سيؤدي إلى فصل الرسم البياني بشكل أكبر.
  • قم بإجراء أي عملية حذف لا تؤدي إلى انقطاع إضافي.

الشفرة الزائفة

تقوم الدالة ReverseDelete(edges[] E ) بترتيب E تنازليًا. حدد فهرسًا i ← 0 بينما i < حجم ( E ) عرّف الحافة ← E [ i ] احذف E [ i ] إذا لم يكن الرسم البياني متصلاً، فإن E [ i ] ← الحافة i ← i + 1 أعد الحواف[] E

في الرسم البياني أعلاه، يمثل الرسم البياني مجموعة الحواف E حيث تحتوي كل حافة على وزن ورؤوس متصلة v1 و v2 .

مثال

في المثال التالي، يتم تقييم الحواف الخضراء بواسطة الخوارزمية، بينما تم حذف الحواف الحمراء.

هذا هو الرسم البياني الأصلي. تشير الأرقام القريبة من الحواف إلى وزن كل حافة.
ستبدأ الخوارزمية بالحافة ذات الوزن الأقصى، وهي في هذه الحالة الحافة DE بوزن 15. وبما أن حذف الحافة DE لا يؤدي إلى فصل الرسم البياني بشكل أكبر، فسيتم حذفها.
الحافة التالية الأكبر هي FG، لذا ستتحقق الخوارزمية مما إذا كان حذف هذه الحافة سيؤدي إلى مزيد من الانفصال في الرسم البياني. وبما أن حذف الحافة لن يؤدي إلى مزيد من الانفصال، فسيتم حذفها.
الحافة الأكبر التالية هي الحافة BD، لذا ستتحقق الخوارزمية من هذه الحافة وتحذفها.
الحافة التالية التي يجب فحصها هي الحافة EG ، والتي لن تُحذف لأنها ستفصل العقدة G عن الرسم البياني. لذلك، الحافة التالية التي يجب حذفها هي الحافة BC .
الحافة الأكبر التالية هي الحافة EF، لذا ستتحقق الخوارزمية من هذه الحافة وتحذفها.
ثم ستقوم الخوارزمية بالبحث في الحواف المتبقية ولن تجد حافة أخرى لحذفها؛ لذلك هذا هو الرسم البياني النهائي الذي تم إرجاعه بواسطة الخوارزمية.

مدة التشغيل

يمكن إثبات أن الخوارزمية تعمل في زمن قدره O ( E log V (log log V ) ³ ) (باستخدام ترميز Big-O )، حيث E هو عدد الحواف و V هو عدد الرؤوس. ويتم تحقيق هذا الحد كما يلي:

  • يستغرق فرز الحواف حسب الوزن باستخدام فرز المقارنة O ( E log E ) من الوقت، والذي يمكن تبسيطه إلى O ( E log V ) باستخدام حقيقة أن أكبر قيمة لـ E هي V 2 .
  • يوجد عدد E من التكرارات للحلقة.
  • يمكن حذف حافة، والتحقق من اتصال الرسم البياني الناتج، وإعادة إدخال الحافة (إذا كانت غير متصلة) في وقت O (log V (log log V ) 3 ) لكل عملية ( Thorup 2000 ) .

إثبات صحة النتائج

يُنصح بقراءة برهان خوارزمية كروسكال أولاً.

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

شجرة ممتدة

الرسم البياني الفرعي المتبقي (g) الناتج عن الخوارزمية ليس منفصلاً، إذ تتحقق الخوارزمية من ذلك في السطر 7. لا يمكن أن يحتوي الرسم البياني الفرعي الناتج على دورة، لأنه في حال احتواءه عليها، فسنصادف عند التحرك على طول الحواف الحافة القصوى في الدورة، وسنحذف تلك الحافة. ​​لذا، يجب أن يكون g شجرة ممتدة للرسم البياني الرئيسي G.

الحد الأدنى

نبين أن الاقتراح التالي P صحيح بالاستقراء: إذا كانت F هي مجموعة الحواف المتبقية في نهاية حلقة while ، فهناك شجرة امتداد دنيا تكون (حوافها) مجموعة جزئية من F.

  1. من الواضح أن الشرط P يتحقق قبل بداية حلقة while. بما أن الرسم البياني المتصل الموزون يحتوي دائمًا على شجرة امتداد دنيا، وبما أن F يحتوي على جميع حواف الرسم البياني، فإن شجرة الامتداد الدنيا هذه يجب أن تكون مجموعة جزئية من F.
  2. لنفترض الآن أن P صحيحة لمجموعة حواف غير نهائية F ولندع T شجرة ممتدة دنيا موجودة في F. يجب أن نثبت أنه بعد حذف الحافة e في الخوارزمية، توجد شجرة ممتدة T' (ربما أخرى) وهي مجموعة جزئية من F.
    1. إذا لم يكن الضلع المحذوف التالي e ينتمي إلى T، فإن T=T' هي مجموعة جزئية من F ويتحقق الشرط P.
    2. وإلا، إذا كان e ينتمي إلى T: لاحظ أولًا أن الخوارزمية تزيل فقط الحواف التي لا تُسبب انقطاعًا في F. لذا، فإن e لا يُسبب انقطاعًا. لكن حذف e يُسبب انقطاعًا في الشجرة T (لأنه عضو في T). لنفترض أن e يفصل T إلى رسمين بيانيين فرعيين t1 و t2. بما أن الرسم البياني بأكمله متصل بعد حذف e، فلا بد من وجود مسار بين t1 و t2 (بخلاف e)، لذا لا بد من وجود دورة C في F (قبل إزالة e). ​​الآن، لا بد من وجود حافة أخرى في هذه الدورة (لنسميها f) ليست في T ولكنها في F (لأنه لو كانت جميع حواف الدورة في الشجرة T لما كانت شجرة بعد الآن). ندعي الآن أن T' = T - e + f هي الشجرة الممتدة الدنيا التي تُعد مجموعة جزئية من F.
    3. أولًا، نُثبت أن T' شجرة شاملة . نعلم أنه بحذف ضلع من شجرة وإضافة ضلع آخر لا يُسبب دورة، نحصل على شجرة أخرى بنفس الرؤوس. بما أن T كانت شجرة شاملة، فلا بد أن T' شجرة شاملة أيضًا. ذلك لأن إضافة "f" لا تُسبب أي دورات بعد حذف "e". (لاحظ أن الشجرة T تحتوي على جميع رؤوس الرسم البياني).
    4. ثانيًا، نثبت أن T' هي شجرة ممتدة دنيا . لدينا ثلاث حالات للحافتين "e" و "f". wt هي دالة الوزن .
      1. wt( f ) < wt( e ) هذا مستحيل لأن هذا يجعل وزن الشجرة T' أقل من وزن الشجرة T. وبما أن T هي الشجرة الممتدة الدنيا، فهذا ببساطة مستحيل.
      2. إذا كان وزن الحافة f أكبر من وزن الحافة e، فهذا مستحيل أيضًا. لأنه عند المرور على الحواف بترتيب تنازلي لأوزانها، يجب أن نرى الحافة f أولًا. وبما أن لدينا دورة C، فإن إزالة الحافة f لن تُسبب أي انقطاع في F. وبالتالي، كان من المفترض أن تُزيلها الخوارزمية من F مُسبقًا. إذن، الحافة f غير موجودة في F، وهذا مستحيل (وقد أثبتنا وجودها في الخطوة 4).
      3. إذن wt(f) = wt(e)، وبالتالي فإن T' هي أيضًا شجرة ممتدة دنيا . لذا، مرة أخرى، P صحيحة.
  3. إذن، يتحقق الشرط P عند انتهاء حلقة while (أي عندما نكون قد رأينا جميع الحواف)، وقد أثبتنا في النهاية أن F تصبح شجرة ممتدة، ونعلم أن F تحتوي على شجرة ممتدة دنيا كمجموعة جزئية منها. لذا، يجب أن تكون F هي الشجرة الممتدة الدنيا نفسها.

انظر أيضاً

مراجع