ارایه طبقه بندی از انواع گراف دوگان و بکارگیری آنها در بهبود آنالیزهای مسیریابی

Abstract

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