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

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

مسئله مکان یابی، چرخ گراف ها، آنالیز پیچیدگی