گراف و کاربرد آن در GIS
محورهای موضوعی : کاربرد GIS&RS در توریسم
سمانه بهرامیان
1
(گروه ریاضی، دانشکده فنی و مهندسی، دانشگاه ازاد اسلامی، سمنان، ایران)
کلید واژه: دوگان گراف, دور همیلتونی, دور اویلری, شبکه حمل و نقل, مسیر بهینه,
چکیده مقاله :
یکی از مهمترین کاربردهای سیستم های اطلاعات مکانی، در مبحث مدیریت حمل و نقل است. در این زمینه قابلیت های تجزیه و تحلیل شبکه در سیستم های اطلاعات مکانی از جمله محاسبه کوتاهترین مسیر، می تواند مفید واقع گردد. گراف و تئوری های آن نقش مهمی در انجام آنالیزهای شبکه GIS دارند. برای حل برخی از مشکلات گراف یا ساده سازی آنالیزها در گراف، می توان تغییراتی در ساختار آن ایجاد کرد. شبیه سازی به وسیله گراف نشان می دهد که توانایی جابه جایی سیستم تا حد زیادی به توپولوژی شبکه حمل و نقل بستگی دارد. به طور کلی یک شبکه برنامه ریزی شده می تواند وسایل نقلیه بیشتری را در خود جا دهد و توانایی جابه جایی کلی آن بسیار بیشتر از یک شبکه در حال رشد خود سازمان دهی شده است. تاکنون نظریه های متعدد و بسیار کاربردی از جمله الگوریتمهای محاسبه کوتاه ترین مسیر برای حل مسائل گوناگون در گرافها ارایه و استفاده شده اند. اما برای بعضی از مسائل مهم و کاربردی راه حل و تئوری مناسبی بر مبنای گراف ارایه نشده است. به همین علت، همانند بسیاری از نظریه های دیگر که در آنها راه حلهایی بر مبنای فضاهای دوگان ارایه شده، در گرافها نیز چنین فضاهایی تعریف و استفاده شده اند. به این صورت که ابتدا مساله موجود در گراف اولیه را به یک فضای دوگان مناسب برده و پس از حل، نتایج به فضای اولیه برگردانده می شود. در این مقاله نشان داده خواهد شد که از مفاهیم دوگان گراف و با تغییر در ساختار و شکل گراف اولیه می توان مسایل با پیچیدگی بسیار زمانی را در گراف اولیه به مسایلی ساده تر و قابل حل تر تبدیل کرد. همچنین، به بحث و بررسی چند کاربرد متنوع در زمینه یافتن کوتاهترین مسیر در مسائل حوزه حمل پرداخته خواهد شد.
One of the most important applications of spatial information systems is in the field of transportation management. In this regard,Today, the use of information and communication technologies has presented a powerful option for transportation management to experts. These solutions are now being used as a core component of transportation systems operations around the world. On the other hand, today's life involves a large amount of movement and mobility, which is done through cars, ships, rail vehicles and airplanes, and so on. Spatial information systems in the field network analysis capabilities in spatial information systems, including the calculation of the shortest path, can be useful. Graphs and their theories play an important role in GIS network analysis. To solve some problems of the graph or to simplify the analysis in the graph, changes can be made to its structure. Graph simulations show that the mobility of the system depends to a large extent on the transport network topology. In general, a planned network can accommodate more vehicles, and its overall mobility is much greater than a self-organized growing network. In this article, while introducing graph capabilities in problem solving, several different applications in finding the shortest path in transportation problems will be discussed..
_||_