شجرة ذات امتدادات دنيا

في نظرية الرسوم البيانية ، تُعرَّف الشجرة الممتدة الدنيا ( MST ) أو الشجرة الممتدة ذات الوزن الأدنى بأنها مجموعة فرعية من حواف رسم بياني غير موجه متصل وموزون الحواف ، تربط جميع الرؤوس معًا دون أي دورات وبأقل وزن إجمالي ممكن للحواف. ^[¹^] أي أنها شجرة ممتدة يكون مجموع أوزان حوافها أصغر ما يمكن. ^[²^] وبشكل أعم، فإن أي رسم بياني غير موجه وموزون الحواف (ليس بالضرورة متصلًا) له غابة ممتدة دنيا ، وهي عبارة عن اتحاد الأشجار الممتدة الدنيا لمكوناته المتصلة .

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

ملكيات

تعدد محتمل

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

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

رجل فريد

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

دليل:

لنفترض العكس ، أي أن هناك شجرتين امتداديتين مختلفتين $A$ و $B.$
بما أن المجموعتين $A$ و $B$ مختلفتان رغم احتوائهما على نفس العقد، فهناك على الأقل حافة واحدة تنتمي إلى إحداهما دون الأخرى. من بين هذه الحواف، لنفترض أن $e1$ هي $الحافة$ ذات الوزن الأقل؛ هذا الاختيار فريد لأن أوزان الحواف جميعها مختلفة. دون الإخلال بعمومية المسألة، نفترض أن $e1$ $تنتمي$ إلى $A.$
بما أن $B$ عبارة عن شجرة امتداد دنيا، فإن ${e 1} \cup B$ يجب أن تحتوي على دورة $C$ مع $e 1$ .
باعتبارها شجرة، لا تحتوي $A$ على دورات، لذلك يجب أن تحتوي $C$ على حافة $e 2$ غير موجودة في $A.$
بما أن $e 1$ تم اختيارها كحافة فريدة ذات وزن أقل من بين تلك التي تنتمي إلى واحدة فقط من $A$ و $B$ ، فإن وزن $e 2$ يجب أن يكون أكبر من وزن $e 1$ .
بما أن $e 1$ و $e 2$ جزء من الدورة $C$ ، فإن استبدال $e 2$ بـ $e 1$ في $B$ ينتج عنه شجرة ممتدة بوزن أصغر.
وهذا يتناقض مع الافتراض القائل بأن $B$ عبارة عن شجرة امتداد أدنى.

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

الرسم البياني الفرعي ذو التكلفة الدنيا

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

خاصية الدورة

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

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

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

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

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

البرهان: لنفترض وجود شجرة امتداد دنيا $T$ لا تحتوي على $e$ . إضافة $e$ إلى $T$ ستُنتج دورةً تعبر القطع مرةً واحدةً عند $e$ ثم تعبر مرةً أخرى عند حافة $e'$ . بحذف $e'$ نحصل على شجرة امتداد $T ∖{e'} \cup {e}$ ذات وزن أصغر تمامًا من $T.$ هذا يُناقض الافتراض بأن $T$ كانت شجرة امتداد دنيا.

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

ميزة التكلفة المنخفضة

إذا كانت الحافة ذات التكلفة الدنيا $e$ في الرسم البياني فريدة، فإن هذه الحافة يتم تضمينها في أي شجرة امتداد دنيا.

البرهان: إذا لم يتم تضمين $e$ في MST، فإن إزالة أي من الحواف (الأكثر تكلفة) في الدورة المتكونة بعد إضافة $e$ إلى MST، سيؤدي إلى شجرة ممتدة ذات وزن أصغر.

انقباض

إذا كانت $T$ شجرة من حواف MST، فيمكننا اختزال $T$ إلى رأس واحد مع الحفاظ على الثابت القائل بأن MST للرسم البياني المختزل بالإضافة إلى $T$ يعطي MST للرسم البياني قبل الاختزال. ^{[ 4 ]}

الخوارزميات

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

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

طُوِّرت أول خوارزمية لإيجاد الشجرة الممتدة الدنيا على يد العالم التشيكي أوتاكار بوروفكا عام 1926 (انظر خوارزمية بوروفكا ). وكان الهدف منها تغطية مورافيا كهربائيًا بكفاءة . تعمل الخوارزمية على مراحل متتالية. في كل مرحلة، تُسمى خطوة بوروفكا ، تُحدِّد غابة $F$ تتكون من الحافة ذات الوزن الأدنى المتصلة بكل رأس في الرسم البياني $G$ ، ثم تُشكِّل الرسم البياني $G₁ = G \ F$ كمدخل للخطوة التالية. هنا ، يُشير $G \ F$ إلى الرسم البياني المُشتق من $G$ عن طريق تقليص الحواف في $F$ (بحسب خاصية القطع ، تنتمي هذه الحواف إلى الشجرة الممتدة الدنيا). تستغرق كل خطوة $من$ خطوات بوروفكا وقتًا خطيًا. وبما أن عدد الرؤوس ينخفض إلى النصف على الأقل في كل خطوة، فإن خوارزمية بوروفكا تستغرق وقتًا قدره $O (m log n)$ . ^{[ 4 ]}

الخوارزمية الثانية هي خوارزمية بريم ، التي ابتكرها فويتش يارنيك عام 1930، وأعاد اكتشافها بريم عام 1957، ثم ديجكسترا عام 1959. تقوم هذه الخوارزمية أساسًا بتوسيع الشجرة الممتدة الدنيا ( $T$ ) ضلعًا تلو الآخر. في البداية، تحتوي $T$ على رأس عشوائي. في كل خطوة، تُضاف إلى $T ضلع ذو أقل وزن$ $(x, y)$ بحيث يكون $x جزءًا من$ $T$ و $y$ ليس جزءًا منها بعد $.$ وبفضل خاصية القطع ، فإن جميع الأضلاع المضافة إلى $T$ تكون جزءًا من الشجرة الممتدة الدنيا. يتراوح زمن تشغيل هذه الخوارزمية بين $O (m log n)$ و $O (m + n log n)$ ، وذلك حسب هياكل البيانات المستخدمة.

أما الخوارزمية الثالثة الشائعة الاستخدام فهي خوارزمية كروسكال ، والتي تستغرق أيضًا وقتًا قدره $O (m log n)$ .

أما الخوارزمية الرابعة، وهي أقل استخدامًا، فهي خوارزمية الحذف العكسي ، وهي عكس خوارزمية كروسكال. زمن تشغيلها هو $O(m log n (log log n) 3)$ .

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

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

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

في نموذج مقارنة، حيث تقتصر العمليات المسموح بها على أوزان الحواف على المقارنات الثنائية، وجد كارغر وكلاين وتارجان (1995) خوارزمية عشوائية ذات زمن خطي تعتمد على مزيج من خوارزمية بوروفكا وخوارزمية الحذف العكسي. ^{[ 5 ]}^{[ 6 ]}

تعتمد أسرع خوارزمية مقارنة غير عشوائية ذات تعقيد معروف، من ابتكار برنارد شازيل ، على الكومة المرنة ، وهي طابور أولوية تقريبي. ^{[ 7 ]}^{[ 8 ]} زمن تشغيلها هو $O (mα (m, n))$ ، حيث $α$ هي الدالة العكسية الكلاسيكية لدالة أكرمان . تنمو الدالة $α$ ببطء شديد، بحيث يمكن اعتبارها عمليًا ثابتة لا تتجاوز 4؛ وبالتالي، تستغرق خوارزمية شازيل زمنًا قريبًا جدًا من الزمن الخطي.

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

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

إذا كان الرسم البياني كثيفًا (أي $m / n \geq log log log n)$ ، فإن خوارزمية حتمية من تأليف فريدمان وتارجان تجد الشجرة الممتدة الدنيا في زمن $O(m)$ . ^{[ 9 ]} تُنفذ الخوارزمية عددًا من المراحل. تُنفذ كل مرحلة خوارزمية بريم عدة مرات، كل مرة لعدد محدود من الخطوات. زمن تشغيل كل مرحلة هو $O(m + n)$ . إذا كان عدد الرؤوس قبل المرحلة هو $n'$ ، فإن عدد الرؤوس المتبقية بعد المرحلة يكون على الأكثر ${\tfrac {n'}{2^{m/n'}}}$ وبالتالي، لا يلزم أكثر من $log* n$ مرحلة، مما يعطي وقت تشغيل خطي للرسوم البيانية الكثيفة. ^{[ 4 ]}

توجد خوارزميات أخرى تعمل في وقت خطي على الرسوم البيانية الكثيفة. ^{[ 7 ]}^{[ 10 ]}

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

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

الرسوم البيانية المستوية

توجد خوارزميات حتمية معروفة تحل المشكلة للرسوم البيانية المستوية في وقت خطي. ^{[ 12 ]}^{[ 13 ]} وبحسب خاصية أويلر للرسوم البيانية المستوية، $فإن m \leq 3n - 6 \in O (n)$ ، لذا فإن هذا يتم في وقت $O (n)$ .

أشجار القرار

بفرض وجود رسم بياني $G$ حيث تكون العقد والحواف ثابتة ولكن الأوزان غير معروفة، يمكن إنشاء شجرة قرار ثنائية (DT) لحساب الشجرة الممتدة الدنيا (MST) لأي تبديل للأوزان. تحتوي كل عقدة داخلية في شجرة القرار على مقارنة بين حافتين، مثل: "هل وزن الحافة بين $x$ و $y$ أكبر من وزن الحافة بين $w$ و $z$ ؟". يتوافق فرعا العقدة مع الإجابتين المحتملتين "نعم" أو "لا". في كل ورقة من أوراق شجرة القرار، توجد قائمة بالحواف من $G$ التي تُقابل الشجرة الممتدة الدنيا. يُعرَّف تعقيد وقت تشغيل شجرة القرار بأنه أكبر عدد من الاستعلامات المطلوبة لإيجاد الشجرة الممتدة الدنيا، وهو ببساطة عمق شجرة القرار. تُسمى شجرة القرار للرسم البياني $G$ مثالية إذا كان لها أصغر عمق بين جميع أشجار القرار الصحيحة لـ $G.$

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

أ. توليد جميع أنواع الأشجار المحتملة

هناك $2^{r \choose 2}$ رسوم بيانية مختلفة على $r$ رأس.
لكل رسم بياني، يمكن دائمًا إيجاد MST باستخدام $r (r - 1)$ مقارنة، على سبيل المثال بواسطة خوارزمية بريم .
وبالتالي، فإن عمق شجرة القرار المثلى أقل من $r 2$ .
وبالتالي، فإن عدد العقد الداخلية في شجرة القرار المثلى أقل من $2^{r^{2}}$ .
تقارن كل عقدة داخلية حافتين. عدد الحواف لا يتجاوز $r² ،$ لذا فإن عدد المقارنات المختلفة لا يتجاوز $r⁴ .$
وبالتالي، فإن عدد حالات DT المحتملة أقل من

${(r^{4})}^{(2^{r^{2}})}=r^{2^{(r^{2}+2)}}.$

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

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

وبالتالي، فإن إجمالي الوقت المطلوب لإيجاد شجرة القرار المثلى لجميع الرسوم البيانية التي تحتوي على $r$ رأس هو: ^{[ 4 ]}

2^{r \choose 2}\cdot r^{2^{(r^{2}+2)}}\cdot (r^{2}+1)!,

وهو أقل من

2^{2^{r^{2}+o(r)}}.

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

توصل سيث بيتي وفيجايا راماتشاندران إلى خوارزمية مثالية قابلة للإثبات تعتمد على المقارنة الحتمية لإيجاد الشجرة الممتدة الدنيا. ^{[ 4 ]} فيما يلي وصف مبسط للخوارزمية.

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

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

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

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

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

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

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

بالنسبة للأوزان العشوائية المنتظمة في $[0,1]$ تم حساب الحجم المتوقع الدقيق للشجرة الممتدة الدنيا للرسوم البيانية الكاملة الصغيرة. ^{[ 16 ]}

الرؤوس	الحجم المتوقع	الحجم المتوقع تقريبًا
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

متغير كسري

يوجد شكل كسري من شجرة الامتداد الدنيا، حيث يُسمح لكل حافة بالظهور "بشكل كسري". رسميًا، مجموعة الامتداد الكسري للرسم البياني (V,E) هي دالة غير سالبة f على E بحيث يكون مجموع f ( e ) على جميع الحواف التي تربط عقدة من W بعقدة من V \ W أكبر من أو يساوي 1، وذلك لكل مجموعة جزئية غير تافهة W من V (أي أن W ليست فارغة ولا تساوي V). وبشكل بديهي، تمثل f ( e ) جزءًا من e الموجود في مجموعة الامتداد. أما مجموعة الامتداد الكسري الدنيا فهي مجموعة امتداد كسري يكون مجموعها $\sum _{e\in E}f(e)\cdot w(e)$ أصغر ما يمكن.

إذا أُجبرت الكسور f ( e ) على أن تكون في المجموعة {0,1}، فإن مجموعة الحواف T التي تحقق f(e)=1 تُشكل مجموعة شاملة، حيث أن كل عقدة أو مجموعة جزئية من العقد متصلة ببقية الرسم البياني بواسطة حافة واحدة على الأقل من T. علاوة على ذلك، إذا كانت f تُقلل من $\sum _{e\in E}f(e)\cdot w(e)$ إذاً، فإن المجموعة الممتدة الناتجة تكون بالضرورة شجرة، لأنه إذا احتوت على دورة، فإنه يمكن إزالة حافة دون التأثير على شرط الامتداد. لذا، فإن مسألة المجموعة الممتدة الجزئية الدنيا هي تبسيط لمسألة الشجرة الممتدة الدنيا، ويمكن تسميتها أيضاً مسألة الشجرة الممتدة الدنيا الجزئية.

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

متغيرات أخرى

شجرة شتاينر لمجموعة جزئية من الرؤوس هي أصغر شجرة تغطي المجموعة الجزئية المعطاة. إيجاد شجرة شتاينر مسألة NP-كاملة . ^{[ 18 ]}
الشجرة الممتدة الدنيا k ( k -MST) هي الشجرة التي تمتد على مجموعة فرعية من k رأس في الرسم البياني بأقل وزن.
مجموعة الأشجار الممتدة الأصغر من الرتبة k هي مجموعة جزئية من الأشجار الممتدة k (من بين جميع الأشجار الممتدة الممكنة) بحيث لا توجد شجرة ممتدة خارج المجموعة الجزئية لها وزن أصغر. ^{[ 19 ]}^{[ 20 ]}^{[ 21 ]} (لاحظ أن هذه المسألة لا علاقة لها بمسألة الشجرة الممتدة الدنيا من الرتبة k ).
الشجرة الممتدة الدنيا الإقليدية هي شجرة ممتدة للرسم البياني مع أوزان الحواف التي تتوافق مع المسافة الإقليدية بين الرؤوس التي هي نقاط في المستوى (أو الفضاء).
الشجرة الممتدة الدنيا المستقيمة هي شجرة ممتدة للرسم البياني مع أوزان الحواف التي تتوافق مع المسافة المستقيمة بين الرؤوس التي هي نقاط في المستوى (أو الفضاء).
تُعدّ شجرة الامتداد الأدنى الموزعة امتدادًا لشجرة الامتداد الأدنى في النموذج الموزع ، حيث تُعتبر كل عقدة بمثابة حاسوب، ولا تعرف أي عقدة أي شيء سوى روابطها المتصلة بها. التعريف الرياضي للمشكلة واحد، ولكن توجد طرق مختلفة لحلها.
الشجرة الممتدة الدنيا ذات السعة المحدودة هي شجرة تحتوي على عقدة مميزة (أصل أو جذر)، وكل شجرة فرعية متصلة بهذه العقدة لا تحتوي على أكثر من c عقدة. تُسمى c سعة الشجرة. يُعدّ حلّ مسألة الشجرة الممتدة الدنيا ذات السعة المحدودة الأمثل مسألة صعبة من نوع NP ، ^{[ 22 ]} ولكنّ الطرق الاستدلالية الجيدة مثل Esau-Williams و Sharma تُنتج حلولًا قريبة من الحل الأمثل في وقت متعدد الحدود.
الشجرة الممتدة الدنيا المقيدة بالدرجة هي شجرة ممتدة دنيا لا يرتبط فيها كل رأس بأكثر من d رأسًا آخر، وذلك لعدد معين d . الحالة d = 2 هي حالة خاصة من مسألة البائع المتجول ، لذا فإن الشجرة الممتدة الدنيا المقيدة بالدرجة هي مسألة صعبة الحل من نوع NP بشكل عام.
التفرع الشجري هو شكل من أشكال شجرة الامتداد الأدنى للرسوم البيانية الموجهة . ويمكن حله في $O(E+V\log V)$ الوقت باستخدام خوارزمية تشو-ليو/إدموندز .
الشجرة الممتدة القصوى هي شجرة ممتدة يكون وزنها أكبر من أو يساوي وزن أي شجرة ممتدة أخرى. يمكن إيجاد هذه الشجرة باستخدام خوارزميات مثل خوارزمية بريم أو كروسكال بعد ضرب أوزان الحواف في -1 وحل مسألة الشجرة الممتدة الدنيا على الرسم البياني الجديد. المسار في الشجرة الممتدة القصوى هو أوسع مسار في الرسم البياني بين طرفيها: من بين جميع المسارات الممكنة، يُعظّم هذا المسار وزن الحافة ذات الوزن الأدنى. ^{[ 23 ]} تُستخدم الأشجار الممتدة القصوى في خوارزميات تحليل اللغات الطبيعية ^{[ 24 ]} وفي خوارزميات تدريب الحقول العشوائية الشرطية .
العمود الفقري فائق القياس هو أصغر عمود فقري ممكن للمسافة في الرسوم البيانية الموجهة وغير الموجهة ذات الأوزان الموجبة. ^{[ 25 ]} يُمثل العمود الفقري فائق القياس اتحاد الغابات الممتدة الدنيا في الرسوم البيانية غير الموجهة (ذات الأوزان الموجبة)، ويُقدم تعميمًا للأشجار الممتدة الدنيا للرسوم البيانية الموجهة، والذي، على عكس الرسوم البيانية المكافئة الدنيا والأشجار الممتدة الدنيا المتفرعة، يحافظ على جميع أقصر المسارات القصوى والدنيا، وعلى اتساق قانون دي مورغان. ^{[ 26 ]}
تتعلق مشكلة الشجرة الممتدة الدنيا الديناميكية بتحديث الشجرة الممتدة الدنيا المحسوبة مسبقًا بعد تغيير وزن الحافة في الرسم البياني الأصلي أو إضافة/حذف رأس. ^{[ 27 ]}^{[ 28 ]}^{[ 29 ]}
تتمثل مشكلة الشجرة الممتدة ذات الحد الأدنى من التصنيفات في إيجاد شجرة ممتدة بأقل عدد من أنواع التصنيفات إذا تم ربط كل حافة في الرسم البياني بتصنيف من مجموعة تصنيفات محدودة بدلاً من وزن. ^{[ 30 ]}
الحافة ذات الوزن الأعلى في الشجرة الممتدة هي حافة عنق الزجاجة. تُسمى الشجرة الممتدة شجرة عنق الزجاجة الدنيا ( MBST ) إذا لم تحتوي على شجرة ممتدة ذات وزن حافة عنق زجاجة أقل. الشجرة الممتدة الدنيا (MST) هي بالضرورة شجرة MBST ( يمكن إثبات ذلك بخاصية القطع )، ولكن شجرة MBST ليست بالضرورة شجرة MST. ^{[ 31 ]}^{[ 32 ]}
لعبة الشجرة الممتدة ذات التكلفة الدنيا هي لعبة تعاونية يتعين على اللاعبين فيها تقاسم تكاليف بناء الشجرة الممتدة المثلى فيما بينهم.
تتمثل مشكلة تصميم الشبكة الأمثل في حساب مجموعة، تخضع لقيود الميزانية، والتي تحتوي على شجرة ممتدة، بحيث يكون مجموع أقصر المسارات بين كل زوج من العقد أصغر ما يمكن.

التطبيقات

تُستخدم الأشجار الممتدة الدنيا بشكل مباشر في تصميم الشبكات، بما في ذلك شبكات الحاسوب ، وشبكات الاتصالات ، وشبكات النقل ، وشبكات إمداد المياه ، وشبكات الكهرباء (التي صُممت من أجلها في الأصل، كما ذُكر سابقًا). ^{[ 33 ]} كما تُستخدم كبرامج فرعية في خوارزميات لحل مسائل أخرى، منها خوارزمية كريستوفيدس لتقريب مسألة البائع المتجول ، ^{[ 34 ]} وتقريب مسألة القطع الأدنى متعددة الأطراف (المكافئة في حالة الطرف الواحد لمسألة التدفق الأقصى )، ^{[ 35 ]} وتقريب مسألة المطابقة المثالية الموزونة ذات التكلفة الدنيا . ^{[ 36 ]}

تشمل التطبيقات العملية الأخرى القائمة على الأشجار الممتدة الدنيا ما يلي:

التصنيف . ^{[ 37 ]}
تحليل التجميع : تجميع النقاط في المستوى، ^{[ 38 ]} التجميع أحادي الارتباط (طريقة للتجميع الهرمي )، ^{[ 39 ]} التجميع القائم على نظرية الرسم البياني، ^{[ 40 ]} وتجميع بيانات التعبير الجيني . ^{[ 41 ]}
بناء الأشجار للبث في شبكات الحاسوب. ^{[ 42 ]}
تسجيل الصور ^{[ 43 ]} والتجزئة [ ⁴⁴^{] -} انظر التجزئة القائمة على الشجرة الممتدة الدنيا .
استخلاص الميزات المنحنية في مجال رؤية الحاسوب . ^{[ 45 ]}
التعرف على التعبيرات الرياضية من خلال الكتابة اليدوية. ^{[ 46 ]}
تصميم الدوائر : تنفيذ عمليات ضرب الثوابت المتعددة بكفاءة، كما هو مستخدم في مرشحات الاستجابة النبضية المحدودة . ^{[ 47 ]}
تقسيم المناطق الاجتماعية والجغرافية إلى مناطق، أي تجميع المناطق في مناطق متجانسة ومتجاورة. ^{[ 48 ]}
مقارنة بيانات علم السموم البيئية . ^{[ 49 ]}
قابلية الملاحظة الطوبولوجية في أنظمة الطاقة. ^{[ 50 ]}
قياس تجانس المواد ثنائية الأبعاد. ^{[ 51 ]}
التحكم في العمليات باستخدام أسلوب Minimax . ^{[ 52 ]}
يمكن استخدام الأشجار الممتدة الدنيا لوصف الأسواق المالية أيضًا. ^{[ 53 ]}^{[ 54 ]} يمكن إنشاء مصفوفة ارتباط بحساب معامل الارتباط بين أي سهمين. يمكن تمثيل هذه المصفوفة طوبولوجيًا كشبكة معقدة، ويمكن إنشاء شجرة ممتدة دنيا لتوضيح العلاقات.

مراجع

↑ "scipy.sparse.csgraph.minimum_spanning_tree - دليل SciPy الإصدار 1.7.1" . وثائق Numpy وScipy — وثائق Numpy وScipy . تم الاطلاع عليه بتاريخ 10 ديسمبر 2021. الشجرة الممتدة الدنيا هي رسم بياني يتكون من مجموعة فرعية من الحواف التي تربط جميع العقد المتصلة، مع تقليل المجموع الكلي للأوزان على الحواف.
↑ "networkx.algorithms.tree.mst.minimum_spanning_edges" . وثائق NetworkX 2.6.2 . تاريخ الاطلاع: 13 ديسمبر 2021. الشجرة الممتدة الدنيا هي رسم بياني فرعي من الرسم البياني (شجرة) ذي أقل مجموع لأوزان الحواف. الغابة الممتدة هي اتحاد الأشجار الممتدة لكل مكون متصل من الرسم البياني.
↑ "هل تحتوي الأشجار الممتدة الدنيا للرسم البياني الموزون على نفس عدد الحواف عند وزن معين؟" . cs.stackexchange.com . تم الاطلاع عليه بتاريخ 4 أبريل 2018 .
1 2 3 4 5 بيتي، سيث؛ راماتشاندران، فيجايا (2002)، "خوارزمية الشجرة الممتدة الدنيا المثلى" (ملف PDF) ، مجلة رابطة آلات الحوسبة ، 49 (1): 16-34 ، doi : 10.1145/505241.505243 ، MR 2148431 ، S2CID 5362916 .
↑ كارغر، ديفيد ر .؛ كلاين، فيليب ن .؛ تارجان، روبرت إي. (1995)، "خوارزمية عشوائية خطية لإيجاد الأشجار الممتدة الدنيا"، مجلة رابطة آلات الحوسبة ، 42 (2): 321-328 ، doi : 10.1145/201019.201022 ، MR 1409738 ، S2CID 832583
↑ بيتي، سيث؛ راماتشاندران، فيجايا (2002)، "تقليل العشوائية في خوارزميات الشجرة الممتدة الدنيا، والاتصال المتوازي، ومجموعات القيم القصوى" ، وقائع الندوة الثالثة عشرة لجمعية ACM-SIAM حول الخوارزميات المنفصلة (SODA '02) ، سان فرانسيسكو، كاليفورنيا، الصفحات 713-722 ، ISBN 978-0-89871-513-2{{citation}}: CS1 maint: موقع الناشر مفقود ( رابط ) .
1 2 شازيل، برنارد (2000)، "خوارزمية الشجرة الممتدة الدنيا ذات تعقيد من نوع أكرمان العكسي"، مجلة رابطة آلات الحوسبة ، 47 (6): 1028-1047 ، doi : 10.1145/355541.355562 ، MR 1866456 ، S2CID 6276962 .
↑ شازيل، برنارد (2000)، "الكومة المرنة: طابور أولوية تقريبي بمعدل خطأ مثالي"، مجلة رابطة آلات الحوسبة ، 47 (6): 1012-1027 ، doi : 10.1145/355541.355554 ، MR 1866455 ، S2CID 12556140 .
↑ فريدمان، إم إل؛ تارجان، آر إي (1987). "أكوام فيبوناتشي واستخداماتها في خوارزميات تحسين الشبكات المحسّنة" . مجلة ACM . 34 (3): 596. doi : 10.1145/28869.28874 . S2CID 7904683 .
↑ جابو، إتش إن ؛ جاليل، زد؛ سبنسر، تي؛ تارجان، آر إي (1986). "خوارزميات فعّالة لإيجاد الأشجار الممتدة الدنيا في الرسوم البيانية غير الموجهة والموجهة". كومبيناتوريكا . 6 (2): 109. doi : 10.1007/bf02579168 . S2CID 35618095 .
↑ فريدمان، إم إل ؛ ويلارد، دي إي (1994)، "خوارزميات ثنائية التفرع لأشجار الامتداد الدنيا وأقصر المسارات"، مجلة علوم الحاسوب والنظم ، 48 (3): 533-551 ، doi : 10.1016/S0022-0000(05)80064-9 ، MR 1279413 .
↑ ماتسوي، تومومي (10 مارس 1995). "مسألة الشجرة الممتدة الدنيا على رسم بياني مستوٍ". الرياضيات التطبيقية المنفصلة . 58 (1): 91-94 . doi : 10.1016/0166-218X(94)00095-U . ISSN 0166-218X .
↑ شيريتون، ديفيد؛ تارجان، روبرت إندري (ديسمبر 1976). "إيجاد الأشجار الممتدة الدنيا" . مجلة SIAM للحوسبة . 5 (4): 724-742 . doi : 10.1137/0205051 . ISSN 0097-5397 .
↑ تشونغ، كا وونغ؛ هان، ييجي؛ لام، تاك واه (2001)، "الخيوط المتزامنة وخوارزمية الأشجار الممتدة الدنيا المتوازية المثلى"، مجلة رابطة آلات الحوسبة ، 48 (2): 297-323 ، doi : 10.1145/375827.375847 ، MR 1868718 ، S2CID 1778676 .
↑ بيتي، سيث؛ راماتشاندران، فيجايا (2002)، "خوارزمية متوازية عشوائية مثلى من حيث الوقت والعمل لإيجاد غابة ممتدة دنيا" (ملف PDF) ، مجلة SIAM للحوسبة ، 31 (6): 1879-1895 ، doi : 10.1137/S0097539700371065 ، MR 1954882 .
↑ ستيل، ج. مايكل (2002)، "الأشجار الممتدة الدنيا للرسوم البيانية ذات أطوال الحواف العشوائية"، الرياضيات وعلوم الحاسوب، الجزء الثاني (فرساي، 2002) ، تريندز ماث، بازل: بيركهاوزر، ص 223-245 ، MR 1940139
1 2 جروتشيل, مارتن ; الأماكن القريبة : شريفر ، ألكسندر (1993)، الخوارزميات الهندسية والتحسين التوافقي ، الخوارزميات والتوافقيات، المجلد. 2 ( الطبعة الثانية)، Springer-Verlag، برلين، دوى : 10.1007 / 978-3-642-78240-4 ، ISBN 978-3-642-78242-8MR 1261419
↑ غاري، مايكل ر .؛ جونسون، ديفيد س. (1979). الحواسيب والاستعصاء: دليل لنظرية اكتمال NP . سلسلة كتب في العلوم الرياضية ( الطبعة الأولى). نيويورك: دبليو إتش فريمان وشركاه . ISBN 9780716710455MR 0519066 . OCLC 247570676 . ND12
↑ جابو، هارولد ن. (1977)، "خوارزميتان لتوليد الأشجار الممتدة الموزونة بالترتيب"، مجلة SIAM للحوسبة ، 6 (1): 139-150 ، doi : 10.1137/0206011 ، MR 0441784 .
↑ إبستين، ديفيد (1992)، "إيجاد أصغر k شجرة ممتدة"، BIT ، 32 (2): 237-248 ، doi : 10.1007/BF01994879 ، MR 1172188 ، S2CID 121160520 .
↑ فريدريكسون، جريج ن. (1997)، "هياكل البيانات المتناقضة للاتصال الديناميكي ثنائي الحواف وأصغر k شجرة ممتدة" ، مجلة SIAM للحوسبة ، 26 (2): 484-538 ، doi : 10.1137/S0097539792226825 ، MR 1438526 .
↑ جوثي، راجا؛ راغافاتشاري، بالاجي (2005)، "خوارزميات التقريب لمسألة الشجرة الممتدة الدنيا ذات السعة المحدودة ومتغيراتها في تصميم الشبكات"، معاملات ACM للخوارزميات ، 1 (2): 265-282 ، doi : 10.1145/1103963.1103967 ، S2CID 8302085
↑ هو، تي سي (1961)، "مشكلة المسار ذي السعة القصوى"، بحوث العمليات ، 9 (6): 898-900 ، doi : 10.1287/opre.9.6.898 ، JSTOR 167055 .
↑ ماكدونالد، رايان؛ بيريرا، فرناندو؛ ريباروف، كيريل؛ هاجيتش، يان (2005). "تحليل التبعية غير الإسقاطية باستخدام خوارزميات الشجرة الممتدة" (ملف PDF) . وقائع مؤتمر HLT/EMNLP .
↑ سيماس، تياجو؛ كوريا، ريون ب.؛ روشا، لويس م. (2021)، "العمود الفقري للمسافة في الشبكات المعقدة"، مجلة الشبكات المعقدة ، 9 (6) cnab021، arXiv : 2103.04668 ، doi : 10.1093/comnet/cnab021 ، PMID 38348382 .
↑ روزوم، جوردان سي؛ روشا، لويس إم (2021)، "العمود الفقري فائق القياس هو اتحاد جميع الغابات الممتدة الدنيا"، مجلة الفيزياء: التعقيد ، 5 (3): 035009، doi : 10.1088/2632-072X/ad679e ، PMID 39131403 تتضمن هذه المقالة نصًا من هذا المصدر، وهو متاح بموجب ترخيص CC BY 4.0 .
↑ سبايرا، ب.م.؛ بان، أ. (1975)، "حول إيجاد وتحديث الأشجار الممتدة وأقصر المسارات" (ملف PDF) ، مجلة SIAM للحوسبة ، 4 (3): 375-380 ، doi : 10.1137/0204032 ، MR 0378466 .
↑ هولم، جاكوب؛ دي ليشتنبرغ، كريستيان؛ ثورب، ميكيل (2001)، "خوارزميات حتمية متعددة اللوغاريتمات ديناميكية بالكامل للاتصال، والشجرة الممتدة الدنيا، والحافة الثنائية، والاتصال الثنائي"، مجلة رابطة آلات الحوسبة ، 48 (4): 723-760 ، doi : 10.1145/502090.502095 ، MR 2144928 ، S2CID 7273552 .
↑ تشين، ف.؛ هوك، د. (1978)، "خوارزميات لتحديث الأشجار الممتدة الدنيا"، مجلة علوم الحاسوب والنظم ، 16 (3): 333-344 ، doi : 10.1016/0022-0000(78)90022-3 .
↑ تشانغ، آر إس؛ ليو، إس جيه (1997)، "أشجار الامتداد ذات الحد الأدنى من التصنيف"، رسائل معالجة المعلومات ، 63 (5): 277-282 ، doi : 10.1016/s0020-0190(97)00127-0 .
↑ "كل شيء عن شجرة الامتداد ذات العنق الزجاجي" . flashing-thoughts.blogspot.ru . 5 يونيو 2010. تم الاطلاع عليه في 4 أبريل 2018 .
↑ "نسخة مؤرشفة" (PDF) . مؤرشفة من الأصل (PDF) بتاريخ 12-06-2013 . تم الاطلاع عليها بتاريخ 02-07-2014 .{{cite web}}: CS1 maint: archived copy as title ( link )
↑ غراهام، آر إل ؛ هيل، بافول (1985)، "حول تاريخ مسألة الشجرة الممتدة الدنيا"، حوليات تاريخ الحوسبة ، 7 (1): 43-57 ، Bibcode : 1985IAHC....7a..43G ، doi : 10.1109/MAHC.1985.10011 ، MR 0783327 ، S2CID 10555375
↑ نيكوس كريستوفيدس ، تحليل أسوأ الحالات لأسلوب استدلالي جديد لمشكلة البائع المتجول ، التقرير 388، كلية الدراسات العليا للإدارة الصناعية، جامعة كارنيجي ميلون، 1976.
^ دالهاوس، إي. جونسون, دي إس ; الأماكن القريبة : سيمور, مقاطعة كولومبيا ; ياناكاكيس، م. (أغسطس 1994). "تعقيد التخفيضات المتعددة الأطراف" (PDF) . مجلة SIAM للحوسبة . 23 (4): 864-894 . دوى : 10.1137 / S0097539792225297 . مؤرشفة من الأصلي (PDF) في 24 أغسطس 2004 . تم الاسترجاع 17 ديسمبر 2012 .
↑ سوبويت، كينيث جيه؛ بلايستيد، ديفيد أ؛ رينغولد، إدوارد م. (1980). طرق استدلالية للمطابقة المثالية الموزونة . المؤتمر السنوي الثاني عشر لجمعية آلات الحوسبة حول نظرية الحوسبة (STOC '80). نيويورك، نيويورك، الولايات المتحدة الأمريكية: جمعية آلات الحوسبة. الصفحات 398-419 . doi : 10.1145/800141.804689 .
↑ سنيث، بي إتش إيه (1 أغسطس 1957). "تطبيق الحواسيب في علم التصنيف" . مجلة علم الأحياء الدقيقة العام . 17 (1): 201-226 . doi : 10.1099/00221287-17-1-201 . PMID 13475686 .
↑ أسانو، ت .؛ بهاتاشاريا، ب.؛ كيل، م.؛ ياو، ف. (1988). خوارزميات التجميع القائمة على الأشجار الممتدة الدنيا والقصوى . الندوة السنوية الرابعة حول الهندسة الحسابية (SCG '88). المجلد 1. الصفحات 252-257 . doi : 10.1145/73393.73419 .
↑ غاور، ج. س.؛ روس، ج. ج. س. (1969). "أشجار الامتداد الأدنى وتحليل التجميع بالارتباط الأحادي". مجلة الجمعية الإحصائية الملكية . ج (الإحصاء التطبيقي). 18 (1): 54-64 . doi : 10.2307/2346439 . JSTOR 2346439 .
↑ بايفينين، نينا (1 مايو 2005). "التجميع باستخدام شجرة امتداد دنيا ذات بنية شبيهة بالبنية الخالية من المقاييس". رسائل التعرف على الأنماط . 26 (7): 921-930 . Bibcode : 2005PaReL..26..921P . doi : 10.1016/j.patrec.2004.09.039 .
↑ شو، ي.؛ أولمان، ف.؛ شو، د. (1 أبريل 2002). "تجميع بيانات التعبير الجيني باستخدام منهجية نظرية الرسم البياني: تطبيق لأشجار الامتداد الأدنى" . المعلوماتية الحيوية . 18 (4): 536-545 . doi : 10.1093/bioinformatics/18.4.536 . PMID 12016051 .
↑ دلال، يوجين ك.؛ ميتكالف، روبرت م. (1 ديسمبر 1978). "إعادة توجيه حزم البث عبر المسار العكسي" . اتصالات رابطة آلات الحوسبة . 21 (12): 1040-1048 . doi : 10.1145/359657.359665 . S2CID 5638057 .
↑ ما، ب.؛ هيرو، أ.؛ جورمان، ج.؛ ميشيل، أ. (2000). تسجيل الصور باستخدام خوارزمية الشجرة الممتدة الدنيا (ملف PDF) . المؤتمر الدولي لمعالجة الصور. المجلد 1. الصفحات 481-484 . doi : 10.1109/ICIP.2000.901000 . مؤرشف (ملف PDF) من النسخة الأصلية بتاريخ 9 أكتوبر 2022.
^ P. Felzenszwalb، D. Huttenlocher: تجزئة الصور الفعالة القائمة على الرسم البياني. IJCV 59(2) (سبتمبر 2004)
↑ سوك، مينسو؛ سونغ، أوهيونغ (1 يونيو 1984). "استخلاص الميزات المنحنية باستخدام الأشجار الممتدة الدنيا". رؤية الحاسوب، والرسومات، ومعالجة الصور . 26 (3): 400-411 . doi : 10.1016/0734-189X(84)90221-4 .
↑ تابيا، إرنستو؛ روخاس، راؤول (2004). "التعرف على التعبيرات الرياضية المكتوبة بخط اليد على الإنترنت باستخدام بناء شجرة الامتداد الأدنى وهيمنة الرمز" (ملف PDF) . التعرف على الرسومات. التطورات الحديثة والآفاق . سلسلة محاضرات في علوم الحاسوب. المجلد 3088. برلين هايدلبرغ: سبرينغر-فيرلاغ. الصفحات 329-340 . ISBN 978-3-540-22478-5تمت أرشفة الملف (PDF) من النسخة الأصلية بتاريخ 2022-10-09.
↑ أولسون، هـ. (2004). تطبيق مرشحات FIR منخفضة التعقيد باستخدام شجرة الامتداد الدنيا . المؤتمر الثاني عشر لجمعية مهندسي الكهرباء والإلكترونيات في منطقة البحر الأبيض المتوسط للهندسة الكهربائية (MELECON 2004). المجلد 1. الصفحات 261-264 . doi : 10.1109/MELCON.2004.1346826 .
↑ أسونساو، آر إم؛ مولودية نيفيس؛ جي كامارا؛ جيم دا كوستا فريتاس (2006). "تقنيات الأقلمة الفعالة للوحدات الجغرافية الاجتماعية والاقتصادية باستخدام الحد الأدنى من الأشجار الممتدة" . المجلة الدولية لعلوم المعلومات الجغرافية . 20 (7): 797– 811. بيب كود : 2006IJGIS..20..797A . دوى : 10.1080/13658810600665111 . S2CID 2530748 .
↑ ديفيليرز، ج.؛ دور، ج. س. (1 أبريل 1989). "الفعالية الاستدلالية لطريقة الشجرة الممتدة الدنيا (MST) في علم السموم". علم السموم البيئية والسلامة البيئية . 17 (2): 227-235 . Bibcode : 1989EcoES..17..227D . doi : 10.1016/0147-6513(89)90042-0 . PMID 2737116 .
↑ موري، هـ.؛ تسوزوكي، س. (1 مايو 1991). "طريقة سريعة لتحليل قابلية الملاحظة الطوبولوجية باستخدام تقنية الشجرة الممتدة الدنيا". معاملات IEEE لأنظمة الطاقة . 6 (2): 491-500 . Bibcode : 1991ITPSy...6..491M . doi : 10.1109/59.76691 .
↑ فيليبين، جيمس جيه؛ كافادار، كارين ؛ شير، دوغلاس آر. (1 يناير 1983). "اختبار تجانس الأسطح ثنائية الأبعاد". النمذجة الرياضية . 4 (2): 167-189 . doi : 10.1016/0270-0255(83)90026-X .
↑ كالابا، روبرت إي. (1963)، نظرية الرسم البياني والتحكم الآلي (ملف PDF) ، مؤرشف من الأصل (ملف PDF) في 21 فبراير 2016
↑ مانتينيا، آر إن (1999). الهيكل الهرمي في الأسواق المالية . المجلة الأوروبية للفيزياء ب - المادة المكثفة والأنظمة المعقدة، 11(1)، 193-197.
↑ دجوهاري، م.، وجان، س. (2015). مشكلة الأمثلية في طوبولوجيا الشبكة في تحليل سوق الأسهم . فيزيكا أ: الميكانيكا الإحصائية وتطبيقاتها، 419، 108-114.

للمزيد من القراءة

أوتاكار بوروفكا حول مشكلة الحد الأدنى من الشجرة الممتدة (ترجمة كل من ورقات عام 1926، والتعليقات، والتاريخ) (2000) ياروسلاف نيسيتريل ، إيفا ميلكوفا، هيلينا نيستريلوفا. (يقدم القسم 7 خوارزميته، التي تبدو وكأنها تقاطع بين خوارزمية بريم وخوارزمية كروسكال).
توماس هـ. كورمن ، تشارلز إي. ليسرسون ، رونالد ل. ريفست ، وكليفورد شتاين . مقدمة في الخوارزميات ، الطبعة الثانية. مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل، 2001. ISBN 0-262-03293-7الفصل 23: الأشجار الممتدة الدنيا، الصفحات 561-579.
إيسنر، جيسون (1997). أحدث الخوارزميات لأشجار الامتداد الأدنى: مناقشة تعليمية . مخطوطة، جامعة بنسلفانيا، أبريل. 78 صفحة.
كرومكوفسكي، جون ديفيد. "لا تزال غير منصهرة بعد كل هذه السنوات"، في الطبعات السنوية، العلاقات العرقية والإثنية، 17/هـ (2009 ماكجرو هيل) (باستخدام شجرة الامتداد الأدنى كطريقة للتحليل الديموغرافي للتنوع العرقي في جميع أنحاء الولايات المتحدة).

روابط خارجية

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

[Numpy_and_Scipy_Documentation_—_Numpy_and_Scipy_documentation-1] "scipy.sparse.csgraph.minimum_spanning_tree - دليل SciPy الإصدار 1.7.1" . وثائق Numpy وScipy — وثائق Numpy وScipy . تم الاطلاع عليه بتاريخ 10 ديسمبر 2021. الشجرة الممتدة الدنيا هي رسم بياني يتكون من مجموعة فرعية من الحواف التي تربط جميع العقد المتصلة، مع تقليل المجموع الكلي للأوزان على الحواف.

[NetworkX_2.6.2_documentation-2] "networkx.algorithms.tree.mst.minimum_spanning_edges" . وثائق NetworkX 2.6.2 . تاريخ الاطلاع: 13 ديسمبر 2021. الشجرة الممتدة الدنيا هي رسم بياني فرعي من الرسم البياني (شجرة) ذي أقل مجموع لأوزان الحواف. الغابة الممتدة هي اتحاد الأشجار الممتدة لكل مكون متصل من الرسم البياني.

[3] "هل تحتوي الأشجار الممتدة الدنيا للرسم البياني الموزون على نفس عدد الحواف عند وزن معين؟" . cs.stackexchange.com . تم الاطلاع عليه بتاريخ 4 أبريل 2018 .

[PettieRamachandran2002-4] 1 2 3 4 5 بيتي، سيث؛ راماتشاندران، فيجايا (2002)، "خوارزمية الشجرة الممتدة الدنيا المثلى" (ملف PDF) ، مجلة رابطة آلات الحوسبة ، 49 (1): 16-34 ، doi : 10.1145/505241.505243 ، MR 2148431 ، S2CID 5362916 .

[5] كارغر، ديفيد ر .؛ كلاين، فيليب ن .؛ تارجان، روبرت إي. (1995)، "خوارزمية عشوائية خطية لإيجاد الأشجار الممتدة الدنيا"، مجلة رابطة آلات الحوسبة ، 42 (2): 321-328 ، doi : 10.1145/201019.201022 ، MR 1409738 ، S2CID 832583

[6] بيتي، سيث؛ راماتشاندران، فيجايا (2002)، "تقليل العشوائية في خوارزميات الشجرة الممتدة الدنيا، والاتصال المتوازي، ومجموعات القيم القصوى" ، وقائع الندوة الثالثة عشرة لجمعية ACM-SIAM حول الخوارزميات المنفصلة (SODA '02) ، سان فرانسيسكو، كاليفورنيا، الصفحات 713-722 ، ISBN 978-0-89871-513-2{{citation}}: CS1 maint: موقع الناشر مفقود ( رابط ) .

[Chazelle2000-7] 1 2 شازيل، برنارد (2000)، "خوارزمية الشجرة الممتدة الدنيا ذات تعقيد من نوع أكرمان العكسي"، مجلة رابطة آلات الحوسبة ، 47 (6): 1028-1047 ، doi : 10.1145/355541.355562 ، MR 1866456 ، S2CID 6276962 .

[8] شازيل، برنارد (2000)، "الكومة المرنة: طابور أولوية تقريبي بمعدل خطأ مثالي"، مجلة رابطة آلات الحوسبة ، 47 (6): 1012-1027 ، doi : 10.1145/355541.355554 ، MR 1866455 ، S2CID 12556140 .

[9] فريدمان، إم إل؛ تارجان، آر إي (1987). "أكوام فيبوناتشي واستخداماتها في خوارزميات تحسين الشبكات المحسّنة" . مجلة ACM . 34 (3): 596. doi : 10.1145/28869.28874 . S2CID 7904683 .

[10] جابو، إتش إن ؛ جاليل، زد؛ سبنسر، تي؛ تارجان، آر إي (1986). "خوارزميات فعّالة لإيجاد الأشجار الممتدة الدنيا في الرسوم البيانية غير الموجهة والموجهة". كومبيناتوريكا . 6 (2): 109. doi : 10.1007/bf02579168 . S2CID 35618095 .

[11] فريدمان، إم إل ؛ ويلارد، دي إي (1994)، "خوارزميات ثنائية التفرع لأشجار الامتداد الدنيا وأقصر المسارات"، مجلة علوم الحاسوب والنظم ، 48 (3): 533-551 ، doi : 10.1016/S0022-0000(05)80064-9 ، MR 1279413 .

[12] ماتسوي، تومومي (10 مارس 1995). "مسألة الشجرة الممتدة الدنيا على رسم بياني مستوٍ". الرياضيات التطبيقية المنفصلة . 58 (1): 91-94 . doi : 10.1016/0166-218X(94)00095-U . ISSN 0166-218X .

[13] شيريتون، ديفيد؛ تارجان، روبرت إندري (ديسمبر 1976). "إيجاد الأشجار الممتدة الدنيا" . مجلة SIAM للحوسبة . 5 (4): 724-742 . doi : 10.1137/0205051 . ISSN 0097-5397 .

[14] تشونغ، كا وونغ؛ هان، ييجي؛ لام، تاك واه (2001)، "الخيوط المتزامنة وخوارزمية الأشجار الممتدة الدنيا المتوازية المثلى"، مجلة رابطة آلات الحوسبة ، 48 (2): 297-323 ، doi : 10.1145/375827.375847 ، MR 1868718 ، S2CID 1778676 .

[15] بيتي، سيث؛ راماتشاندران، فيجايا (2002)، "خوارزمية متوازية عشوائية مثلى من حيث الوقت والعمل لإيجاد غابة ممتدة دنيا" (ملف PDF) ، مجلة SIAM للحوسبة ، 31 (6): 1879-1895 ، doi : 10.1137/S0097539700371065 ، MR 1954882 .

[16] ستيل، ج. مايكل (2002)، "الأشجار الممتدة الدنيا للرسوم البيانية ذات أطوال الحواف العشوائية"، الرياضيات وعلوم الحاسوب، الجزء الثاني (فرساي، 2002) ، تريندز ماث، بازل: بيركهاوزر، ص 223-245 ، MR 1940139

[:1-17] 1 2 جروتشيل, مارتن ; الأماكن القريبة : شريفر ، ألكسندر (1993)، الخوارزميات الهندسية والتحسين التوافقي ، الخوارزميات والتوافقيات، المجلد. 2 ( الطبعة الثانية)، Springer-Verlag، برلين، دوى : 10.1007 / 978-3-642-78240-4 ، ISBN 978-3-642-78242-8MR 1261419

[18] غاري، مايكل ر .؛ جونسون، ديفيد س. (1979). الحواسيب والاستعصاء: دليل لنظرية اكتمال NP . سلسلة كتب في العلوم الرياضية ( الطبعة الأولى). نيويورك: دبليو إتش فريمان وشركاه . ISBN 9780716710455MR 0519066 . OCLC 247570676 . ND12

[19] جابو، هارولد ن. (1977)، "خوارزميتان لتوليد الأشجار الممتدة الموزونة بالترتيب"، مجلة SIAM للحوسبة ، 6 (1): 139-150 ، doi : 10.1137/0206011 ، MR 0441784 .

[20] إبستين، ديفيد (1992)، "إيجاد أصغر k شجرة ممتدة"، BIT ، 32 (2): 237-248 ، doi : 10.1007/BF01994879 ، MR 1172188 ، S2CID 121160520 .

[21] فريدريكسون، جريج ن. (1997)، "هياكل البيانات المتناقضة للاتصال الديناميكي ثنائي الحواف وأصغر k شجرة ممتدة" ، مجلة SIAM للحوسبة ، 26 (2): 484-538 ، doi : 10.1137/S0097539792226825 ، MR 1438526 .

[22] جوثي، راجا؛ راغافاتشاري، بالاجي (2005)، "خوارزميات التقريب لمسألة الشجرة الممتدة الدنيا ذات السعة المحدودة ومتغيراتها في تصميم الشبكات"، معاملات ACM للخوارزميات ، 1 (2): 265-282 ، doi : 10.1145/1103963.1103967 ، S2CID 8302085

[23] هو، تي سي (1961)، "مشكلة المسار ذي السعة القصوى"، بحوث العمليات ، 9 (6): 898-900 ، doi : 10.1287/opre.9.6.898 ، JSTOR 167055 .

[24] ماكدونالد، رايان؛ بيريرا، فرناندو؛ ريباروف، كيريل؛ هاجيتش، يان (2005). "تحليل التبعية غير الإسقاطية باستخدام خوارزميات الشجرة الممتدة" (ملف PDF) . وقائع مؤتمر HLT/EMNLP .

[25] سيماس، تياجو؛ كوريا، ريون ب.؛ روشا، لويس م. (2021)، "العمود الفقري للمسافة في الشبكات المعقدة"، مجلة الشبكات المعقدة ، 9 (6) cnab021، arXiv : 2103.04668 ، doi : 10.1093/comnet/cnab021 ، PMID 38348382 .

[26] روزوم، جوردان سي؛ روشا، لويس إم (2021)، "العمود الفقري فائق القياس هو اتحاد جميع الغابات الممتدة الدنيا"، مجلة الفيزياء: التعقيد ، 5 (3): 035009، doi : 10.1088/2632-072X/ad679e ، PMID 39131403 تتضمن هذه المقالة نصًا من هذا المصدر، وهو متاح بموجب ترخيص CC BY 4.0 .

[27] سبايرا، ب.م.؛ بان، أ. (1975)، "حول إيجاد وتحديث الأشجار الممتدة وأقصر المسارات" (ملف PDF) ، مجلة SIAM للحوسبة ، 4 (3): 375-380 ، doi : 10.1137/0204032 ، MR 0378466 .

[28] هولم، جاكوب؛ دي ليشتنبرغ، كريستيان؛ ثورب، ميكيل (2001)، "خوارزميات حتمية متعددة اللوغاريتمات ديناميكية بالكامل للاتصال، والشجرة الممتدة الدنيا، والحافة الثنائية، والاتصال الثنائي"، مجلة رابطة آلات الحوسبة ، 48 (4): 723-760 ، doi : 10.1145/502090.502095 ، MR 2144928 ، S2CID 7273552 .

[29] تشين، ف.؛ هوك، د. (1978)، "خوارزميات لتحديث الأشجار الممتدة الدنيا"، مجلة علوم الحاسوب والنظم ، 16 (3): 333-344 ، doi : 10.1016/0022-0000(78)90022-3 .

[30] تشانغ، آر إس؛ ليو، إس جيه (1997)، "أشجار الامتداد ذات الحد الأدنى من التصنيف"، رسائل معالجة المعلومات ، 63 (5): 277-282 ، doi : 10.1016/s0020-0190(97)00127-0 .

[31] "كل شيء عن شجرة الامتداد ذات العنق الزجاجي" . flashing-thoughts.blogspot.ru . 5 يونيو 2010. تم الاطلاع عليه في 4 أبريل 2018 .

[32] "نسخة مؤرشفة" (PDF) . مؤرشفة من الأصل (PDF) بتاريخ 12-06-2013 . تم الاطلاع عليها بتاريخ 02-07-2014 .{{cite web}}: CS1 maint: archived copy as title ( link )

[33] غراهام، آر إل ؛ هيل، بافول (1985)، "حول تاريخ مسألة الشجرة الممتدة الدنيا"، حوليات تاريخ الحوسبة ، 7 (1): 43-57 ، Bibcode : 1985IAHC....7a..43G ، doi : 10.1109/MAHC.1985.10011 ، MR 0783327 ، S2CID 10555375

[34] نيكوس كريستوفيدس ، تحليل أسوأ الحالات لأسلوب استدلالي جديد لمشكلة البائع المتجول ، التقرير 388، كلية الدراسات العليا للإدارة الصناعية، جامعة كارنيجي ميلون، 1976.

[35] دالهاوس، إي. جونسون, دي إس ; الأماكن القريبة : سيمور, مقاطعة كولومبيا ; ياناكاكيس، م. (أغسطس 1994). "تعقيد التخفيضات المتعددة الأطراف" (PDF) . مجلة SIAM للحوسبة . 23 (4): 864-894 . دوى : 10.1137 / S0097539792225297 . مؤرشفة من الأصلي (PDF) في 24 أغسطس 2004 . تم الاسترجاع 17 ديسمبر 2012 .

[36] سوبويت، كينيث جيه؛ بلايستيد، ديفيد أ؛ رينغولد، إدوارد م. (1980). طرق استدلالية للمطابقة المثالية الموزونة . المؤتمر السنوي الثاني عشر لجمعية آلات الحوسبة حول نظرية الحوسبة (STOC '80). نيويورك، نيويورك، الولايات المتحدة الأمريكية: جمعية آلات الحوسبة. الصفحات 398-419 . doi : 10.1145/800141.804689 .

[37] سنيث، بي إتش إيه (1 أغسطس 1957). "تطبيق الحواسيب في علم التصنيف" . مجلة علم الأحياء الدقيقة العام . 17 (1): 201-226 . doi : 10.1099/00221287-17-1-201 . PMID 13475686 .

[38] أسانو، ت .؛ بهاتاشاريا، ب.؛ كيل، م.؛ ياو، ف. (1988). خوارزميات التجميع القائمة على الأشجار الممتدة الدنيا والقصوى . الندوة السنوية الرابعة حول الهندسة الحسابية (SCG '88). المجلد 1. الصفحات 252-257 . doi : 10.1145/73393.73419 .

[39] غاور، ج. س.؛ روس، ج. ج. س. (1969). "أشجار الامتداد الأدنى وتحليل التجميع بالارتباط الأحادي". مجلة الجمعية الإحصائية الملكية . ج (الإحصاء التطبيقي). 18 (1): 54-64 . doi : 10.2307/2346439 . JSTOR 2346439 .

[40] بايفينين، نينا (1 مايو 2005). "التجميع باستخدام شجرة امتداد دنيا ذات بنية شبيهة بالبنية الخالية من المقاييس". رسائل التعرف على الأنماط . 26 (7): 921-930 . Bibcode : 2005PaReL..26..921P . doi : 10.1016/j.patrec.2004.09.039 .

[41] شو، ي.؛ أولمان، ف.؛ شو، د. (1 أبريل 2002). "تجميع بيانات التعبير الجيني باستخدام منهجية نظرية الرسم البياني: تطبيق لأشجار الامتداد الأدنى" . المعلوماتية الحيوية . 18 (4): 536-545 . doi : 10.1093/bioinformatics/18.4.536 . PMID 12016051 .

[42] دلال، يوجين ك.؛ ميتكالف، روبرت م. (1 ديسمبر 1978). "إعادة توجيه حزم البث عبر المسار العكسي" . اتصالات رابطة آلات الحوسبة . 21 (12): 1040-1048 . doi : 10.1145/359657.359665 . S2CID 5638057 .

[43] ما، ب.؛ هيرو، أ.؛ جورمان، ج.؛ ميشيل، أ. (2000). تسجيل الصور باستخدام خوارزمية الشجرة الممتدة الدنيا (ملف PDF) . المؤتمر الدولي لمعالجة الصور. المجلد 1. الصفحات 481-484 . doi : 10.1109/ICIP.2000.901000 . مؤرشف (ملف PDF) من النسخة الأصلية بتاريخ 9 أكتوبر 2022.

[44] P. Felzenszwalb، D. Huttenlocher: تجزئة الصور الفعالة القائمة على الرسم البياني. IJCV 59(2) (سبتمبر 2004)

[45] سوك، مينسو؛ سونغ، أوهيونغ (1 يونيو 1984). "استخلاص الميزات المنحنية باستخدام الأشجار الممتدة الدنيا". رؤية الحاسوب، والرسومات، ومعالجة الصور . 26 (3): 400-411 . doi : 10.1016/0734-189X(84)90221-4 .

[46] تابيا، إرنستو؛ روخاس، راؤول (2004). "التعرف على التعبيرات الرياضية المكتوبة بخط اليد على الإنترنت باستخدام بناء شجرة الامتداد الأدنى وهيمنة الرمز" (ملف PDF) . التعرف على الرسومات. التطورات الحديثة والآفاق . سلسلة محاضرات في علوم الحاسوب. المجلد 3088. برلين هايدلبرغ: سبرينغر-فيرلاغ. الصفحات 329-340 . ISBN 978-3-540-22478-5تمت أرشفة الملف (PDF) من النسخة الأصلية بتاريخ 2022-10-09.

[47] أولسون، هـ. (2004). تطبيق مرشحات FIR منخفضة التعقيد باستخدام شجرة الامتداد الدنيا . المؤتمر الثاني عشر لجمعية مهندسي الكهرباء والإلكترونيات في منطقة البحر الأبيض المتوسط للهندسة الكهربائية (MELECON 2004). المجلد 1. الصفحات 261-264 . doi : 10.1109/MELCON.2004.1346826 .

[48] أسونساو، آر إم؛ مولودية نيفيس؛ جي كامارا؛ جيم دا كوستا فريتاس (2006). "تقنيات الأقلمة الفعالة للوحدات الجغرافية الاجتماعية والاقتصادية باستخدام الحد الأدنى من الأشجار الممتدة" . المجلة الدولية لعلوم المعلومات الجغرافية . 20 (7): 797– 811. بيب كود : 2006IJGIS..20..797A . دوى : 10.1080/13658810600665111 . S2CID 2530748 .

[49] ديفيليرز، ج.؛ دور، ج. س. (1 أبريل 1989). "الفعالية الاستدلالية لطريقة الشجرة الممتدة الدنيا (MST) في علم السموم". علم السموم البيئية والسلامة البيئية . 17 (2): 227-235 . Bibcode : 1989EcoES..17..227D . doi : 10.1016/0147-6513(89)90042-0 . PMID 2737116 .

[50] موري، هـ.؛ تسوزوكي، س. (1 مايو 1991). "طريقة سريعة لتحليل قابلية الملاحظة الطوبولوجية باستخدام تقنية الشجرة الممتدة الدنيا". معاملات IEEE لأنظمة الطاقة . 6 (2): 491-500 . Bibcode : 1991ITPSy...6..491M . doi : 10.1109/59.76691 .

[51] فيليبين، جيمس جيه؛ كافادار، كارين ؛ شير، دوغلاس آر. (1 يناير 1983). "اختبار تجانس الأسطح ثنائية الأبعاد". النمذجة الرياضية . 4 (2): 167-189 . doi : 10.1016/0270-0255(83)90026-X .

[52] كالابا، روبرت إي. (1963)، نظرية الرسم البياني والتحكم الآلي (ملف PDF) ، مؤرشف من الأصل (ملف PDF) في 21 فبراير 2016

[53] مانتينيا، آر إن (1999). الهيكل الهرمي في الأسواق المالية . المجلة الأوروبية للفيزياء ب - المادة المكثفة والأنظمة المعقدة، 11(1)، 193-197.

[54] دجوهاري، م.، وجان، س. (2015). مشكلة الأمثلية في طوبولوجيا الشبكة في تحليل سوق الأسهم . فيزيكا أ: الميكانيكا الإحصائية وتطبيقاتها، 419، 108-114.

[

[

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]

[ 26 ]

[ 27 ]

[ 28 ]

[ 29 ]

[ 30 ]

[ 31 ]

[ 32 ]

[ 33 ]

[ 34 ]

[ 35 ]

[ 36 ]

[ 37 ]

[ 38 ]

[ 39 ]

[ 40 ]

[ 41 ]

[ 42 ]

[ 43 ]

44

[ 45 ]

[ 46 ]

[ 47 ]

[ 48 ]

[ 49 ]

[ 50 ]

[ 51 ]

[ 52 ]

[ 53 ]

[ 54 ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗