درخت فراگیر مینیمم اقلیدسی

درخت فراگیر مینیمم اقلیدسی درخت فراگیر مینیمم اقلیدسی درخت فراگیر مینیمم از مجموعه‌ای از n نقطه در صفحه (یا به‌طور کلی در ℝ بعدی)، که در آن وزن یال بین هر جفت از نقاط فاصله بین آن دو نقطه است. به عبارت ساده‌تر، اتصال مجموعه‌ای از نقاط با استفاده از خطوطی که مجموع طول همه خطوط به حداقل رسیده است و هر نقطه توسط خطوط به نقاط دیگر راه دارد. پیدا کردن درخت فراگیر مینیمم اقلیدسی در صفحه با پیچیدگی زمانی(O(nlogn و حافظه(O(n انجام پذیر است. در ابعاد بالاتر (D ≥ ۳)، پیدا کردن یک الگوریتم بهینه یک مسئله حل نشده باقی‌مانده است.

یک درخت فراگیر مینیمم اقلیدسی با ۲۵ نقطه تصادفی

الگوریتم‌های محاسبه

ساده‌ترین الگوریتم محاسبهٔ درخت فراگیر مینیمم اقلیدسی برای n نقطه محاسبهٔ گراف کامل با نقاط و مشخص کردن وزن یال‌ها و انجام الگوریتم مینیمم درخت فرگیر (کروسکال یا پریم) روی آن است. چون درخت کامل (n²) یال دارد محاسبه با این الگوریتم به(Ω(n2 زمان نیاز دارد. الگوریتم بهتر برای محاسبهٔ درخت فراگیر مینیمم اقلیدسی استفاده از مثلث‌بندی دیلانی است:

1. محاسبهٔ مثلث‌بندی دیلانی در زمان(O(n log n و با حافظهٔ (o(n. چون با مثلث‌بندی دیلانی هر راس حداکثر سه یال خواهد داشت تعداد یال‌ها (o(n خواهد بود.
2. محاسبهٔ وزن یال‌ها با توجه با فاصلهٔ نقاط.
3. اجرای الگوریتم مینیمم درخت فرگیر (الگوریتم کروسکال یا الگوریتم پریم) روی این گراف.

نتیجهٔ نهایی در زمان(o(nlogn و با حافظه ی(o(n بدست می‌آید.

اندازهٔ مورد انتظار

اندازه مورد انتظار برای تعداد زیادی از نقاط توسط J. Michael Steele تعیین شد. اگر f چگالی تابع احتمال برای نقاط باشد برای n بزرگ و ${\displaystyle d\neq 1}$ اندازه درخت مینیمم اقلیدسی حدود: ${\displaystyle c(d)n^{\frac {d-1}{d}}\int _{\mathbb {R} ^{d}}f(x)^{\frac {d-1}{d}}dx}$

خواهد بود که در آن(c(d ثابتی است که با توجه به بعد d تخمین زده می‌شود.

کاربردها

کاربرد آشکار مینیمم درخت پوشای اقلیدسی برای پیدا کردن ارزانترین شبکه‌ای از سیم یا لوله برای اتصال مجموعه‌ای از مکان، با فرض اینکه هزینهٔ پیوندها یک مقدار ثابت در هر واحد طول است. گرچه این روش در صورت قطع شدن یکی از خطوط شبکه را به دو قسمت تقسیم می‌کند لذا در اکثر شبکه‌ها درخت k بار متصل را پیاده‌سازی می‌کنند.

پانویس

منابع

• Smith College: The Open Problems Project: Problem 5: Euclidean Minimum Spanning Tree
• Max-Planck-Institut fuer Informatik: Exercise solutions, by Kavitha Telikepalli (Postscript)
• STANN (Michael Connor, Piyush Kumar and Samidh Chatterjee): A C++ library that can compute Euclidean Minimum Spanning Trees in low dimensions