الگوریتم مسئله مکان‎یابی p- میانه روی چرخ گراف ها

Publish Year: 1398
نوع سند: مقاله کنفرانسی
زبان: Persian
View: 354

This Paper With 9 Page And PDF and WORD Format Ready To Download

  • Certificate
  • من نویسنده این مقاله هستم

استخراج به نرم افزارهای پژوهشی:

لینک ثابت به این Paper:

شناسه ملی سند علمی:

TIET02_009

تاریخ نمایه سازی: 24 شهریور 1398

Abstract:

در این مقاله به مطالعه و بررسی مسائل p- میانه روی چرخ گراف ها می پردازیم. فرض کنید G=(V,E) یک گراف با تابع طول +l:E⟶R و وزن های راسی نامنفی باشد. هدف مسائل p- میانه، تعیین مکان p سرویس دهنده روی یال ها یا راس های G می باشد بطوری که مجموع کوتاه ترین فواصل وزن دار از هر راس به نزدیک ترین سرویس دهنده مینیمم گردد. در اینجا برای مسئله مکان یابی 1- میانه روی چرخ گراف ها یک الگوریتم خطی پیشنهاد می گردد که با استفاده از این الگوریتم خطی می توان مقدار تابع هدف تمام رئوس در دور را بدست آورد و مقادیر تابع هدف v_0 و رئوس دور را مقایسه کرده و جواب بهینه را بدست آورد. در نتیجه پیچیدگی زمانی مسئله 1- میانه روی چرخ O(n) است که در آن n تعداد رئوس گراف می باشد. در نهایت با یک مثال به طور کامل کاربرد الگوریتم پیشنهادی را تشریح می کنیم.

Authors

رویا نعمتی

کارشناسی ارشد، گروه آموزشی ریاضی، دانشگاه تبریز،