خوارزمية MST ذات زمن خطي متوقع

تعتمد كل دورة من دورات الخوارزمية على تعديل لخوارزمية بوروفكا يشار إليها باسم خطوة بوروفكا :

المدخلات: رسم بياني G بدون رؤوس معزولة 1. لكل رأس v ، حدد أخف حافة متصلة بـ v. 2. أنشئ رسمًا بيانيًا مُختزلًا G' عن طريق استبدال كل مكون من مكونات G المتصلة بالحواف المحددة في الخطوة 1 برأس واحد. 3. إزالة جميع الرؤوس المعزولة، والحلقات الذاتية، والحواف المتكررة غير الدنيا من الرسم البياني G'. الناتج: الحواف المحددة في الخطوة 1 والرسم البياني المُختزل G'.

تُعادل خطوة بوروفكا الحلقة الداخلية لخوارزمية بوروفكا، التي تعمل في زمن O ( m )، حيث m هو عدد الحواف في الرسم البياني G. علاوة على ذلك، بما أنه يمكن اختيار كل حافة مرتين على الأكثر (مرة واحدة لكل رأس متصل بها)، فإن الحد الأقصى لعدد المكونات المنفصلة بعد الخطوة 1 يساوي نصف عدد الرؤوس. وبالتالي، تُقلل خطوة بوروفكا عدد الرؤوس في الرسم البياني بمقدار النصف على الأقل، وتحذف n /2 حافة على الأقل، حيث n هو عدد الرؤوس في الرسم البياني G.

مثال على تنفيذ خطوة Borůvka

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

في كل تكرار، تزيل الخوارزمية الحواف ذات الخصائص المحددة التي تستبعدها من الشجرة الممتدة الدنيا . تُسمى هذه الحواف بالحواف الثقيلة من النوع F ، وتُعرَّف كما يلي: ليكن F غابة على الرسم البياني H. الحافة الثقيلة من النوع F هي حافة e تربط الرأسين u و v، ويكون وزنها أكبر من وزن أثقل حافة على المسار من u إلى v في F. (إذا لم يكن المسار موجودًا في F، يُعتبر وزنه لانهائيًا). أي حافة ليست ثقيلة من النوع F تُسمى خفيفة من النوع F. إذا كان F رسمًا بيانيًا جزئيًا من G ، فلا يمكن لأي حافة ثقيلة من النوع F في G أن تكون ضمن الشجرة الممتدة الدنيا لـ G وفقًا لخاصية الدورة . عند إعطاء غابة، يمكن حساب الحواف الثقيلة من النوع F في وقت خطي باستخدام خوارزمية التحقق من الشجرة الممتدة الدنيا. ^{[ 2 ] [ 3 ]}

اللمة - ليكن H رسمًا بيانيًا جزئيًا من G يتكون من تضمين كل حافة من G بشكل مستقل باحتمالية p، وليكن F الغابة الممتدة الدنيا لـ H. العدد المتوقع للحواف الخفيفة من النوع F في G هو على الأكثر n/p حيث n هو عدد رؤوس G.

لإثبات اللمة، نفحص حواف G أثناء إضافتها إلى H. عدد الحواف الخفيفة من النوع F في G مستقل عن ترتيب اختيار حواف H ، لأن الغابة الممتدة الدنيا لـ H هي نفسها لجميع ترتيبات الاختيار. لأغراض البرهان، نفترض اختيار حواف H بأخذ حواف G واحدة تلو الأخرى بترتيب وزن الحافة من الأخف إلى الأثقل. لنفترض أن e هي الحافة قيد الدراسة حاليًا. إذا كانت نهايتا e في مكونين منفصلين من H ، فإن e هي أخف حافة تربط هذين المكونين، وإذا أُضيفت إلى H ، فستكون في F وفقًا لخاصية القطع . هذا يعني أيضًا أن e خفيفة من النوع F بغض النظر عما إذا أُضيفت إلى H أم لا ، لأنه لا تُؤخذ في الاعتبار إلا الحواف الأثقل لاحقًا. إذا كانت كلتا نهايتي e في نفس مكون H ، فإنها (وستكون دائمًا) ثقيلة من النوع F وفقًا لخاصية الدورة . تُضاف الحافة e بعد ذلك إلى H باحتمالية p .

الحد الأقصى لعدد حواف F-light المضافة إلى H هو n - 1، لأن أي شجرة امتداد دنيا لـ H تحتوي على n - 1 حافة. ​​بمجرد إضافة n - 1 حافة F-light إلى H ، لا تُعتبر أي من الحواف اللاحقة F-light وفقًا لخاصية الدورة . وبالتالي، فإن عدد حواف F-light في G محدود بعدد حواف F-light التي تم النظر فيها لـ H قبل إضافة n - 1 حافة F-light فعليًا إلى H. بما أن إضافة أي حافة F-light تتم باحتمالية p، فإن هذا يُكافئ رمي عملة معدنية باحتمالية p لظهور صورة حتى ظهور n - 1 صورة. إجمالي عدد رميات العملة يساوي عدد حواف F-light في G. يُعطى توزيع عدد رميات العملة بواسطة التوزيع ذي الحدين العكسي بمعاملات n - 1 و p . بالنسبة لهذه المعاملات، فإن القيمة المتوقعة لهذا التوزيع هي ( n - 1) / p .

بتجاهل العمل المنجز في المسائل الفرعية المتكررة، يكون إجمالي العمل المنجز في استدعاء واحد للخوارزمية خطيًا بالنسبة لعدد الحواف في الرسم البياني المُدخل. تستغرق الخطوة 1 وقتًا ثابتًا. يمكن تنفيذ خطوات بوروفكا في وقت خطي بالنسبة لعدد الحواف كما هو مذكور في قسم خطوات بوروفكا . تتكرر الخطوة 3 عبر الحواف وتقلب عملة معدنية واحدة لكل حافة، لذا فهي خطية بالنسبة لعدد الحواف. يمكن تنفيذ الخطوة 4 في وقت خطي باستخدام خوارزمية مُعدلة للتحقق من الشجرة الممتدة الدنيا ذات الوقت الخطي. ^{[ 2 ] [ 3 ]} بما أن العمل المنجز في تكرار واحد للخوارزمية خطي بالنسبة لعدد الحواف، فإن العمل المنجز في تشغيل كامل للخوارزمية (بما في ذلك جميع الاستدعاءات المتكررة) محدود بمعامل ثابت مضروب في إجمالي عدد الحواف في المسألة الأصلية وجميع المسائل الفرعية المتكررة.

ينتج عن كل استدعاء للخوارزمية مشكلتان فرعيتان على الأكثر، لذا تشكل مجموعة المشكلات الفرعية شجرة ثنائية . تقلل كل خطوة من خطوات بوروفكا عدد الرؤوس بمقدار النصف على الأقل، لذا بعد خطوتين من خطوات بوروفكا، ينخفض ​​عدد الرؤوس بمقدار الربع. بالتالي، إذا كان الرسم البياني الأصلي يحتوي على n رأسًا و m حافة ، فإن كل مشكلة فرعية عند العمق d من الشجرة تقع على رسم بياني يحتوي على n /4d ^رأسًا على الأكثر . كما أن الشجرة تحتوي على log₄n _مستوى على الأكثر.

لتحليل شجرة الاستدعاء الذاتي، لنفترض أن مشكلة الابن الأيسر هي المشكلة الفرعية في الاستدعاء الذاتي في الخطوة 3، ومشكلة الابن الأيمن هي المشكلة الفرعية في الاستدعاء الذاتي في الخطوة 5. احسب إجمالي عدد الحواف في المشكلة الأصلية وجميع المشكلات الفرعية عن طريق حساب عدد الحواف في كل مسار أيسر من الشجرة. يبدأ المسار الأيسر إما من الابن الأيمن أو من الجذر، ويشمل جميع العقد التي يمكن الوصول إليها عبر مسار من الأبناء الأيسرين. تظهر المسارات اليسرى لشجرة ثنائية محاطة بدائرة زرقاء في الرسم التخطيطي على اليمين.

يتم اختيار كل حافة في مسألة الابن الأيسر من حواف مسألة الأصل (بعد استبعاد الحواف التي تم تقليصها في خطوات بوروفكا ) باحتمالية 1/2. إذا كانت مسألة الأصل تحتوي على x حافة، فإن العدد المتوقع للحواف في مسألة الابن الأيسر هو x /2 على الأكثر. إذا تم استبدال x بمتغير عشوائي X ، فبفضل خطية التوقع، يُعطى العدد المتوقع للحواف في مسألة الابن الأيسر Y بالعلاقة التالية:${\displaystyle E[Y]\leq E[X]/2}$وبالتالي، إذا كان العدد المتوقع للحواف في مسألة ما في بداية المسار الأيسر هو k ، فإن مجموع العدد المتوقع للحواف في كل مسألة فرعية في المسار الأيسر يكون على الأكثر${\displaystyle \sum _{d=0}^{\infty }{\frac {k}{2^{d}}}=2k}$(انظر المتسلسلات الهندسية ). يحتوي الجذر على m من الحواف، لذا فإن العدد المتوقع للحواف يساوي 2m زائد ضعف العدد المتوقع للحواف في كل مسألة فرعية يمنى.

يُساوي العدد المتوقع للحواف في كل مسألة فرعية يمنى عدد حواف F-light في المسألة الأصلية، حيث F هي الشجرة الممتدة الدنيا للمسألة الفرعية اليسرى. وبحسب نظرية أخذ العينات، فإن عدد حواف F-light أقل من أو يساوي ضعف عدد الرؤوس في المسألة الفرعية . وبما أن عدد الرؤوس في مسألة فرعية عند العمق d هو n /4d ^، فإن العدد الإجمالي للرؤوس في جميع المسائل الفرعية اليمنى يُعطى بالعلاقة التالية:${\displaystyle \sum _{d=1}^{\infty }{\frac {2^{d-1}n}{4^{d}}}=n/2}$وبالتالي، فإن العدد المتوقع للحواف في المسألة الأصلية وجميع المسائل الفرعية هو على الأكثر 2m + n . وبما أن n على الأكثر 2m بالنسبة للرسم البياني الذي لا يحتوي على رؤوس معزولة، فإن الخوارزمية تعمل في وقت متوقع قدره O ( m ).

يُعادل زمن التشغيل في أسوأ الحالات زمن تشغيل خوارزمية بوروفكا . ويحدث هذا إذا أُضيفت جميع الحواف إلى المسألة الفرعية اليسرى أو اليمنى في كل استدعاء. في هذه الحالة، تكون الخوارزمية مطابقة ^{لخوارزمية} بوروفكا التي تعمل في زمن O (min{ n² , m log n }) على رسم بياني ذي n رأسًا و m حافة.