حساب دوگان گراف و کاربرد های GIS | ||
| نشریه سنجش از دور و GIS ایران | ||
| مقاله 1، دوره 1، شماره 1، تیر 1388، صفحه 1-16 اصل مقاله (778.31 K) | ||
| نوع مقاله: مقاله پژوهشی | ||
| نویسندگان | ||
| جواد صابریان* 1؛ محمد رضا ملک1؛ مجید همراه1؛ استفن وینتر2 | ||
| 1دانشگاه خواجه نصیرالدین طوسی | ||
| 2دانشگاه ملبورن استرالیا | ||
| چکیده | ||
| برای حل برخی از مشکلات یا برای ساده سازی آنالیز ها در گراف،می توان تغییراتی را در ساختار آن ایجاد کرد. دوگان گراف یکی از مصادیق این تغییر محسوب می شود . دوگان گراف خطی یکی از انواع تعریف شده دوگان گراف است که برای بیان گراف های دارای گره ها ی وزن دار پیشنهاد شده است. در این مقاله مفهومی به عنوان حساب دوگان گراف خطی،بر مبنای این دوگان گراف معرفی شده است. برای این منظور،دوگان خطی(LD1) و دوگان خطی معکوس (LD-1) معرفی،و نحوه استخراج آنها شرح داده می شود . همچنین نشان داده خواهد شد که این چهار چوب می تواند کاربرد های فراوانی داشته باشد .یکی از مهمترین کاربرد های آن،یافتن دور همیلتونی در گراف است . به عبارت دیگر،با استفاده از تبدیلات بین دو گان گراف و گراف اولیه می توان دور های همیلتونی را ، که تا کنون یافتن انها در گراف بسیار دشوار بوده است،به دور های ایولری تبدیل کرد. بدین وسیله حل مسائل بسیار ساده تر خواهد شد. دور همیلتونی کاربرد های فراوانی در حوزه GIS و علوم مرتبط با اطلاعات مکانی دارد. از آن جمله می توان به طراحی مسیر در حمل و نقل، مدیریت بحران،مخابرات و شبکه های آی و برق و گاز اشاره کرد. در این زمینه، نمونه موردی کوچکی که روش ابداعی در این مقاله در آن به اجرا در آمده نیز آورده شده است. | ||
| کلیدواژه‌ها | ||
| گراف- دوگان گراف-دور اویلری؛ دور همیلتونی؛ طراحی سفر | ||
| عنوان مقاله [English] | ||
| Linear Dual Graph Calculus and its Applications in GIS | ||
| چکیده [English] | ||
| In order to solve some problems, as well as to simplify or facilitate some analyses in graphs, some changes can be made in the graphs. Dual graph is one of these changes. Linear dual graph is a type of dual graph that is proposed for presenting graphs with weighted nodes. In this paper, linear dual graph calculus that is based on the linear dual graph is introduced. For this purpose, at first, Linear Dual (LD1) and inverse Linear Dual (LD-1) is introduced, and then, the way of their extraction is explained. After that some applications of this calculus is explained. One of its most important applications is in specification the Hamiltonian cycle in graphs. In other words, by transportation between linear dual graph and the primal graph,we can convert the Hamiltonian cycles whose specification has always been so difficult, to Eulerian ones which can be easily recognized. | ||
| کلیدواژه‌ها [English] | ||
| Graph, Linear dual graph, Eulerian cycle, Hamiltonian cycle, Trip planning | ||
| مراجع | ||
|
| ||
|
آمار تعداد مشاهده مقاله: 3,183 تعداد دریافت فایل اصل مقاله: 1,694 |
||