دور همیلتونی

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

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