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

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

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

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

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

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

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

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

اندازه مورد انتظار برای تعداد زیادی از نقاط توسط J. Michael Steele تعیین شد. اگر f چگالی تابع احتمال برای نقاط باشد برای n بزرگ و $d \neq 1$ اندازه درخت مینیمم اقلیدسی حدود: $c(d) n^{\frac{d-1}{d}} \int_{\Bbb{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