الشجرة الممتدة ذات الوزن الأدنى

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

شجرة الامتداد الدنيا (MST)، أو شجرة الامتداد الدنيا للوزن، هي مجموعة فرعية من حواف االرسم البياني غير الموجه المتصل والمرجح بالحافة. تربط هذه الشجرة جميع الرؤوسمعًا دون أي دورات(مسارات مغلقة)، ويكون لديها أقل وزن إجمالي ممكن للحواف .[1] هذا يعني أنها تمثل شجرة ممتدة يكون مجموع أوزان حوافها هو الأصغر قدر الإمكان.[2] بشكل عام، يمتلك أي رسم بياني غير موجه ذو حافة مرجحة (حتى لو لم يكن متصلاً بالضرورة) "غابة امتداد دنيا"، وهي عبارة عن اتحاد لأشجار الامتداد الدنيا لمكوناتها المتصلة.

تُعدّ أشجار الامتداد الدنيا (MST) مفيدة في العديد من حالات الاستخدام الواقعية. لنأخذ على سبيل المثال شركة اتصالات تسعى لتمديد كابلات في حي جديد. في هذه الحالة، إذا كانت الشركة مقيدة بمسارات محددة لدفن الكابلات (مثل الطرق)، يمكن تمثيل ذلك بـرسم بياني. ستكون "النقاط" في هذا الرسم هي المنازل، و"المسارات" هي الحواف التي تربط هذه المنازل.قد تكون بعض المسارات أكثر تكلفة من غيرها، إما لطولها الزائد أو لحاجتها لدفن الكابل على عمق أكبر؛ هذه المسارات الأكثر تكلفة تُمثل بـحواف ذات أوزان أكبر. يمكن أن تكون العملة (الدولار، اليورو، إلخ) وحدة مقبولة لوزن الحافة، حيث لا يُشترط أن تلتزم أطوال الحواف بقواعد الهندسة العادية مثل متباينة المثلث. شجرة الامتداد لهذا الرسم البياني ستكون مجموعة فرعية من تلك المسارات التي لا تحتوي على دورات (أي لا تُشكل حلقات مغلقة)، ولكنها لا تزال تربط جميع المنازل ببعضها. قد توجد العديد من الأشجار الممتدة المحتملة. هنا يأتي دور شجرة الامتداد الدنيا؛ فهي الشجرة التي تمتلك أقل تكلفة إجمالية، وبالتالي تمثل المسار الأقل تكلفة لمد الكابل.

ملكيات

التعدد المحتمل

وإذا كان هناك n رأسًا في الرسم البياني ، فإن كل شجرة ممتدة تحتوي على n − 1 حافة.

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

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

التفرد

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

دليل:

  1. افترض العكس ، أي أن هناك MSTs مختلفة A و B
  2. نظرًا لأن A و B يختلفان على الرغم من احتوائهما على نفس العقد، فهناك على الأقل حافة واحدة تنتمي إلى أحدهما ولكن ليس إلى الآخر. ومن بين هذه الحواف، دع e1 تكون الحافة ذات الوزن الأقل؛ وهذا الاختيار فريد من نوعه لأن أوزان الحواف كلها مميزة. بدون فقدان العمومية، افترض أن e1 موجودة في A
  3. نظرًا لأن B عبارة عن MST، {e1} ∪ B يجب أن تحتوي على دورة C مع e1 .
  4. باعتبارها شجرة، لا تحتوي A على أي دورات، وبالتالي يجب أن يكون لدى C حافة e2 ليست في A
  5. نظرًا لأن e1 تم اختياره باعتباره الحافة ذات الوزن الأقل الفريدة بين تلك التي تنتمي إلى واحدة فقط من A و B ، فيجب أن يكون وزن e2 أكبر من وزن e1 .
  6. نظرًا لأن e1 و e2 جزء من الدورة C ، فإن استبدال e2 بـ e1 في B يؤدي إلى الحصول على شجرة ممتدة ذات وزن أصغر.
  7. وهذا يتناقض مع الافتراض القائل بأن B هو MST.

بشكل عام، إذا لم تكن أوزان الحواف كلها مميزة، فإن مجموعة الأوزان (المتعددة) في الأشجار ذات الامتداد الأدنى ستكون فريدة بالتأكيد؛ أي أنها ستكون متماثلة لجميع الأشجار ذات الامتداد الأدنى الممكنة [1].[3]

إذا كانت الأوزان موجبة، فإن شجرة الامتداد الدنيا تُعد في الواقع رسمًا بيانيًا فرعيًا بأقل تكلفة يربط بين جميع الرؤوس. يعود السبب في ذلك إلى أنه إذا احتوى الرسم البياني الفرعي على <b>دورة</b>(Cycle)، فإن إزالة أي حافة على طول تلك الدورة سيؤدي إلى تقليل التكلفة الإجمالية مع الحفاظ على الاتصال بين جميع الرؤوس.

خاصية الدورة

بالنسبة لأي دورة (C) في الرسم البياني، إذا كان وزن الحافة (e) من (C) أكبر من الأوزان الفردية لأي من الحواف الأخرى لـ (C)، فلا يمكن لهذه الحافة (e) أن تنتمي إلى شجرة الامتداد الدنيا (MST).

نفترض العكس، أي أن الحافة e تنتمي إلى شجرة الامتداد الدنيا (MST) T1. عند حذف الحافة e، ستنقسم الشجرة T1 إلى شجرتين فرعيتين، بحيث تكون طرفا الحافة e في شجرتين فرعيتين مختلفتين.بما أن بقية الدورة C تعيد ربط الشجرتين الفرعيتين، فهذا يعني وجود حافة f ضمن الدورة C (وغير الحافة e) تكون نهايتاها في الشجرتين الفرعيتين المختلفتين. هذه الحافة f ستعيد ربط الشجرتين الفرعيتين لتشكيل شجرة جديدة T2.وبما أن وزن الحافة f أقل من وزن الحافة e (حسب الفرضية في المبرهنة)، فإن وزن الشجرة الجديدة T2 سيكون أقل من وزن الشجرة T1. هذا يتعارض مع الافتراض الأولي بأن T1 هي شجرة امتداد دنيا، مما يثبت أن الحافة e لا يمكن أن تنتمي إلى MST.

قطع الممتلكات

يوضح هذا الشكل خاصية القطع لـ MSTs. T هو MST الوحيد للرسم البياني المعطى. إذا كان S = {A,B,D,E}, وبالتالي V – S = {C,F}, فهناك 3 احتمالات للحافة عبر القطع (S, V – S) ، وهي الحواف BC ، EC ، EF للرسم البياني الأصلي. وبعد ذلك، يكون e أحد حواف الوزن الأدنى للقطع، وبالتالي فإن S ∪ {e} هو جزء من MST T

بالنسبة لأي قطع (cut) C من الرسم البياني، إذا كان وزن الحافة e في مجموعة القطع C أصغر بشكل صارم من أوزان جميع الحواف الأخرى لمجموعة القطع C، فإن هذه الحافة e تنتمي إلى جميع أشجار الامتداد الدنيا (MSTs) للرسم البياني .

الإثبات لنفرض وجود شجرة امتداد دنيا (MST) T لا تحتوي على الحافة e. عند إضافة الحافة e إلى الشجرة T، سينتج عن ذلك دورة (cycle). هذه الدورة ستقطع القطع (cut) مرة واحدة عند الحافة e وستعود عبر حافة أخرى e′ تنتمي إلى القطع نفسه.

بإزالة الحافة e′ من الشجرة، نحصل على شجرة ممتدة جديدة T∖{e' } ∪ {e}. وزن هذه الشجرة الجديدة سيكون أصغر تمامًا من وزن الشجرة T، لأن وزن الحافة e' أصغر بشكل صارم من وزن الحافة e′ (حسب تعريف مبرهنة القطع). هذا يتعارض مع الافتراض بأن T كانت شجرة امتداد دنيا، مما يثبت أن الحافة e' يجب أن تنتمي إلى جميع أشجار الامتداد الدنيا للرسم البياني.

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

حافة التكلفة الدنيا

إذا كانت الحافة ذات التكلفة الدنيا e لـالرسم البياني فريدة (أي لا توجد حافة أخرى بنفس التكلفة الأدنى)، فسيتم تضمين هذه الحافة في أي شجرة امتداد دنيا (MST).

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

الانكماش

إذا كانت T تمثل شجرة مكونة من حواف شجرة الامتداد الدنيا (MST)، فيمكننا دمج T في رأس واحد. هذا الإجراء يحافظ على الخاصية التي تنص على أن MST للرسم البياني المُقلَّص، بالإضافة إلى الحواف الأصلية في T، سيعطينا MST للرسم البياني قبل عملية الانكماش .[4]

الخوارزميات

في جميع الخوارزميات المذكورة أدناه، يُمثل m عدد الحواف في الرسم البياني، بينما يُمثل n عدد الرؤوس.

الخوارزميات الكلاسيكية

تم تطوير أول خوارزمية للعثور على شجرة الامتداد الدنيا (MST) بواسطة العالم التشيكي أوتاكار بوروفكا في عام 1926، وتُعرف اليوم باسم خوارزمية بوروفكا. كان الهدف من هذه الخوارزمية هو توفير تغطية كهربائية فعالة لمنطقة مورافيا.

تُنفذ الخوارزمية على مراحل متتالية، تُسمى كل منها خطوة بوروفكا. في كل خطوة، تُحدد غابة F تتكون من الحافة ذات الوزن الأدنى المرتبطة بكل رأس في الرسم البياني G. بعد ذلك، يُشكل الرسم البياني الجديد G1 = G \ F ليكون مدخلًا للخطوة التالية. يُشير الرمز G \ F هنا إلى الرسم البياني الناتج عن تقليص (انكماش) الحواف الموجودة في الغابة F. بفضل خاصية القطع (Cut Property)، تنتمي هذه الحواف المُقلَّصة إلى شجرة الامتداد الدنيا (MST).

تستغرق كل خطوة من خطوات بوروفكا وقتًا خطيًا (O(V) أو O(E)، اعتمادًا على طريقة التنفيذ). نظرًا لأن عدد الرؤوس ينخفض إلى النصف على الأقل في كل خطوة، فإن خوارزمية بوروفكا تستغرق وقتًا إجماليًا قدره (O(m log n)).[5]

الخوارزمية الثانية هي خوارزمية بريم ، التي اخترعها فويتش جارنيك عام 1930، وأعاد اكتشافها بريم عام 1957، ثم وديكسترا عام 1959. تعمل هذه الخوارزمية بشكل أساسي على بناء شجرة الامتداد الدنيا (MST) T حافة واحدة في كل مرة.

في البداية، تحتوي T على رأس عشوائي. في كل خطوة، تُضاف حافة (x,y) ذات الوزن الأقل إلى T، بحيث يكون الرأس x موجودًا بالفعل في T بينما الرأس y ليس كذلك. باستخدام خاصية القطع (Cut Property)، تكون جميع الحواف المُضافة إلى T جزءًا من الـ MST.يتراوح وقت تشغيل الخوارزمية بين O(mlogn) أو O(m+nlogn)، وذلك اعتمادًا على هياكل البيانات المستخدمة في التنفيذ.

الخوارزمية الثالثة الشائعة الاستخدام هي خوارزمية كروسكال (Kruskal's algorithm)، والتي تستغرق أيضًا وقتًا قدره O(mlogn).

الخوارزمية الرابعة، الأقل شيوعًا، هي <b>خوارزمية الحذف العكسي</b> (Reverse-Delete Algorithm)، وهي عكس خوارزمية كروسكال. يبلغ وقت تشغيلها O(m log n (log log n)3).

تُصنف هذه االخوارزميات الأربعة (بوروفكا، بريم، كروسكال، والحذف العكسي) على أنها خوارزميات جشعة (Greedy Algorithms). نظرًا لأنها تعمل في وقت متعدد الحدود، فإن مشكلة العثور على مثل هذه الأشجار تقع ضمن فئة التعقيد FP (Function Problem). أما مشكلات القرار ذات الصلة، مثل تحديد ما إذا كانت حافة معينة موجودة في شجرة الامتداد الدنيا (MST) أو تحديد ما إذا كان الحد الأدنى للوزن الإجمالي يتجاوز قيمة معينة، فتقع ضمن فئة التعقيد P (Polynomial time).

خوارزميات أسرع

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

في نموذج المقارنة، الذي تقتصر فيه العمليات المسموح بها على أوزان الحواف على المقارنات الثنائية فقط، توصل كارغر وكلاين وتارجان (1995) إلى <b>خوارزمية عشوائية زمنية خطية</b>. تعتمد هذه الخوارزمية على مزيج من خوارزمية بوروفكا وخوارزمية الحذف العكسي Karger, Klein & Tarjan (1995) [6][7]

أسرع خوارزمية غير عشوائية تعتمد على المقارنة ذات التعقيد الزمني المعروف، والتي ابتكرها <b>برنارد شازيل</b>، تعتمد على بنية بيانات تُعرف بـالكومة الناعمة (Soft Heap)، وهي في الأساس قائمة انتظار ذات أولوية تقريبية .[8][9]

يبلغ وقت تشغيل هذه الخوارزمية O(m α(m,n))، حيث α هي الدالة المعكوس الوظيفي الكلاسيكي لدالة أكرمان. تنمو الدالة α ببطء شديد لدرجة أنها يمكن اعتبارها، لأغراض عملية، ثابتة لا تتجاوز القيمة 4. وهذا يعني أن خوارزمية شازيل تستغرق وقتًا يقترب جدًا من الوقت الخطي.

خوارزميات الزمن الخطي في حالات خاصة

الرسوم البيانية الكثيفة

إذا كان الرسم البياني كثيفًا (أي m/n≥logloglogn)، فإن الخوارزمية الحتمية التي طورها فريدمان وتارجان تجد شجرة الامتداد الدنيا (MST) في وقت O(m) .[10] تنفذ هذه الخوارزمية عدة مراحل. تقوم كل مرحلة بتطبيق خوارزمية بريم عدة مرات، كل مرة لعدد محدود من الخطوات. وقت تشغيل كل مرحلة هو O(m + n). إذا كان عدد الرؤوس قبل مرحلة ما هو n′، فإن عدد الرؤوس المتبقية بعد هذه المرحلة لا يتجاوز . وبالتالي، لا يلزم سوى عدد قليل من المراحل، لا يتجاوز log∗n، مما يوفر وقت تشغيل خطيًا للرسوم البيانية الكثيفة.

ان هناك خوارزميات أخرى تعمل في وقت خطي على الرسوم البيانية الكثيفة .[11][12]

أوزان الأعداد الصحيحة

إذا كانت أوزان الحواف عبارة عن أعداد صحيحة ممثلة في النظام الثنائي، فمن المعروف أن هناك خوارزميات حتمية تستطيع حل المشكلة في عمليات الأعداد الصحيحة بـ O(m + n). ومع ذلك، تبقى مسألة ما إذا كان من الممكن حل المشكلة بشكل حتمي لرسم بياني عام في وقت خطي باستخدام خوارزمية تعتمد على المقارنة سؤالًا مفتوحًا حتى الآن.[13]

أشجار القرار

عند التعامل مع رسم بياني G ثابت العقد والحواف ولكن بأوزان غير معروفة، يمكننا بناء شجرة قرار ثنائية (DT) لتحديد شجرة الامتداد الدنيا (MST) بغض النظر عن ترتيب الأوزان.

تتميز هذه الشجرة بما يلي:

  • العقد الداخلية: تحتوي كل عقدة داخلية على مقارنة بين حافتين، كالسؤال: "هل وزن الحافة بين x وy أكبر من وزن الحافة بين w وz؟".
  • الأطفال: يمثل طفلا العقدة الإجابتين المحتملتين: "نعم" أو "لا".
  • الأوراق: تحتوي كل ورقة في الشجرة على قائمة من الحواف التي تُشكل الـ MST.

إن تعقيد وقت تشغيل شجرة القرار الثنائية هو ببساطة عمقها، وهو أكبر عدد من الاستعلامات اللازمة لإيجاد الـ MST. تُعد شجرة القرار الثنائية للرسم البياني G "مثلى" إذا كان لها أقل عمق ممكن بين جميع أشجار القرار الثنائية الصحيحة لـ G.

بالنسبة لأي عدد صحيح r، يمكن العثور على أشجار قرار مثلى لجميع الرسوم البيانية التي تحتوي على r رؤوس عن طريق لبحث بالقوة الغاشمة (Brute-force search). يتم هذا البحث على خطوتين.

أ. توليد : جميع DTs المحتملة

  • هناك رسوم بيانية مختلفة على رؤوس r .
  • بالنسبة لكل رسم بياني، يمكن دائمًا العثور على MST باستخدام مقارنات r(r – 1) ، على سبيل المثال بواسطة خوارزمية Prim .
  • ومن ثم، فإن عمق DT الأمثل أقل من r2 .
  • ومن ثم، فإن عدد العقد الداخلية في DT الأمثل أقل من .
  • كل عقدة داخلية تقارن بين حافتين. عدد الحواف هو r2 على الأكثر، وبالتالي فإن العدد المختلف للمقارنات هو r4 على الأكثر.
  • ومن ثم، فإن عدد DTs المحتملة أقل من

ب. تحديد : DTs الصحيحة للتأكد من صحة DT، يجب التحقق منها على جميع التباديل الممكنة لأوزان الحافة .

  • عدد هذه التباديل هو على الأكثر (r2)! .
  • بالنسبة لكل تبديل، قم بحل مشكلة MST على الرسم البياني المعطى باستخدام أي خوارزمية موجودة، وقارن النتيجة بالإجابة المقدمة بواسطة DT.
  • يبلغ وقت تشغيل أي خوارزمية MST r2 على الأكثر، وبالتالي فإن الوقت الإجمالي المطلوب للتحقق من جميع التباديل هو (r2 + 1)!

فإن إجمالي الوقت المطلوب لإيجاد DT الأمثل لجميع الرسوم البيانية التي تحتوي على r رؤوس هي :[5]

وهو أقل من

الخوارزمية المثالية

لقد ابتكر سيث بيتي وفيجايا راماشاندران خوارزمية شجرة الامتداد الدنيا (MST) حتمية تعتمد على المقارنة، وقد تم إثبات صحتها.[5] فيما يلي وصف مبسط لهذه الخوارزمية.

  1. ليكن r = log log log n ، حيث n هو عدد الرؤوس. ابحث عن جميع أشجار القرار المثالية على الرؤوس r . يمكن القيام بذلك في الوقت O(n) (انظر أشجار القرار أعلاه).
  2. قم بتقسيم الرسم البياني إلى مكونات تحتوي على r رأس على الأكثر في كل مكون. يستخدم هذا القسم كومة ناعمة ، والتي "تفسد" عددًا صغيرًا من حواف الرسم البياني.
  3. استخدم أشجار القرار المثالية للعثور على MST للمخطط الفرعي غير الفاسد داخل كل مكون.
  4. قم بتقليص كل مكون متصل يمتد بواسطة MSTs إلى رأس واحد، وقم بتطبيق أي خوارزمية تعمل على الرسوم البيانية الكثيفة في الوقت O(m) لتقليص الرسم البياني الفرعي غير الفاسد
  5. قم بإضافة الحواف التالفة إلى الغابة الناتجة لتشكيل رسم بياني فرعي مضمون لاحتواء الحد الأدنى من الشجرة الممتدة، وأصغر بعامل ثابت من الرسم البياني الأولي. قم بتطبيق الخوارزمية المثلى بشكل متكرر على هذا الرسم البياني.

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

الخوارزميات المتوازية والموزعة

تناولت الأبحاث أيضًا الخوارزميات المتوازية لمشكلة شجرة الامتداد الدنيا (MST). باستخدام عدد خطي من المعالجات، يمكن حل المشكلة في وقت O(log n).[14][15]

يمكن أيضًا التعامل مع مشكلة شجرة الامتداد الدنيا (MST) ببطريقة موزعة. فإذا اعتبرنا كل عقدة بمثابة جهاز كمبيوتر، ولا تملك أي عقدة معلومات سوى عن الروابط المتصلة بها مباشرةً، فإنه يظل بالإمكان حساب <b>شجرة الامتداد الدنيا الموزعة</b>(Distributed Minimum Spanning Tree).

MST على الرسوم البيانية الكاملة ذات الأوزان العشوائية

أظهر <b>آلان م. فريز</b> أنه في رسم بياني كامل ذي n رأس، حيث تمثل أوزان الحواف متغيرات عشوائية موزعة بشكل متطابق مع دالة التوزيع F التي تُرضي . عندما يقترب n من اللانهاية (+∞)، فإن الوزن المتوقع لشجرة الامتداد الدنيا (MST) يقترب من حيث ζ هي دالة زيتا لريمان (وبشكل أكثر تحديدًا، ζ(3) هو ثابت أبيري).

وقد أثبت فريز وستيل أيضًا التقارب في الاحتمالات لهذه القيمة. كما أثبت سفانتي جانسون نظرية الحد المركزي لوزن شجرة الامتداد الدنيا (MST).

بالنسبة للأوزان العشوائية الموحدة في النطاق ، تم حساب الحجم الدقيق المتوقع لشجرة الامتداد الدنيا (MST) للرسوم البيانية الكاملة الصغيرة [1].[16]

الرؤوس الحجم المتوقع الحجم التقريبي المتوقع
2
1/2
 0.5
3
3/4
 0.75
4
31/35
 0.8857143
5
893/924
 0.9664502
6
278/273
 1.0183151
7
30739/29172
 1.053716
8
199462271/184848378
 1.0790588
9
126510063932/115228853025
 1.0979027

المتغير الكسري

توجد نسخة كسرية من شجرة الامتداد الدنيا (MST)، حيث يُسمح لكل حافة بأن تظهر "كسريًا". رسميًا، تُعرف المجموعة الكسرية الممتدة (Fractional Spanning Set) للرسم البياني (V,E) بأنها دالة غير سالبة f على مجموعة الحواف E. هذه الدالة يجب أن تحقق شرطًا أساسيًا: لكل مجموعة فرعية غير تافهة W من الرؤوس V (أي أن W ليست فارغة ولا تساوي V)، يكون مجموع قيم f(e) على جميع الحواف التي تربط عقدة في W بعقدة خارج W (أي في V∖W) أكبر من أو يساوي 1.

بشكل بديهي، يمثل f(e) الكسر من الحافة e الذي يُساهم في المجموعة الممتدة. أما مجموعة الامتداد الكسري الأدنى (Minimum Fractional Spanning Set) فهي تلك المجموعة الممتدة الكسرية التي يكون مجموعها هو الأصغر قدر الإمكان.

إذا تم تقييد الكسور f(e) لتكون ضمن المجموعة {0,1}، فإن المجموعة T من الحواف حيث f(e)=1 تمثل مجموعة ممتدة (Spanning Set). تعني هذه المجموعة أن كل عقدة أو مجموعة فرعية من العقد تتصل ببقية الرسم البياني بحافة واحدة على الأقل من T.علاوة على ذلك، إذا كانت f تُقلل من المجموع ، فإن المجموعة الممتدة الناتجة تكون بالضرورة شجرة. وذلك لأنه إذا احتوت على دورة، يمكن إزالة حافة واحدة من هذه الدورة دون التأثير على خاصية الامتداد، مما يقلل من التكلفة الإجمالية وهذا يناقض كونها الأقل تكلفة.بناءً على ذلك، تُعد مشكلة المجموعة الكسرية الدنيا (Fractional Spanning Set Problem) بمثابة تخفيف (relaxation) لمشكلة شجرة الامتداد الدنيا (MST)، ولذلك يمكن تسميتها أيضًا بـمشكلة MST الكسرية (Fractional MST Problem).

يمكن حل مشكلة MST الكسرية في زمن متعدد الحدود باستخدام طريقة القطع الناقص :248. ومع ذلك، إذا أضفنا شرطًا بأن تكون (f(e)) نصف عدد صحيح (أي أن (f(e)) يجب أن تكون ضمن {0، 1/2، 1})، تصبح المشكلة NP-hard [1]:248. يعود ذلك إلى أنها تتضمن كحالة خاصة <b>مشكلة الدورة الهاميلتونية</b>: ففي رسم بياني غير مرجح ذي (n) رأس، لا يمكن الحصول على رسم بياني نصف صحيح بمتوسط وزن () إلا عن طريق تعيين وزن 1/2 لكل حافة من دورات هاميلتون.

متغيرات أخرى

قالب:Regular polygon minimum spanning tree.svg

  • شجرة شتاينر لمجموعة فرعية من الرؤوس هي الشجرة الدنيا التي تمتد عبر المجموعة الفرعية المحددة. إن العثور على شجرة شتاينر هو NP-كامل .
  • شجرة الامتداد الدنيا (k-MST) هي الشجرة التي تمتد عبر مجموعة فرعية من k رأس في الرسم البياني بأقل وزن ممكن.
  • مجموعة من أشجار الامتداد الـ k الأصغر هي مجموعة فرعية من k شجرة امتداد (من بين جميع أشجار الامتداد الممكنة) بحيث لا توجد شجرة امتداد خارج هذه المجموعة ذات وزن أصغر . (لاحظ أن هذه المشكلة لا علاقة لها بشجرة الامتداد الدنيا k-MST).[17][18][19]
  • شجرة الامتداد الدنيا الإقليدية (Euclidean minimum spanning tree) هي شجرة امتداد لرسم بياني تكون أوزان حوافها مطابقة للمسافة الإقليدية بين الرؤوس، وهي نقاط في مستوى (أو فراغ).
  • شجرة الامتداد الدنيا المستطيلة (Rectilinear minimum spanning tree) هي شجرة امتداد لرسم بياني تكون أوزان حوافها مطابقة للمسافة المستطيلة بين الرؤوس، وهي نقاط في مستوى (أو فراغ).
  • شجرة الامتداد الدنيا الموزعة (Distributed minimum spanning tree) هي امتداد لمفهوم شجرة الامتداد الدنيا إلى النموذج الموزع، حيث يُعتبر كل عقدة جهاز كمبيوتر، ولا تعرف أي عقدة شيئًا سوى الروابط المتصلة بها. التعريف الرياضي للمشكلة هو نفسه، ولكن توجد مقاربات مختلفة للحل.
  • شجرة الامتداد الدنيا ذات السعة (Capacitated minimum spanning tree) هي شجرة تحتوي على عقدة مميزة (أصل أو جذر)، وكل من الأشجار الفرعية المتصلة بهذه العقدة لا تحتوي على أكثر من c عقدة. يُطلق على c اسم سعة الشجرة. حل مشكلة CMST بشكل مثالي هو NP-hard [4]، ولكن التقنيات الاستدلالية الجيدة مثل Esau-Williams و Sharma تُنتج حلولًا قريبة من الأمثل في وقت متعدد الحدود.[20]
  • شجرة الامتداد الدنيا ذات القيود الدرجية (Degree-constrained minimum spanning tree) هي شجرة امتداد دنيا حيث يكون كل رأس متصلًا بما لا يزيد عن d رأس أخرى، لعدد d مُعطى. تعتبر الحالة d=2 حالة خاصة من مشكلة البائع المتجول، لذا فإن شجرة الامتداد الدنيا المقيدة بالدرجة هي NP-hard بشكل عام.
  • الشجرة الجذرية (Arborescence) هي نوع مختلف من شجرة الامتداد الدنيا للرسوم البيانية الموجهة. يمكن حلها في وقت O(E+VlogV) باستخدام خوارزمية Chu–Liu/Edmonds.
  • شجرة الامتداد القصوى (Maximum spanning tree) هي شجرة امتداد يكون وزنها أكبر من أو يساوي وزن أي شجرة امتداد أخرى. يمكن إيجاد مثل هذه الشجرة باستخدام خوارزميات مثل بريم أو كروسكال بعد ضرب أوزان الحواف بـ -1 وحل مشكلة شجرة الامتداد الدنيا على الرسم البياني الجديد. المسار في شجرة الامتداد القصوى هو أوسع مسار في الرسم البياني بين نقطتي نهايته: من بين جميع المسارات الممكنة، فإنه يعظم وزن الحافة الأقل وزنًا.[21][22] تجد أشجار الامتداد القصوى تطبيقات في خوارزميات التحليل اللغوي الطبيعي [21] وفي خوارزميات تدريب الحقول العشوائية الشرطية.
  • مشكلة شجرة الامتداد الدنيا الديناميكية (Dynamic MST problem) تتعلق بتحديث شجرة امتداد دنيا تم حسابها مسبقًا بعد تغيير وزن حافة في الرسم البياني الأصلي أو إدخال/حذف رأس .[23][24][25]
  • مشكلة شجرة الامتداد الدنيا ذات التسمية الدنيا (Minimum labeling spanning tree problem) تهدف إلى إيجاد شجرة امتداد بأقل عدد من أنواع التسميات إذا كانت كل حافة في الرسم البياني مرتبطة بتسمية من مجموعة تسميات محدودة بدلاً من وزن.[26]
  • حافة الاختناق (Bottleneck edge) هي الحافة ذات الوزن الأعلى في شجرة امتداد. تُعتبر شجرة الامتداد شجرة امتداد دنيا ذات اختناق (MBST) إذا لم يحتوي الرسم البياني على شجرة امتداد ذات وزن حافة اختناق أصغر. شجرة الامتداد الدنيا (MST) هي بالضرورة شجرة امتداد دنيا ذات اختناق (MBST) (يمكن إثبات ذلك بخاصية القطع)، ولكن شجرة الامتداد الدنيا ذات الاختناق (MBST) ليست بالضرورة شجرة امتداد دنيا (MST).[27][28]
  • لعبة شجرة الامتداد الدنيا ذات التكلفة الأدنى (Minimum-cost spanning tree game) هي لعبة تعاونية يتعين على اللاعبين فيها تقاسم تكاليف بناء شجرة الامتداد المثلى فيما بينهم.
  • مشكلة تصميم الشبكة الأمثل (Optimal network design problem) هي مشكلة حساب مجموعة، تخضع لقيود الميزانية، تحتوي على شجرة امتداد، بحيث يكون مجموع أقصر المسارات بين كل زوج من العقد أصغر ما يمكن.

التطبيقات

للأشجار ذات الامتداد الأدنى (MSTs) تطبيقات مباشرة في تصميم الشبكات، بما في ذلك شبكات الكمبيوتر ،وشبكات الاتصالات، وشبكات النقل، وشبكات إمدادات المياه، والشبكات الكهربائية (التي اختُرعت لأجلها في الأصل، كما ذكرنا سابقًا).[29]

تُستدعى هذه الأشجار أيضًا كبرامج فرعية (subroutines) في خوارزميات لحل مشكلات أخرى، ومنها:

  • خوارزمية كريستوفيدس لتقريب مشكلة بائع السفر .[30]
  • تقريب مشكلة القطع الأدنى متعدد الأطراف (وهي تعادل مشكلة التدفق الأقصى في حالة الطرف الواحد) [3].
  • تقريب المطابقة المثالية المرجحة بأقل تكلفة .[31]

تُستخدم أشجار الامتداد الدنيا (MSTs) في مجموعة واسعة من التطبيقات العملية، منها:

مراجع

  1. ↑ "scipy.sparse.csgraph.minimum_spanning_tree - SciPy v1.7.1 Manual". Numpy and Scipy Documentation — Numpy and Scipy documentation. مؤرشف من الأصل في 2025-02-25. اطلع عليه بتاريخ 2021-12-10. A minimum spanning tree is a graph consisting of the subset of edges which together connect all connected nodes, while minimizing the total sum of weights on the edges.
  2. ↑ "networkx.algorithms.tree.mst.minimum_spanning_edges". NetworkX 2.6.2 documentation. مؤرشف من الأصل في 2025-04-06. اطلع عليه بتاريخ 2021-12-13. A minimum spanning tree is a subgraph of the graph (a tree) with the minimum sum of edge weights. A spanning forest is a union of the spanning trees for each connected component of the graph.
  3. ↑ "Do the minimum spanning trees of a weighted graph have the same number of edges with a given weight?". cs.stackexchange.com. اطلع عليه بتاريخ 2018-04-04.
  4. ↑ Pettie، Seth؛ Ramachandran، Vijaya (2002)، "An optimal minimum spanning tree algorithm" (PDF)، Journal of the Association for Computing Machinery، ج. 49، ص. 16–34، DOI:10.1145/505241.505243، MR:2148431، S2CID:5362916، مؤرشف من الأصل (PDF) في 2024-08-04.
  5. 1 2 3 Pettie، Seth؛ Ramachandran، Vijaya (2002)، "An optimal minimum spanning tree algorithm" (PDF)، Journal of the Association for Computing Machinery، ج. 49، ص. 16–34، DOI:10.1145/505241.505243، MR:2148431، S2CID:5362916، مؤرشف من الأصل (PDF) في 2024-08-04Pettie, Seth; Ramachandran, Vijaya (2002), "An optimal minimum spanning tree algorithm" (PDF), Journal of the Association for Computing Machinery, 49 (1): 16–34, doi:10.1145/505241.505243، MR 2148431, S2CID 5362916.
  6. ↑ Karger، David R.؛ Klein، Philip N.؛ Tarjan، Robert E. (1995)، "A randomized linear-time algorithm to find minimum spanning trees"، Journal of the Association for Computing Machinery، ج. 42، ص. 321–328، DOI:10.1145/201019.201022، MR:1409738، S2CID:832583
  7. ↑ Pettie، Seth؛ Ramachandran، Vijaya (2002)، "Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms"، Proc. 13th ACM-SIAM Symposium on Discrete Algorithms (SODA '02)، San Francisco, California، ص. 713–722، ISBN:9780898715132{{استشهاد}}: صيانة الاستشهاد: مكان بدون ناشر (link).
  8. ↑ Chazelle، Bernard (2000)، "The soft heap: an approximate priority queue with optimal error rate"، Journal of the Association for Computing Machinery، ج. 47، ص. 1012–1027، DOI:10.1145/355541.355554، MR:1866455، S2CID:12556140.
  9. ↑ Chazelle، Bernard (2000)، "A minimum spanning tree algorithm with inverse-Ackermann type complexity"، Journal of the Association for Computing Machinery، ج. 47، ص. 1028–1047، DOI:10.1145/355541.355562، MR:1866456، S2CID:6276962.
  10. ↑ Fredman، M. L.؛ Tarjan، R. E. (1987). "Fibonacci heaps and their uses in improved network optimization algorithms". Journal of the ACM. ج. 34 ع. 3: 596. DOI:10.1145/28869.28874. S2CID:7904683.
  11. ↑ Chazelle، Bernard (2000)، "A minimum spanning tree algorithm with inverse-Ackermann type complexity"، Journal of the Association for Computing Machinery، ج. 47، ص. 1028–1047، DOI:10.1145/355541.355562، MR:1866456، S2CID:6276962Chazelle, Bernard (2000), "A minimum spanning tree algorithm with inverse-Ackermann type complexity", Journal of the Association for Computing Machinery, 47 (6): 1028–1047, doi:10.1145/355541.355562, MR 1866456, S2CID 6276962.
  12. ↑ Gabow، H. N.؛ Galil، Z.؛ Spencer، T.؛ Tarjan، R. E. (1986). "Efficient algorithms for finding minimum spanning trees in undirected and directed graphs". Combinatorica. ج. 6 ع. 2: 109. DOI:10.1007/bf02579168. S2CID:35618095.
  13. ↑ Fredman، M. L.؛ Willard، D. E. (1994)، "Trans-dichotomous algorithms for minimum spanning trees and shortest paths"، Journal of Computer and System Sciences، ج. 48، ص. 533–551، DOI:10.1016/S0022-0000(05)80064-9، MR:1279413.
  14. ↑ Chong، Ka Wong؛ Han، Yijie؛ Lam، Tak Wah (2001)، "Concurrent threads and optimal parallel minimum spanning trees algorithm"، Journal of the Association for Computing Machinery، ج. 48، ص. 297–323، DOI:10.1145/375827.375847، MR:1868718، S2CID:1778676.
  15. ↑ Pettie، Seth؛ Ramachandran، Vijaya (2002)، "A randomized time-work optimal parallel algorithm for finding a minimum spanning forest" (PDF)، SIAM Journal on Computing، ج. 31، ص. 1879–1895، DOI:10.1137/S0097539700371065، MR:1954882، مؤرشف من الأصل (PDF) في 2012-01-28.
  16. ↑ Steele، J. Michael (2002)، "Minimal spanning trees for graphs with random edge lengths"، Mathematics and computer science, II (Versailles, 2002)، Trends Math.، Basel: Birkhäuser، ص. 223–245، MR:1940139
  17. ↑ Gabow، Harold N. (1977)، "Two algorithms for generating weighted spanning trees in order"، SIAM Journal on Computing، ج. 6، ص. 139–150، DOI:10.1137/0206011، MR:0441784.
  18. ↑ Eppstein، David (1992)، "Finding the k smallest spanning trees"، BIT، ج. 32، ص. 237–248، DOI:10.1007/BF01994879، MR:1172188، S2CID:121160520.
  19. ↑ Frederickson، Greg N. (1997)، "Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees"، SIAM Journal on Computing، ج. 26، ص. 484–538، DOI:10.1137/S0097539792226825، MR:1438526، مؤرشف من الأصل في 2024-07-06.
  20. ↑ Jothi، Raja؛ Raghavachari، Balaji (2005)، "Approximation Algorithms for the Capacitated Minimum Spanning Tree Problem and Its Variants in Network Design"، ACM Trans. Algorithms، ج. 1، ص. 265–282، DOI:10.1145/1103963.1103967، S2CID:8302085
  21. 1 2 McDonald، Ryan؛ Pereira، Fernando؛ Ribarov، Kiril؛ Hajič، Jan (2005). "Non-projective dependency parsing using spanning tree algorithms" (PDF). Proc. HLT/EMNLP. مؤرشف من الأصل (PDF) في 2022-01-29.
  22. ↑ Hu، T. C. (1961)، "The maximum capacity route problem"، Operations Research، ج. 9، ص. 898–900، DOI:10.1287/opre.9.6.898، JSTOR:167055.
  23. ↑ Holm، Jacob؛ de Lichtenberg، Kristian؛ Thorup، Mikkel (2001)، "Poly-logarithmic deterministic fully dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity"، Journal of the Association for Computing Machinery، ج. 48، ص. 723–760، DOI:10.1145/502090.502095، MR:2144928، S2CID:7273552.
  24. ↑ Spira، P. M.؛ Pan، A. (1975)، "On finding and updating spanning trees and shortest paths" (PDF)، SIAM Journal on Computing، ج. 4، ص. 375–380، DOI:10.1137/0204032، MR:0378466.
  25. ↑ Chin، F.؛ Houck، D. (1978)، "Algorithms for updating minimal spanning trees"، Journal of Computer and System Sciences، ج. 16، ص. 333–344، DOI:10.1016/0022-0000(78)90022-3.
  26. ↑ Chang، R.S.؛ Leu، S.J. (1997)، "The minimum labeling spanning trees"، Information Processing Letters، ج. 63، ص. 277–282، DOI:10.1016/s0020-0190(97)00127-0.
  27. ↑ "Everything about Bottleneck Spanning Tree". flashing-thoughts.blogspot.ru. 5 يونيو 2010. مؤرشف من الأصل في 2018-05-05. اطلع عليه بتاريخ 2018-04-04.
  28. ↑ "Archived copy" (PDF). مؤرشف من الأصل (PDF) في 2013-06-12. اطلع عليه بتاريخ 2014-07-02.{{استشهاد ويب}}: صيانة الاستشهاد: الأرشيف كعنوان (link)
  29. ↑ Graham، R. L.؛ Hell، Pavol (1985)، "On the history of the minimum spanning tree problem"، Annals of the History of Computing، ج. 7، ص. 43–57، DOI:10.1109/MAHC.1985.10011، MR:0783327، S2CID:10555375
  30. ↑ Dahlhaus، E.؛ Johnson، D. S.؛ Papadimitriou، C. H.؛ Seymour، P. D.؛ Yannakakis، M. (أغسطس 1994). "The complexity of multiterminal cuts" (PDF). SIAM Journal on Computing. ج. 23 ع. 4: 864–894. DOI:10.1137/S0097539792225297. مؤرشف من الأصل (PDF) في 2004-08-24. اطلع عليه بتاريخ 2012-12-17.
  31. ↑ Supowit، Kenneth J.؛ Plaisted، David A.؛ Reingold، Edward M. (1980). "Heuristics for weighted perfect matching". 12th Annual ACM Symposium on Theory of Computing (STOC '80). New York, NY, USA: ACM. ص. 398–419. DOI:10.1145/800141.804689. مؤرشف من الأصل في 2018-11-21.
  32. ↑ Sneath، P. H. A. (1 أغسطس 1957). "The Application of Computers to Taxonomy". Journal of General Microbiology. ج. 17 ع. 1: 201–226. DOI:10.1099/00221287-17-1-201. PMID:13475686.
  33. ↑ Asano، T.؛ Bhattacharya، B.؛ Keil، M.؛ Yao، F. (1988). "Clustering algorithms based on minimum and maximum spanning trees". Fourth Annual Symposium on Computational Geometry (SCG '88). ج. 1. ص. 252–257. DOI:10.1145/73393.73419.
  34. ↑ Gower، J. C.؛ Ross، G. J. S. (1969). "Minimum Spanning Trees and Single Linkage Cluster Analysis". Journal of the Royal Statistical Society. C (Applied Statistics). ج. 18 ع. 1: 54–64. DOI:10.2307/2346439. JSTOR:2346439.
  35. ↑ Päivinen، Niina (1 مايو 2005). "Clustering with a minimum spanning tree of scale-free-like structure". Pattern Recognition Letters. ج. 26 ع. 7: 921–930. Bibcode:2005PaReL..26..921P. DOI:10.1016/j.patrec.2004.09.039.
  36. ↑ Xu، Y.؛ Olman، V.؛ Xu، D. (1 أبريل 2002). "Clustering gene expression data using a graph-theoretic approach: an application of minimum spanning trees". Bioinformatics. ج. 18 ع. 4: 536–545. DOI:10.1093/bioinformatics/18.4.536. PMID:12016051.
  37. ↑ Dalal، Yogen K.؛ Metcalfe، Robert M. (1 ديسمبر 1978). "Reverse path forwarding of broadcast packets". Communications of the ACM. ج. 21 ع. 12: 1040–1048. DOI:10.1145/359657.359665. S2CID:5638057.
  38. ↑ Ma، B.؛ Hero، A.؛ Gorman، J.؛ Michel، O. (2000). "Image registration with minimum spanning tree algorithm" (PDF). International Conference on Image Processing. ج. 1. ص. 481–484. DOI:10.1109/ICIP.2000.901000. مؤرشف (PDF) من الأصل في 2022-10-09.
  39. ↑ Suk، Minsoo؛ Song، Ohyoung (1 يونيو 1984). "Curvilinear feature extraction using minimum spanning trees". Computer Vision, Graphics, and Image Processing. ج. 26 ع. 3: 400–411. DOI:10.1016/0734-189X(84)90221-4.
  40. ↑ Tapia، Ernesto؛ Rojas، Raúl (2004). "Recognition of On-line Handwritten Mathematical Expressions Using a Minimum Spanning Tree Construction and Symbol Dominance" (PDF). Graphics Recognition. Recent Advances and Perspectives. Lecture Notes in Computer Science. Berlin Heidelberg: Springer-Verlag. ج. 3088. ص. 329–340. ISBN:978-3540224785. مؤرشف (PDF) من الأصل في 2022-10-09.
  41. ↑ Ohlsson، H. (2004). "Implementation of low complexity FIR filters using a minimum spanning tree". 12th IEEE Mediterranean Electrotechnical Conference (MELECON 2004). ج. 1. ص. 261–264. DOI:10.1109/MELCON.2004.1346826.
  42. ↑ Assunção، R. M.؛ M. C. Neves؛ G. Câmara؛ C. Da Costa Freitas (2006). "Efficient regionalization techniques for socio-economic geographical units using minimum spanning trees". International Journal of Geographical Information Science. ج. 20 ع. 7: 797–811. Bibcode:2006IJGIS..20..797A. DOI:10.1080/13658810600665111. S2CID:2530748. مؤرشف من الأصل في 2023-09-18.
  43. ↑ Devillers، J.؛ Dore، J.C. (1 أبريل 1989). "Heuristic potency of the minimum spanning tree (MST) method in toxicology". Ecotoxicology and Environmental Safety. ج. 17 ع. 2: 227–235. Bibcode:1989EcoES..17..227D. DOI:10.1016/0147-6513(89)90042-0. PMID:2737116.
  44. ↑ Mori، H.؛ Tsuzuki، S. (1 مايو 1991). "A fast method for topological observability analysis using a minimum spanning tree technique". IEEE Transactions on Power Systems. ج. 6 ع. 2: 491–500. Bibcode:1991ITPSy...6..491M. DOI:10.1109/59.76691.
  45. ↑ Filliben، James J.؛ Kafadar، Karen؛ Shier، Douglas R. (1 يناير 1983). "Testing for homogeneity of two-dimensional surfaces". Mathematical Modelling. ج. 4 ع. 2: 167–189. DOI:10.1016/0270-0255(83)90026-X.
  46. ↑ Kalaba، Robert E. (1963)، Graph Theory and Automatic Control (PDF)، مؤرشف من الأصل (PDF) في 2017-02-18

قراءة إضافية

روابط خارجية

هذه المقالة صادرة عن Wikipedia. النص متاح تحت رخصة المشاع الإبداعي - الإسناد - الترخيص بالمثل. قد تُطبَّق شروط إضافية على ملفات الوسائط.