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

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

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

## ملكيات

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

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

دليل:

# افترض العكس ، أي أن هناك MSTs مختلفة  و 
# نظرًا لأن  و  يختلفان على الرغم من احتوائهما على نفس العقد، فهناك على الأقل حافة واحدة تنتمي إلى أحدهما ولكن ليس إلى الآخر. ومن بين هذه الحواف، دع  تكون الحافة ذات الوزن الأقل؛ وهذا الاختيار فريد من نوعه لأن أوزان الحواف كلها مميزة. بدون فقدان العمومية، افترض أن  موجودة في 
# نظرًا لأن  عبارة عن MST،  يجب أن تحتوي على دورة  مع  .
# باعتبارها شجرة، لا تحتوي  على أي دورات، وبالتالي يجب أن يكون لدى  حافة  ليست في 
# نظرًا لأن  تم اختياره باعتباره الحافة ذات الوزن الأقل الفريدة بين تلك التي تنتمي إلى واحدة فقط من  و  ، فيجب أن يكون وزن  أكبر من وزن  .
# نظرًا لأن  و  جزء من الدورة  ، فإن استبدال  بـ  في  يؤدي إلى الحصول على شجرة ممتدة ذات وزن أصغر.
# وهذا يتناقض مع الافتراض القائل بأن  هو MST.

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

إذا كانت **الأوزان موجبة**، فإن **شجرة الامتداد الدنيا** تُعد في الواقع **رسمًا بيانيًا فرعيًا بأقل تكلفة** يربط بين جميع الرؤوس. يعود السبب في ذلك إلى أنه إذا احتوى الرسم البياني الفرعي على **(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**.

=== قطع الممتلكات ===
[[ملف:Msp-the-cut-correct.svg|تصغير|400x400بك| يوضح هذا الشكل خاصية القطع لـ MSTs.  هو MST الوحيد للرسم البياني المعطى. إذا كان  وبالتالي  فهناك 3 احتمالات للحافة عبر القطع  ، وهي الحواف  ،  ،  للرسم البياني الأصلي. وبعد ذلك، يكون e أحد حواف الوزن الأدنى للقطع، وبالتالي فإن } هو جزء من MST ]]
''بالنسبة لأي قطع (cut) C من الرسم البياني، إذا كان وزن الحافة e في مجموعة القطع C أصغر بشكل صارم من أوزان جميع الحواف الأخرى لمجموعة القطع C، فإن هذه الحافة e تنتمي إلى جميع أشجار الامتداد الدنيا (MSTs) للرسم البياني .''

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

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

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

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

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

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

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

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

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

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

الخوارزمية الثانية هي **خوارزمية بريم** ، التي اخترعها فويتش جارنيك عام 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).

الخوارزمية الرابعة، الأقل شيوعًا، هي  **(Reverse-Delete Algorithm)**، وهي عكس خوارزمية كروسكال. يبلغ وقت تشغيلها .

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

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

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

أسرع خوارزمية غير عشوائية تعتمد على المقارنة ذات التعقيد الزمني المعروف، والتي ابتكرها ، تعتمد على بنية بيانات تُعرف بـ**الكومة الناعمة (Soft Heap)**، وهي في الأساس قائمة انتظار ذات أولوية تقريبية .

يبلغ وقت تشغيل هذه الخوارزمية ، حيث α هي الدالة [[دالة أكرمان|المعكوس الوظيفي الكلاسيكي لدالة أكرمان]]. تنمو الدالة α ببطء شديد لدرجة أنها يمكن اعتبارها، لأغراض عملية، ثابتة لا تتجاوز القيمة 4. وهذا يعني أن خوارزمية شازيل تستغرق وقتًا يقترب جدًا من **الوقت الخطي**.

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

==== الرسوم البيانية الكثيفة ====
إذا كان الرسم البياني **كثيفًا** (أي m/n≥logloglogn)، فإن الخوارزمية الحتمية التي طورها فريدمان وتارجان تجد **شجرة الامتداد الدنيا (MST)** في وقت  . تنفذ هذه الخوارزمية عدة مراحل. تقوم كل مرحلة بتطبيق **خوارزمية بريم** عدة مرات، كل مرة لعدد محدود من الخطوات. وقت تشغيل كل مرحلة هو . إذا كان عدد الرؤوس قبل مرحلة ما هو n′، فإن عدد الرؤوس المتبقية بعد هذه المرحلة لا يتجاوز <math>\tfrac{n'}{2^{m/n'}}</math>. وبالتالي، لا يلزم سوى عدد قليل من المراحل، لا يتجاوز log∗n، مما يوفر وقت تشغيل خطيًا للرسوم البيانية الكثيفة.

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

==== أوزان الأعداد الصحيحة ====
إذا كانت أوزان الحواف عبارة عن أعداد صحيحة ممثلة في النظام الثنائي، فمن المعروف أن هناك خوارزميات حتمية تستطيع حل المشكلة في عمليات الأعداد الصحيحة بـ . ومع ذلك، تبقى مسألة ما إذا كان من الممكن حل المشكلة بشكل حتمي لرسم بياني عام في وقت خطي باستخدام خوارزمية تعتمد على المقارنة **سؤالًا مفتوحًا** حتى الآن.

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

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

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

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

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

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

* هناك <math>2^{r \choose 2}</math> رسوم بيانية مختلفة على رؤوس  .
* بالنسبة لكل رسم بياني، يمكن دائمًا العثور على MST باستخدام مقارنات  ، على سبيل المثال بواسطة [[خوارزمية بريم|خوارزمية Prim]] .
* ومن ثم، فإن عمق DT الأمثل أقل من  .
* ومن ثم، فإن عدد العقد الداخلية في DT الأمثل أقل من <math>2^{r^2}</math> .
* كل عقدة داخلية تقارن بين حافتين. عدد الحواف هو  على الأكثر، وبالتالي فإن العدد المختلف للمقارنات هو  على الأكثر.
* ومن ثم، فإن عدد DTs المحتملة أقل من

<math>{(r^4)}^{(2^{r^2})} = r^{2^{(r^2+2)}}.</math>

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

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

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

: <math>2^{r \choose 2} \cdot r^{2^{(r^2+2)}} \cdot (r^2+1)!,</math>

وهو أقل من

: <math>2^{2^{r^2+o(r)}}.</math>

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

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

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

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

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

== MST على الرسوم البيانية الكاملة ذات الأوزان العشوائية ==
أظهر  أنه في رسم بياني كامل ذي n رأس، حيث تمثل أوزان الحواف متغيرات عشوائية موزعة بشكل متطابق مع دالة التوزيع F التي تُرضي <math>F'(0) > 0</math>. عندما يقترب n من اللانهاية (+∞)، فإن الوزن المتوقع لشجرة الامتداد الدنيا (MST) يقترب من <math>\zeta(3)/F'(0)</math> حيث ζ هي [[دالة زيتا لريمان]] (وبشكل أكثر تحديدًا، ζ(3) هو [[ثابتة أبيري|ثابت أبيري]]).

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

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


== المتغير الكسري ==
توجد نسخة كسرية من **شجرة الامتداد الدنيا (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)** فهي تلك المجموعة الممتدة الكسرية التي يكون مجموعها <math>\sum_{e\in E} f(e)\cdot w(e)</math> هو الأصغر قدر الإمكان.

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

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

== متغيرات أخرى ==

* **شجرة شتاينر** لمجموعة فرعية من الرؤوس هي الشجرة الدنيا التي تمتد عبر المجموعة الفرعية المحددة. إن العثور على شجرة شتاينر هو [[مسألة كثيرة حدود غير قطعية كاملة|NP-كامل]] .
* **شجرة الامتداد الدنيا (k-MST)** هي الشجرة التي تمتد عبر مجموعة فرعية من k رأس في الرسم البياني بأقل وزن ممكن.
* **مجموعة من أشجار الامتداد الـ k الأصغر** هي مجموعة فرعية من k شجرة امتداد (من بين جميع أشجار الامتداد الممكنة) بحيث لا توجد شجرة امتداد خارج هذه المجموعة ذات وزن أصغر . (لاحظ أن هذه المشكلة لا علاقة لها بشجرة الامتداد الدنيا k-MST).
* **شجرة الامتداد الدنيا الإقليدية (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 تُنتج حلولًا قريبة من الأمثل في وقت متعدد الحدود.
* **شجرة الامتداد الدنيا ذات القيود الدرجية (Degree-constrained minimum spanning tree)** هي شجرة امتداد دنيا حيث يكون كل رأس متصلًا بما لا يزيد عن d رأس أخرى، لعدد d مُعطى. تعتبر الحالة d=2 حالة خاصة من مشكلة البائع المتجول، لذا فإن شجرة الامتداد الدنيا المقيدة بالدرجة هي **NP-hard** بشكل عام.
* **الشجرة الجذرية (Arborescence)** هي نوع مختلف من شجرة الامتداد الدنيا للرسوم البيانية الموجهة. يمكن حلها في وقت O(E+VlogV) باستخدام خوارزمية Chu–Liu/Edmonds.
* **شجرة الامتداد القصوى (Maximum spanning tree)** هي شجرة امتداد يكون وزنها أكبر من أو يساوي وزن أي شجرة امتداد أخرى. يمكن إيجاد مثل هذه الشجرة باستخدام خوارزميات مثل بريم أو كروسكال بعد ضرب أوزان الحواف بـ -1 وحل مشكلة شجرة الامتداد الدنيا على الرسم البياني الجديد. المسار في شجرة الامتداد القصوى هو أوسع مسار في الرسم البياني بين نقطتي نهايته: من بين جميع المسارات الممكنة، فإنه يعظم وزن الحافة الأقل وزنًا. تجد أشجار الامتداد القصوى تطبيقات في خوارزميات التحليل اللغوي الطبيعي  وفي خوارزميات تدريب الحقول العشوائية الشرطية.
* **مشكلة شجرة الامتداد الدنيا الديناميكية (Dynamic MST problem)** تتعلق بتحديث شجرة امتداد دنيا تم حسابها مسبقًا بعد تغيير وزن حافة في الرسم البياني الأصلي أو إدخال/حذف رأس .
* **مشكلة شجرة الامتداد الدنيا ذات التسمية الدنيا (Minimum labeling spanning tree problem)** تهدف إلى إيجاد شجرة امتداد بأقل عدد من أنواع التسميات إذا كانت كل حافة في الرسم البياني مرتبطة بتسمية من مجموعة تسميات محدودة بدلاً من وزن.
* **حافة الاختناق (Bottleneck edge)** هي الحافة ذات الوزن الأعلى في شجرة امتداد. تُعتبر شجرة الامتداد **شجرة امتداد دنيا ذات اختناق (MBST)** إذا لم يحتوي الرسم البياني على شجرة امتداد ذات وزن حافة اختناق أصغر. شجرة الامتداد الدنيا (MST) هي بالضرورة شجرة امتداد دنيا ذات اختناق (MBST) (يمكن إثبات ذلك بخاصية القطع)، ولكن شجرة الامتداد الدنيا ذات الاختناق (MBST) ليست بالضرورة شجرة امتداد دنيا (MST).
* **لعبة شجرة الامتداد الدنيا ذات التكلفة الأدنى (Minimum-cost spanning tree game)** هي لعبة تعاونية يتعين على اللاعبين فيها تقاسم تكاليف بناء شجرة الامتداد المثلى فيما بينهم.
* **مشكلة تصميم الشبكة الأمثل (Optimal network design problem)** هي مشكلة حساب مجموعة، تخضع لقيود الميزانية، تحتوي على شجرة امتداد، بحيث يكون مجموع أقصر المسارات بين كل زوج من العقد أصغر ما يمكن.

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

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

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

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

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

== مراجع ==




== قراءة إضافية ==

* [http://citeseer.ist.psu.edu/nesetril00otakar.html أوتاكار بوروفكا حول مشكلة الحد الأدنى من الشجرة الممتدة (ترجمة كل من ورقات عام 1926، والتعليقات، والتاريخ) (2000)] ياروسلاف نيسيتريل ، إيفا ميلكوفا، هيلينا نيستريلوفا. (يقدم القسم 7 خوارزميته، والتي تبدو وكأنها مزيج بين خوارزمية بريم وخوارزمية كروسكال.)
* توماس هـ. كورمين ، وتشارلز إي. ليسرسون ، [[رونالد ريفست|ورونالد إل. ريفست]] ، [[كليفورد شتاين|وكليفورد ستاين]] . *مقدمة في الخوارزميات'' ، الطبعة الثانية. MIT Press و McGraw-Hill، 2001.رقم ISBN&nbsp;0-262-03293-7 . الفصل 23: أشجار الامتداد الدنيا، ص.&nbsp;561–579.
* آيزنر، جيسون (1997). خوارزميات حديثة لأشجار الامتداد الدنيا: مناقشة تعليمية . مخطوطة، جامعة بنسلفانيا، أبريل. 78 صفحة
* كرومكوفسكي، جون ديفيد. "لم تنصهر بعد كل هذه السنوات"، في الإصدارات السنوية، العلاقات العرقية والإثنية، الطبعة 17 (2009 ماكجرو هيل) (باستخدام شجرة الامتداد الدنيا كطريقة للتحليل الديموغرافي للتنوع العرقي في جميع أنحاء الولايات المتحدة).

## روابط خارجية

* تم تنفيذه في BGL، مكتبة Boost Graph
* مستودع خوارزميات ستوني بروك - أكواد شجرة الامتداد الدنيا
* تم تنفيذه في QuickGraph لـ . شبكة

تصنيف:شجرة الامتداد