حساب دوگان گراف و کاربرد های GIS

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

Keywords:

گراف- دوگان گراف-دور اویلری , دور همیلتونی , طراحی سفر