خوارزمية كروسكال - وبناء إطار الأمثل

في أوائل الهندسه 19th القرن جاكوب شتاينر من برلين تعيين مهمة كيفية توصيل ثلاث قرى بحيث كان طولها أقصر. وفي وقت لاحق، لخص المشكلة: هو مطلوب منها لإيجاد نقطة في طائرة، كانت المسافة منه إلى n نقاط أخرى أدنى. في القرن 20th، فإنه يواصل العمل على هذا الموضوع. تقرر اتخاذ بضع نقاط وربطها في مثل هذه الطريقة أن المسافة بينهما كانت أقصر. كل هذا هو حالة خاصة من المشكلة قيد الدراسة.

"الجشع" الخوارزمية

يشير خوارزمية كروسكال إلى خوارزمية "الجشعين" (وتسمى أيضا التدرج). جوهر تلك - أعلى فوز في كل خطوة. ليس دائما، وتوفر الخوارزميات "الجشعين" أفضل حل لهذه المشكلة. هناك نظرية، والتي تبين أنها تعطي في تطبيقها على مهام محددة الحل الأمثل. هذه هي نظرية matroids. يشير خوارزمية كروسكال لمثل هذه المشاكل.

إيجاد الحد الأدنى للوزن الذبيحة

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

وصف

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

تطبيق

دلالة على الغابات الحالية F. إنه يقسم مجموعة من القمم في مجال الاتصال (أشكال نقابتهم F، وأنها هي المنفصلة). في كل حواف القمم الحمراء التي تكمن في قطعة واحدة. الجزء (خ) - الدالة التي لكل قمة س يعود جزء من الاسم، فإنه ينتمي السينية. اتحدوا (س، ص) - وهو الإجراء الذي يبني قسم جديد، ويتألف من الجمع بين أجزاء من x و y وجميع الأجزاء الأخرى. دعونا ن - عدد الحواف. يتم تضمين كافة هذه المفاهيم في خوارزمية كروسكال و. التنفيذ:

1. ترتيب جميع حواف الرسم البياني من 1 إلى الأوزان تصاعدي ن عشر. (منظمة العفو الدولية، ثنائية - ط مع عدد حافة قمة).

2. لأنني = 1 إلى n القيام به.

3. س: = الجزء (منظمة العفو الدولية).

4. ذ: = الجزء (ثنائية).

5. إذا كان x لا ذ المساواة ثم اتحدوا (س، ص)، لتشمل مع عدد حافة F ط.

صحة

دعونا T - إطار الرسم البياني الأصلي شيدت باستخدام خوارزمية كروسكال وS - إطاره التعسفي. علينا أن نثبت أن ث (T) ليست أكبر من ث (S).

دعونا M - تعدد زعانف S، P - عدد وافر من زعانف T. إذا S لا تساوي T، ثم هناك آخرون إطار ضلع T، لا ينتمون إلى S. S. وآخرون تجاور دورة، ويسمى C. C إزالة من أي وفاق الحافة، تعود S. نحصل على إطار جديد، لأن حواف والقمم هي نفسها. وزنه ليست أكبر من ث (S)، منذ ث (وآخرون) لم يعد (عناوين) ث في قوة كروسكال الخوارزمية. هذه العملية (بديلة الأضلاع T S على الأضلاع) سوف تتكرر طالما تلقي T. وزن كل إطار تلقت لاحقا ليس أكبر من وزنه السابق، مما يعني أن ث (T) ليست أكبر من ث (S).

متانة خوارزمية كروسكال ليلي من نظرية من رادو-ادموندز على matroids.

أمثلة تطبيق كروسكال خوارزمية

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

ويوضح الشكل الرسم البياني، والذي يتألف من عنصرين المتصلة. خطوط عريضة تشير إلى ضلوع إطار المثلى (الأخضر) التي شيدت باستخدام خوارزمية كروسكال.

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

تسلسل الأضلاع وأضاف (1.6)؛ (0،3)، (2،6) أو (2،6)، (0،3) - ليست مهمة. (3،4)؛ (0،1)، (1،6) أو (1،6)، (0،1)، والرعاية أيضا (5،6).

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