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

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

کلیدواژه ها:

گراف ، دوگان گراف ، بهترین مسیر ، شبکه حمل ونقل ، GIS