گراف و کاربرد آن در GIS

کاربرد سیستم اطلاعات جغرافیایی و سنجش از دور در برنامه‌ریزی

دوره 12، شماره 2 - شماره پیاپی 44، شهریور 1400، صفحه 41-51   

نوع مقاله: مقاله مروری

نویسنده

سمانه بهرامیان^*

گروه ریاضی، دانشکده فنی و مهندسی، دانشگاه ازاد اسلامی، سمنان، ایران

چکیده

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

کلیدواژه‌ها

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

مراجع