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

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