چکیده N گره را روی N دراین مقاله در نظر داریم تا یک درخت با رأس تعبیه کنیم این تعبیه باید n نقطه داخل یک چند ضلعی با به گونهای باشد که تعداد خمهای درخت حاصل حداقل شود . ایدهی اصلی الگوریتم جدید مدل کردن مسئله به صورت مسئلهی تطبیقدهی گرافها واستفاده از الگوریتمهای تطبیقدهی گراف است که منجر به بررسی مسئله ی فاصله ی پیوندی و مسیر با حداقل تعداد لینک می شود، سپس با به کار بردن مفهوم تصحیح خطا ویافتن یک تابع هزینه ی مناسب و استفاده از روش تجزیهی گرافها، تطبیقدهی گراف ها ر ا با حداقل هزینه برای به حداقل رساندن تعداد خم انجام میدهیم است. O(N2n+N و الگوریتم دارای پیچیدگی محاسباتی ( 4 کلیدواژگان: تعبیه ی هندسی، تعبیه ی درخت در مجموعه نقاط، به حداقل رساندن خم، تطبیقدهی گراف.

واژه‌های کلیدی: تعبیه ی هندسی، تعبیه ی درخت در مجموعه نقاط، به حداقل رساندن خم، تطبیقدهی گراف.

متن کامل [PDF 3836 kb]   (1890 دریافت)