hotchpotch/wikipedia-multilingual-ir-pairs huggingface dataset:
الشجرة الممتدة ذات الوزن الأدنى ملكيات
وإذا كان هناك n رأسًا في الرسم البياني ، فإن كل شجرة ممتدة تحتوي على n − 1 حافة.
قد يوجد عدد من أشجار الامتداد الدنيا التي تحمل الوزن الإجمالي نفسه. وبشكل خاص، إذا كانت جميع أوزان حواف الرسم البياني متساوية، فإن كل شجرة ممتدة في هذا الرسم البياني ستكون بالضرورة شجرة امتداد دنيا.
إذا كان لكل حافة وزن مميز، فستكون هناك شجرة امتداد دنيا واحدة وفريدة فقط. هذا ينطبق على العديد من السيناريوهات الواقعية، مثل مثال شركة الاتصالات المذكور سابقًا، حيث من غير المرجح أن يكون لمسارين نفس التكلفة تمامًا. هذا المبدأ ينطبق أيضًا على الغابات الممتدة.
نظرًا لأن A و B يختلفان على الرغم من احتوائهما على نفس العقد، فهناك على الأقل حافة واحدة تنتمي إلى أحدهما ولكن ليس إلى الآخر. ومن بين هذه الحواف، دع e1 تكون الحافة ذات الوزن الأقل؛ وهذا الاختيار فريد من نوعه لأن أوزان الحواف كلها مميزة. بدون فقدان العمومية، افترض أن e1 موجودة في A
الشجرة الممتدة ذات الوزن الأدنى ملكيات
بشكل عام، إذا لم تكن أوزان الحواف كلها مميزة، فإن مجموعة الأوزان (المتعددة) في الأشجار ذات الامتداد الأدنى ستكون فريدة بالتأكيد؛ أي أنها ستكون متماثلة لجميع الأشجار ذات الامتداد الأدنى الممكنة [1].
إذا كانت الأوزان موجبة، فإن شجرة الامتداد الدنيا تُعد في الواقع رسمًا بيانيًا فرعيًا بأقل تكلفة يربط بين جميع الرؤوس. يعود السبب في ذلك إلى أنه إذا احتوى الرسم البياني الفرعي على <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.
بالنسبة لأي قطع (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 للرسم البياني قبل عملية الانكماش .
الشجرة الممتدة ذات الوزن الأدنى الخوارزميات
في جميع الخوارزميات المذكورة أدناه، يُمثل m عدد الحواف في الرسم البياني، بينما يُمثل n عدد الرؤوس.
تم تطوير أول خوارزمية للعثور على شجرة الامتداد الدنيا (MST) بواسطة العالم التشيكي أوتاكار بوروفكا في عام 1926، وتُعرف اليوم باسم خوارزمية بوروفكا. كان الهدف من هذه الخوارزمية هو توفير تغطية كهربائية فعالة لمنطقة مورافيا.
تُنفذ الخوارزمية على مراحل متتالية، تُسمى كل منها خطوة بوروفكا. في كل خطوة، تُحدد غابة F تتكون من الحافة ذات الوزن الأدنى المرتبطة بكل رأس في الرسم البياني G. بعد ذلك، يُشكل الرسم البياني الجديد G1 = G \ F ليكون مدخلًا للخطوة التالية. يُشير الرمز G \ F هنا إلى الرسم البياني الناتج عن تقليص (انكماش) الحواف الموجودة في الغابة F. بفضل خاصية القطع (Cut Property)، تنتمي هذه الحواف المُقلَّصة إلى شجرة الامتداد الدنيا (MST).
تستغرق كل خطوة من خطوات بوروفكا وقتًا خطيًا (O(V) أو O(E)، اعتمادًا على طريقة التنفيذ). نظرًا لأن عدد الرؤوس ينخفض إلى النصف على الأقل في كل خطوة، فإن خوارزمية بوروفكا تستغرق وقتًا إجماليًا قدره (O(m log n)).
الشجرة الممتدة ذات الوزن الأدنى الخوارزميات
الخوارزمية الثانية هي خوارزمية بريم ، التي اخترعها فويتش جارنيك عام 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)
الشجرة الممتدة ذات الوزن الأدنى الخوارزميات
أسرع خوارزمية غير عشوائية تعتمد على المقارنة ذات التعقيد الزمني المعروف، والتي ابتكرها <b>برنارد شازيل</b>، تعتمد على بنية بيانات تُعرف بـالكومة الناعمة (Soft Heap)، وهي في الأساس قائمة انتظار ذات أولوية تقريبية .
يبلغ وقت تشغيل هذه الخوارزمية O(m α(m,n))، حيث α هي الدالة المعكوس الوظيفي الكلاسيكي لدالة أكرمان. تنمو الدالة α ببطء شديد لدرجة أنها يمكن اعتبارها، لأغراض عملية، ثابتة لا تتجاوز القيمة 4. وهذا يعني أن خوارزمية شازيل تستغرق وقتًا يقترب جدًا من الوقت الخطي.
إذا كان الرسم البياني كثيفًا (أي m/n≥logloglogn)، فإن الخوارزمية الحتمية التي طورها فريدمان وتارجان تجد شجرة الامتداد الدنيا (MST) في وقت O(m) . تنفذ هذه الخوارزمية عدة مراحل. تقوم كل مرحلة بتطبيق خوارزمية بريم عدة مرات، كل مرة لعدد محدود من الخطوات. وقت تشغيل كل مرحلة هو O(m + n). إذا كان عدد الرؤوس قبل مرحلة ما هو n′، فإن عدد الرؤوس المتبقية بعد هذه المرحلة لا يتجاوز . وبالتالي، لا يلزم سوى عدد قليل من المراحل، لا يتجاوز log∗n، مما يوفر وقت تشغيل خطيًا للرسوم البيانية الكثيفة.
الشجرة الممتدة ذات الوزن الأدنى الخوارزميات
ان هناك خوارزميات أخرى تعمل في وقت خطي على الرسوم البيانية الكثيفة .
إذا كانت أوزان الحواف عبارة عن أعداد صحيحة ممثلة في النظام الثنائي، فمن المعروف أن هناك خوارزميات حتمية تستطيع حل المشكلة في عمليات الأعداد الصحيحة بـ O(m + n). ومع ذلك، تبقى مسألة ما إذا كان من الممكن حل المشكلة بشكل حتمي لرسم بياني عام في وقت خطي باستخدام خوارزمية تعتمد على المقارنة سؤالًا مفتوحًا حتى الآن.
عند التعامل مع رسم بياني G ثابت العقد والحواف ولكن بأوزان غير معروفة، يمكننا بناء شجرة قرار ثنائية (DT) لتحديد شجرة الامتداد الدنيا (MST) بغض النظر عن ترتيب الأوزان.
إن تعقيد وقت تشغيل شجرة القرار الثنائية هو ببساطة عمقها، وهو أكبر عدد من الاستعلامات اللازمة لإيجاد الـ MST. تُعد شجرة القرار الثنائية للرسم البياني G "مثلى" إذا كان لها أقل عمق ممكن بين جميع أشجار القرار الثنائية الصحيحة لـ G.
بالنسبة لأي عدد صحيح r، يمكن العثور على أشجار قرار مثلى لجميع الرسوم البيانية التي تحتوي على r رؤوس عن طريق لبحث بالقوة الغاشمة (Brute-force search). يتم هذا البحث على خطوتين.
الشجرة الممتدة ذات الوزن الأدنى الخوارزميات
ب. تحديد : DTs الصحيحة للتأكد من صحة DT، يجب التحقق منها على جميع التباديل الممكنة لأوزان الحافة .
فإن إجمالي الوقت المطلوب لإيجاد DT الأمثل لجميع الرسوم البيانية التي تحتوي على r رؤوس هي :
لقد ابتكر سيث بيتي وفيجايا راماشاندران خوارزمية شجرة الامتداد الدنيا (MST) حتمية تعتمد على المقارنة، وقد تم إثبات صحتها. فيما يلي وصف مبسط لهذه الخوارزمية.
قم بإضافة الحواف التالفة إلى الغابة الناتجة لتشكيل رسم بياني فرعي مضمون لاحتواء الحد الأدنى من الشجرة الممتدة، وأصغر بعامل ثابت من الرسم البياني الأولي. قم بتطبيق الخوارزمية المثلى بشكل متكرر على هذا الرسم البياني.
إن وقت تشغيل جميع خطوات الخوارزمية هو O(m)، باستثناء الخطوة التي تستخدم أشجار القرار. وقت تشغيل هذه الخطوة غير معروف، لكن ثبت أنها الخطوة المثالية؛ فلا يمكن لأي خوارزمية أن تتفوق على شجرة القرار المثالية. بالتالي، تتمتع هذه الخوارزمية بخاصية فريدة: فهي مثالية بشكل مثبت، على الرغم من أن تعقيد وقت تشغيلها لم يُحدد بعد.
تناولت الأبحاث أيضًا الخوارزميات المتوازية لمشكلة شجرة الامتداد الدنيا (MST). باستخدام عدد خطي من المعالجات، يمكن حل المشكلة في وقت O(log n).
يمكن أيضًا التعامل مع مشكلة شجرة الامتداد الدنيا (MST) ببطريقة موزعة. فإذا اعتبرنا كل عقدة بمثابة جهاز كمبيوتر، ولا تملك أي عقدة معلومات سوى عن الروابط المتصلة بها مباشرةً، فإنه يظل بالإمكان حساب <b>شجرة الامتداد الدنيا الموزعة</b>(Distributed Minimum Spanning Tree).
الشجرة الممتدة ذات الوزن الأدنى MST على الرسوم البيانية الكاملة ذات الأوزان العشوائية
أظهر <b>آلان م. فريز</b> أنه في رسم بياني كامل ذي n رأس، حيث تمثل أوزان الحواف متغيرات عشوائية موزعة بشكل متطابق مع دالة التوزيع F التي تُرضي . عندما يقترب n من اللانهاية (+∞)، فإن الوزن المتوقع لشجرة الامتداد الدنيا (MST) يقترب من  حيث ζ هي دالة زيتا لريمان (وبشكل أكثر تحديدًا، ζ(3) هو ثابت أبيري).
وقد أثبت فريز وستيل أيضًا التقارب في الاحتمالات لهذه القيمة. كما أثبت سفانتي جانسون نظرية الحد المركزي لوزن شجرة الامتداد الدنيا (MST).
بالنسبة للأوزان العشوائية الموحدة في النطاق ، تم حساب الحجم الدقيق المتوقع لشجرة الامتداد الدنيا (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) فهي تلك المجموعة الممتدة الكسرية التي يكون مجموعها  هو الأصغر قدر الإمكان.
الشجرة الممتدة ذات الوزن الأدنى المتغير الكسري
إذا تم تقييد الكسور 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 لكل حافة من دورات هاميلتون.
الشجرة الممتدة ذات الوزن الأدنى متغيرات أخرى
مجموعة من أشجار الامتداد الـ k الأصغر هي مجموعة فرعية من k شجرة امتداد (من بين جميع أشجار الامتداد الممكنة) بحيث لا توجد شجرة امتداد خارج هذه المجموعة ذات وزن أصغر . (لاحظ أن هذه المشكلة لا علاقة لها بشجرة الامتداد الدنيا k-MST).
شجرة الامتداد الدنيا الموزعة (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 بشكل عام.
شجرة الامتداد القصوى (Maximum spanning tree) هي شجرة امتداد يكون وزنها أكبر من أو يساوي وزن أي شجرة امتداد أخرى. يمكن إيجاد مثل هذه الشجرة باستخدام خوارزميات مثل بريم أو كروسكال بعد ضرب أوزان الحواف بـ -1 وحل مشكلة شجرة الامتداد الدنيا على الرسم البياني الجديد. المسار في شجرة الامتداد القصوى هو أوسع مسار في الرسم البياني بين نقطتي نهايته: من بين جميع المسارات الممكنة، فإنه يعظم وزن الحافة الأقل وزنًا. تجد أشجار الامتداد القصوى تطبيقات في خوارزميات التحليل اللغوي الطبيعي  وفي خوارزميات تدريب الحقول العشوائية الشرطية.
الشجرة الممتدة ذات الوزن الأدنى متغيرات أخرى
مشكلة شجرة الامتداد الدنيا ذات التسمية الدنيا (Minimum labeling spanning tree problem) تهدف إلى إيجاد شجرة امتداد بأقل عدد من أنواع التسميات إذا كانت كل حافة في الرسم البياني مرتبطة بتسمية من مجموعة تسميات محدودة بدلاً من وزن.
حافة الاختناق (Bottleneck edge) هي الحافة ذات الوزن الأعلى في شجرة امتداد. تُعتبر شجرة الامتداد شجرة امتداد دنيا ذات اختناق (MBST) إذا لم يحتوي الرسم البياني على شجرة امتداد ذات وزن حافة اختناق أصغر. شجرة الامتداد الدنيا (MST) هي بالضرورة شجرة امتداد دنيا ذات اختناق (MBST) (يمكن إثبات ذلك بخاصية القطع)، ولكن شجرة الامتداد الدنيا ذات الاختناق (MBST) ليست بالضرورة شجرة امتداد دنيا (MST).
مشكلة تصميم الشبكة الأمثل (Optimal network design problem) هي مشكلة حساب مجموعة، تخضع لقيود الميزانية، تحتوي على شجرة امتداد، بحيث يكون مجموع أقصر المسارات بين كل زوج من العقد أصغر ما يمكن.
الشجرة الممتدة ذات الوزن الأدنى التطبيقات
للأشجار ذات الامتداد الأدنى (MSTs) تطبيقات مباشرة في تصميم الشبكات، بما في ذلك شبكات الكمبيوتر ،وشبكات الاتصالات، وشبكات النقل، وشبكات إمدادات المياه، والشبكات الكهربائية (التي اختُرعت لأجلها في الأصل، كما ذكرنا سابقًا).
تُستدعى هذه الأشجار أيضًا كبرامج فرعية (subroutines) في خوارزميات لحل مشكلات أخرى، ومنها:
تُستخدم أشجار الامتداد الدنيا (MSTs) في مجموعة واسعة من التطبيقات العملية، منها:
يمكن أيضًا استخدام أشجار الامتداد الدنيا لوصف الأسواق المالية. يمكن إنشاء مصفوفة الارتباط عن طريق حساب معامل الارتباط بين أي سهمين. يمكن تمثيل هذه المصفوفة طوبولوجيًا كشبكة معقدة ويمكن إنشاء شجرة امتدادية دنيا لتوضيح العلاقات.
الشجرة الممتدة ذات الوزن الأدنى قراءة إضافية
أوتاكار بوروفكا حول مشكلة الحد الأدنى من الشجرة الممتدة (ترجمة كل من ورقات عام 1926، والتعليقات، والتاريخ) (2000) ياروسلاف نيسيتريل ، إيفا ميلكوفا، هيلينا نيستريلوفا. (يقدم القسم 7 خوارزميته، والتي تبدو وكأنها مزيج بين خوارزمية بريم وخوارزمية كروسكال.)
توماس هـ. كورمين ، وتشارلز إي. ليسرسون ، ورونالد إل. ريفست ، وكليفورد ستاين . مقدمة في الخوارزميات ، الطبعة الثانية. MIT Press و McGraw-Hill، 2001.(ردمك 0-262-03293-7)رقم ISBN 0-262-03293-7 . الفصل 23: أشجار الامتداد الدنيا، ص. 561–579.
كرومكوفسكي، جون ديفيد. "لم تنصهر بعد كل هذه السنوات"، في الإصدارات السنوية، العلاقات العرقية والإثنية، الطبعة 17 (2009 ماكجرو هيل) (باستخدام شجرة الامتداد الدنيا كطريقة للتحليل الديموغرافي للتنوع العرقي في جميع أنحاء الولايات المتحدة).
الإيرانيون في لبنان
الإيرانيون في لبنان هم السكان من أصول إيرانية المقيمون في لبنان. بعضهم مواطنون لبنانيون وبعضهم مهاجرون أو من أصل إيراني ولدوا في لبنان. يعيش العديد من الإيرانيين في النبطية جنوب لبنان.  يعمل العديد من الإيرانيين في لبنان في تجارة السجاد.
ووهان جيانغدا
نادي جامعة جيانغهان في ووهان لكرة القدم (بالصينية: 武汉江汉大学足球俱乐部) المعروف كذلك باسم ووهان جيانغدا (بالصينية: 武汉江大) هو نادِ كرة قدم صيني للسيدات من مدينة ووهان. وينافس حالياً في دوري السوبر الصيني للسيدات. تأسس النادي عام 2001 بموجب الشراكة بين جامعة جيانغهان واتحاد ووهان لكرة القدم.
في عام 2025 حقق ووهان جيانغدا أول ألقابه القارية بتتويجه بلقب دوري أبطال آسيا للسيدات بعد فوزه في النهائي على ملبورن سيتي بركلات الترجيح 5-4 بعد التعادل في الوقتين الأصلي والإضافي 1-1.
العرب الفرس
العرب الفرس (الفارسية: عرب های پارسی) هم أشخاص من أصول عرب وفارسية مختلطة. تاريخياً، كانت الزيجات بين العرب والفرس شائعة في إيران الكويت العراق البحرين، وكذلك في لبنان سوريا، وإن كان بدرجة أقل.
العرب الفرس التاريخ
في شبه الجزيرة العربية قبل الإسلام، عاش العديد من العرب في المجال الثقافي لبلاد فارس، وبالتالي استخدموا اللغة الفارسية لغةً مكتوبة لهم. أُشير إلى هؤلاء باسم العرب الفرس. في عهد الإمبراطورية الساسانية، كان هناك مجتمع عربي فارسي بارز يُدعى "الأبناء". يشير المصطلح إلى أي شخص ولد لأمٍ عربية وأبٍ فارسي في خضم الحروب الحبشية الفارسية؛ وكان من الشائع بشكلٍ خاص أن يتزوج الجنود الفرس من النساء العربيات خلال هذا الوقت، حيث كان الجيش الساساني محاصراً في جميع أنحاء جنوب شبه الجزيرة العربية من أجل صد إمبراطورية الأكسوميين من المنطقة.
في فترة انتشار الإسلام في الجزيرة العربية، برز الصحابي سلمان الفارسي، وكان فارسياً عرقياً من رامهرمز . كان في الأصل زرادشتياً ، وكان مسيحياً عندما التقى محمد في مدينة يثرب.  وبعد أن صادق محمداً، اعتنق الإسلام ، فأصبح من أبرز الصحابة غير العرب.
العرب الفرس التاريخ
بعد الفتح الإسلامي لبلاد فارس، بدأ الفرس بدورهم في استخدام اللغة العربية لغةً مكتوبةً إلى جانب اللغة الفارسية. كان العديد من العلماء والفلاسفة المسلمين المشهورين في عهد الخلافة العباسية من الفرس الذين كتبوا أعمالهم العلمية باللغة العربية بينما استمروا في كتابة الأعمال الأدبية والشعر باللغة الفارسية - من أبرزهم ابن سينا وعمر الخيام .
العرب الفرس التعريف
نادراً ما يستخدم مصطلح "عربي فارسي" وصفاً لذاته. يميل معظم الأشخاص إلى تحديد هويتهم على أنهم إما فارسيون أو عرب، ويعتبرون أنفسهم أعضاء في مجموعة عرقية واحدة فقط، ولكنهم في الوقت نفسه يدركون خلفيتهم المختلطة. بالنسبة للعديد من الأشخاص، فإن العامل الأكثر أهمية في تحديد هويتهم هو الدولة ذات السيادة التي يعيشون فيها أو التي جاء منها أسلافهم الحديثون.
العرب الفرس المجتمعات
يعيش العرب والمتحدثون باللغة العربية جنباW إلى جنب مع الفرس بشكل أساسي في مناطق خوزستان وبوشهر وهرمزجان وخراسان في إيران. توجد علاقات زواج مختلط بين العرب الإيرانيين والفرس الإيرانيين.   يوجد أكثر من مليون سيد إيراني من أصل عربي، لكن معظمهم فارسيون ومختلطون ويعتبرون أنفسهم فارسيين وإيرانيين اليوم.  هاجر أغلب السادة إلى إيران من البلاد العربية بشكل رئيسي في القرنين الخامس عشر والسابع عشر خلال العصر الصفوي . عمل الصفويون على تغيير المشهد الديني في إيران من خلال فرض المذهب الشيعي الإثني عشري على السكان. وبما أن معظم السكان اعتنقوا الإسلام السني، وكانت النسخة المتعلمة من المذهب الشيعي نادرة في إيران في ذلك الوقت، فقد استورد إسماعيل الصفوي مجموعة جديدة منعلماء الشيعة الذين كانوا في الغالب من السادة من المراكز الشيعية التقليدية في الأراضي الناطقة بالعربية، مثل جبل عامل (في جنوب لبنان)، وسوريا ، والبحرين ، وجنوب العراق للمساعدة على إيجاد رجال دين للدولة. عرض عليهم الصفويون الأرض والمال مقابل الولاء.
العرب الفرس المجتمعات
تعود الهجرة الفارسية إلى البحرين إلى أيام الإمبراطورية الفارسية الساسانية والأخمينية، على الرغم من وجود هجرة مستمرة في العصر الحديث منذ مئات السنين.  هجرة الشيعة الناطقين بالفارسية إلى البحرين دائمة.
عام 1910، موّلت الجالية الفارسية مدرسة خاصة هي مدرسة الاتحاد، وكانت تدرس اللغة الفارسية إلى جانب مواد أخرى.  وفي سوق المنامة ، كان العديد من الفرس يتجمعون في حي مشبير. ومع ذلك فقد استوطنوا في مناطق أخرى مع تطور المدن الجديدة وتوسع القرى في عهد عيسى بن سلمان آل خليفة. واليوم، يتمركز عدد كبير منهم في المناطق الشيعية في المحرق والمدن الشيعية الحديثة في جزيرة البحرين .
في سبعينيات القرن العشرين، نفى صدام حسين ما بين 350 ألفاً إلى 650 ألفًا من العراقيين الشيعة من أصل إيراني (ويطلق عليهم أيضاً العجم ).  الفرس العراقيون يتبعون المذهب الشيعي. للفرس تاريخ طويل في العراق، يعود تاريخه إلى ما قبل الفتح الإسلامي لفارس في القرن السابع.
العرب الفرس المجتمعات
الخليط العربي الفارسي شائع في الواقع بين الشيعة اللبنانيين، وقد انتهى الأمر بالعديد من الإيرانيين في لبنان واللبنانيين في إيران إلى الزواج من بعضهم البعض والاستقرار. يختلط العديد من المسلمين الشيعة البارزين من لبنان بالفرس.
في سوريا ، يوجد مجتمع صغير من العرب الفرس في المناطق ذات الأغلبية العلوية/النصيرية، معظمهم في اللاذقية وطرطوس ، والباقي في دمشق .
محمد الشيخ سليمان
محمد الشيخ سليمان رجل أعمال فلسطيني ومربي خيول بارز، وُلد في الناصرة ، فلسطين ، وهو رجل أعمال فلسطيني وومربي خيول. في عام 2022، حاز على لقب "أفضل رجل أعمال لهذا العام" من قِبل "جوائز المهرجانات العربية الدولية المتميزة ".
محمد الشيخ سليمان الحياة المبكرة والتعليم
أكمل محمد الشيخ سليمان تعليمه الابتدائي والثانوي في مدرسة الراهبات الفرنسيسكانيات بالناصرة. بعد ذلك، التحق بالجامعة وحصل على درجة في إدارة الأعمال والإدارة العامة، وتخرج عام 2015.
حصل سليمان على درجة البكالوريوس في الاقتصاد وإدارة الأعمال من الجامعة المفتوحة .  بعد ذلك، تابع دراسته العليا في العلوم السياسية والعلاقات الدولية . وهو الآن في طور إكمال درجة الماجستير في الاقتصاد وإدارة الأعمال من جامعة إسطنبول بتركيا .
محمد الشيخ سليمان حياة مهنية
بدأ سليمان مسيرته المهنية بتأسيس شركته العقارية الخاصة، الشيخ للعقارات. عملت هذه الشركة في مجال بناء وتجديد الفنادق.
م في عام 2016، دخل سليمان مجال تربية الخيول العربية وأسس مزرعة الشيخ. حققت المزرعة إنجازًا لافتًا بفوزها بـبببطولة العالم للخيول العربية لعامين متتاليين، في عامي 2018 و2019 .
وفي عام 2022م،استقبل وفداً من نادي هلال القدس في القدس.
خليل رباح
خليل رباح، من مواليد عام 1961، هو فنان تشكيلي فلسطيني متعدد التخصصات، وقيّم فني، ومعلم. يشتهر بأعماله الفنية التركيبية المفاهيمية التي تركز على إعادة كتابة التاريخ. يعيش رباح حاليًا في رام الله ، الضفة الغربية
خليل رباح الحياة والمهنة
لقد وُلِد خليل رباح عام 1961 في مدينه القدس. تخرج من جامعة تكساس في أرلينجتون .
خليل رباح هو مؤسس مشروع المتحف الفلسطيني للتاريخ الطبيعي والبشرية، ومؤسس مشارك لـلمؤسسة المعمل للفن المعاصر في القدس، وأحد مؤسسي مدرسة الفن فلسطين في لندن . منذ عام 2005، يتولى رباح منصب مدير بينالي رواق في رام الله
قام خليل رباح بالتدريس في أكاديمية بتسلئيل للفنون والتصميم من عام 1997 إلى عام 2000 ؛ وايضا قام بالتدريس في جامعة بيرزيت .
في عام 2002، تم حصوله على منحة لينونو للسلام .
نادي ليمنجتون
نادي ليامينغتون لكرة القدم هو نادٍ رياضي يقع في مدينة ليامينغتون سبا بمقاطعة وركشير في إنجلترا. يشارك الفريق حالياً في دوري الدرجة الوطنية الشمالية، ويُقام مبارياته على ملعب نيو ويندميل الواقع بالقرب من منطقة بيشوبز تاشبروك.
نادي ليمنجتون تاريخ النادي
تأسس النادي عام 1933 كفريق عمل لشركة لوكهيد بورغ آند بيك، واكتسب لقب “الفرامل” نسبةً إلى المنتجات التي تصنعها الشركة. بدأ الفريق اللعب في دوري ووريك والمنطقة، قبل أن ينضم إلى دوري كوفنتري ووركس لموسم 1934–35. في عام 1940 انتقل النادي إلى دوري ليمينغتون والمنطقة، لكنه عاد بعد عامين إلى دوري كوفنتري ووركس. في عام 1944 انضم إلى دوري كوفنتري والمنطقة. وفي عام 1947 غُيّر اسم النادي إلى “لوكهيد ليمينغتون” عند انضمامه إلى دوري الهواة المركزي. بعد تحقيق المركز الثالث مرتين، انضم النادي إلى دوري برمنغهام كومبينيشن عام 1949. في عام 1954 أُلغِي الدوري، فانضم ليمينغتون، كمعظم الأندية، إلى دوري برمنغهام والمنطقة. شارك في القسم الجنوبي لموسم انتقالي، وحل وصيفاً له، مما أهلّه للمشاركة في القسم الأول في الموسم التالي. في عام 1960 تم تقليص الدوري إلى قسم واحد، وفاز النادي بلقب البطولة موسم 1961–62.