دوگان گراف

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

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

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