گراف (ساختار داده): تفاوت میان نسخهها
Rey dehghan (بحث | مشارکتها) اضافه کردن جدول |
Rey dehghan (بحث | مشارکتها) تغییرات نهایی |
||
خط ۸۹: | خط ۸۹: | ||
این نوع دوگان گراف بیشتر در مسائلی که در آنها نیاز به تقسیمبندی فضا است استفاده شدهاست. به عنوان مثال الگوریتم تولید پلیگونهای تیسن از روی تعدا نقاط یمی از موارد کاربرد این نوع دوگان است. |
این نوع دوگان گراف بیشتر در مسائلی که در آنها نیاز به تقسیمبندی فضا است استفاده شدهاست. به عنوان مثال الگوریتم تولید پلیگونهای تیسن از روی تعدا نقاط یمی از موارد کاربرد این نوع دوگان است. |
||
از دوگان ورونی گراف برای تقریب الگوریتمهای کوتاهترین مسی بر مبنای معیار فاصله استفاده کردهاند. چون تعداد گرهها در دوگان ورونی گراف به مراتب کمتر از گراف اولیه است، به همین دلیل آنها نشان دادهاند که جواب تقریبی مسئله کوتاهترین مسیر بر مبنای فاصله را میتوان در دوگان ورونی گراف اولیه محاسبه کرد. |
از دوگان ورونی گراف برای تقریب الگوریتمهای کوتاهترین مسی بر مبنای معیار فاصله استفاده کردهاند. چون تعداد گرهها در دوگان ورونی گراف به مراتب کمتر از گراف اولیه است، به همین دلیل آنها نشان دادهاند که جواب تقریبی مسئله کوتاهترین مسیر بر مبنای فاصله را میتوان در دوگان ورونی گراف اولیه محاسبه کرد. |
||
Wallgrun |
Wallgrun <ref name=":0">{{یادکرد کتاب|نشانی=http://dx.doi.org/10.1007/978-3-642-10345-2_6|عنوان=Global Mapping: Minimal Route Graphs Under Spatial Constraints|نام خانوادگی=Wallgrün|نام=Jan Oliver|تاریخ=2009-11-10|ناشر=Springer Berlin Heidelberg|شابک=9783642103025|مکان=Berlin, Heidelberg|صفحات=113–146}}</ref>نشان دادهاست که از دوگان ورونی گراف میتوان در مسائل طراحی حرکت رباتها استفاده برد. طراحی حرکت یک ربات در یک محدوده بسته باید بر اساس مشاهدات لحظهای ربات انجام شود به نحوی که بدون برخورد با موانع و دیوارها با پیمودن کوتاهترین مسیر به مقصد مورد نظر برسد. وی نشان دادهاست که ربات مورد نظر باید بر روی دوگان ورونی گراف مشاهداتش حرکت کند. وی همچنین چگونگی استخراج این دوگان ورونی گراف را بر اساس مشاهدات ربات بیان کردهاست<ref name=":0" />. |
||
== همچنین ببینید == |
|||
* [[پیمایش گراف]] |
|||
* [[پایگاه دادههای گراف]] |
|||
* [[نظریه گراف]] |
|||
* [[الگوریتم جستجوی عمق اول|جستجوی عمق اول]] |
|||
* [[الگوریتم جستجوی اول سطح|جستجوی سطح اول]] |
|||
== الگوریتمهای گراف == |
== الگوریتمهای گراف == |
||
خط ۹۷: | خط ۱۰۶: | ||
== منابع == |
== منابع == |
||
{{پانویس}} |
{{پانویس}} |
||
⚫ | {{یادکرد|فصل= 26|کتاب=[[مقدمهای بر الگوریتمها]]|ناشر= MIT Press and McGraw-Hill|چاپ= |شهر= |کوشش= |ویرایش= 2nd edition |سال= 2001 |شابک=ISBN 0-262-03293-7 |نویسنده= [[توماس اچ کورمن]]، [[Charles E. Leiserson]], [[رونالد ریوست]]، and [[کلیفورد استین]]|نویسندگان سایر بخشها=|ترجمه=|صفحه=696–697 |زبان=en |مقاله= |ژورنال= |نشریه= |تاریخ= |دوره= |شماره= |شاپا=}} |
||
{{چپچین}} |
|||
⚫ | |||
{{پایان چپچین}} |
{{پایان چپچین}} |
||
⚫ | |||
<!-- [[گراف (داده ساختار]]) -->* Wallgrün, J. O. (2008)”Hierarchical Voronoi Graphs- .Spatial representation and reasoning for mobile robots,” London: Springer Winter, S. (2002a) “Modeling the costs of turns in- .route planning”, GeoInformatica, 6(4), pp.345-360 Winter, S. (2002b) “Route specifications with- a linear dual graph”, Symposium on Geospatial .Theory,Processing and Ap |
|||
⚫ | |||
[[رده:گرافها]] |
[[رده:گرافها]] |
||
[[رده:نوع داده انتزاعی]] |
[[رده:نوع داده انتزاعی]] |
نسخهٔ ۸ ژوئن ۲۰۱۸، ساعت ۱۱:۵۷
در علوم رایانه یک گراف، دادهساختاری انتزاعی است که به صورت گراف جهت دار و بدون جهت پیاده سازی میشود و . هدفش به کارگیریِ مفهوم گراف از ریاضیات و به خصوص نظریه گراف است.
یک داده ساختار گراف اساساً از یک مجموعهٔ متناهیِ زوجهای مرتب موسوم به یال شامل واحدهایی به نام رأس یا گره تشکیل میشود؛ همانطور که در ریاضیات به ازای یک یال (u,v) میگوییم که u به v میرود یا u و v مجاورند. همچنین میتوان به هر یال یک گراف یک عدد نسبت داد که در این صورت گراف وزن دار بوجود می آید .
عملیات ها
عملیات ابتدایی ارائه شده توسط یک ساختار داده گراف G معمولا شامل [۱]:
- مجاورت (G, x, y): امتحان اینکه آیا یک یال از رأس x به رأس y وجود دارد؛
- همسایه ها (G, x):لیست تمام رأس ها را به طوری که یک یال از رأس x به رأس y وجود دارد؛
- درج راس(G, x) :راس x را در صورت عدم وجود اضافه می کند؛
- حدف راس (G, x) :راس x را در صورت وجود حذف می کند ؛
- درج یال (G, x, y): یک یال از رأس x به رأس y اضافه می کند ؛
- حذف یال (G, x, y): یال از رأس x به رأس y را در صورت وجود حذف می کند؛
- گرفتن ارزش راس (G, x): مقدار مربوط به رأس x را برمی گرداند؛
- مقداردهی راس (G, x,v) :مقدار مربوط به رأس x را v قرار می دهد؛
در گراف وزن دار دستورات زیر نیز وجود دارد :
- گرفتن ارزش یال (G, x,y):مقدار مربوط به یال گذرنده از (x، y) را باز می گرداند؛
- مقدار دهی یال (G, x, y, v): مقدار مربوط به لبه (x، y) را به v تنظیم می کند؛
نمایش گرافها
ساختار داده های مختلفی برای نمایش گراف ها در عمل استفاده می شود :
لیست مجاورت [۲]
راس ها به عنوان سوابق یا اشیا ذخیره می شوند و هر رأس لیستی از رأس های مجاور را ذخیره می کند. این ساختار داده ها اجازه ذخیره سازی داده های اضافی در رأس ها را می دهد. داده های اضافی را می توان ذخیره کرد اگر یال ها نیز به عنوان اشیا ذخیره شوند، در این صورت هر رأس یال های حادث بر خود را ذخیره می کند و هر یال رأس حاد خود را ذخیره می کند.
ماتریس مجاورت
یک ماتریس دو بعدی، که در آن ردیف ها نشان دهنده رأس مبدا و ستون ها نشان دهنده راس مقصد هستند. داده ها در یال ها و رأس ها باید در خارج از ماتریس ذخیره شوند. فقط هزینه یک یال می تواند بین هر جفت رأس ذخیره شود.
ماتریس وقوع
یک ماتریس بولی دو بعدی، که در آن ردیف ها نشان دهنده رأس ها و ستون هانشان دهنده یال ها هستند. ورودی ها نشان می دهند که آیا رأس یک ردیف به یال یک ستون متصل است یا خیر.
جدول زیر، هزینه پیچیدگی زمانی را برای انجام عملیات مختلف در گراف ها، برای هر یک از این نمایش ها، | V | نشان دهنده تعداد رأس ها و | E | تعداد لبه هاست .
لیست پیوندی | ماتریس مجاورت | ماتریس وقوع | |
---|---|---|---|
ذخیره گراف | |||
درج راس | |||
درج یال | |||
حذف راس | |||
حذف یال | |||
سوال: آیا رأس X و Y مجاور هستند؟
(فرض بر این است که موقعیت ذخیره سازی آنها شناخته شده است) |
هر سه راه قابل اجرا برای گراف جهت دار و بدون جهت است. نمایش لیست مجاورت معمولاً ترجیح داده میشود چرا که یک روش فشرده برای نمایش گرافهای کم یال فراهم میکند. اگر گراف متراکم یا همان پر یال باشد، نمایشِ ماتریس مجاورت مقدم است. همچنین در مواقعی که نیاز داریم سریعاً بدانیم که آیا به ازای دو رأس داده شده یال متصلکنندهٔ بینشان وجود دارد یا خیر، از لیست مجاورت استفاده میکنیم. طبقهبندی انواع دوگان گراف دوگان گرافهایی که تاکنون در علوم مختلف تعریف و استفاده شدهاند، بر اساس نحوه استخراج به دو گروه بر مبنای گراف اولیه و مفهومی تقسیمبندی شدهاند. در ادامه وجه تسمیه و مشخصات آنها شرح داده شدهاند.
دوگان گراف بر مبنای گراف اولیه
این نوع دوگان گراف از گراف اولیه استخراج میشود. به عبارت این نوع دوگان گراف از گراف اولیه دیگر بعد از اینکه گراف اولیه بر اساس دیدگاههای رایج آن استخراج شد، سپس دوگان گراف آن بر اساس قوانین خاصی استخراج میشود. در این طبقه دو نوع دوگان یعنی دوگان گراف ورونی و دوگان گراف خطی را میتوان گنجاند. دوگان گراف ورونی تعریف: دوگان گراف ورونی یک گراف مسطح، گرافی است که گرههای آن نماهای گراف اولیه بوده و یالهای آن بیانگر ارتباطات همجواری در گراف اولیه باشد این نوع دوگان دارای ویژگیهای زیر است: -دوگان گراف ورونی یک گراف مسطح یک گراف مسطح است (که ممکن است یال موازی و حلقه نیز داشته باشد(. - اگر G یک گراف همبند وG‘، دوگان گراف ورونی آن باشد، آنگاه G نیز، دوگان گراف ورونیG‘ خواهد بود. -- دوگانهای گراف ورونی یک گراف منحصر به فرد نیستند ویک گراف میتواند چندین دوگان گراف ورونی غیر یک ریخت داشته باشد. زیرا با تغییر نمایش گراف اولیه دوگان گراف ورونی آن نیز تغییر میکند این نوع دوگان گراف بیشتر در مسائلی که در آنها نیاز به تقسیمبندی فضا است استفاده شدهاست. به عنوان مثال الگوریتم تولید پلیگونهای تیسن از روی تعدا نقاط یمی از موارد کاربرد این نوع دوگان است. از دوگان ورونی گراف برای تقریب الگوریتمهای کوتاهترین مسی بر مبنای معیار فاصله استفاده کردهاند. چون تعداد گرهها در دوگان ورونی گراف به مراتب کمتر از گراف اولیه است، به همین دلیل آنها نشان دادهاند که جواب تقریبی مسئله کوتاهترین مسیر بر مبنای فاصله را میتوان در دوگان ورونی گراف اولیه محاسبه کرد.
Wallgrun [۳]نشان دادهاست که از دوگان ورونی گراف میتوان در مسائل طراحی حرکت رباتها استفاده برد. طراحی حرکت یک ربات در یک محدوده بسته باید بر اساس مشاهدات لحظهای ربات انجام شود به نحوی که بدون برخورد با موانع و دیوارها با پیمودن کوتاهترین مسیر به مقصد مورد نظر برسد. وی نشان دادهاست که ربات مورد نظر باید بر روی دوگان ورونی گراف مشاهداتش حرکت کند. وی همچنین چگونگی استخراج این دوگان ورونی گراف را بر اساس مشاهدات ربات بیان کردهاست[۳].
همچنین ببینید
الگوریتمهای گراف
الگوریتمهای گراف زمینهٔ مهم علاقه در علوم رایانه به حساب میآیند. برخی از عملیاتِ مربوط به گرافها عبارتند از: پیدا کردن مسیری بین دو گره، مانند جستجوی عمق اول و جستجوی سطح اول و پیدا کردن کوتاهترین مسیر از یک گره به دیگری، مانند الگوریتم دیکسترا. یک روش برای پیدا کردن کوتاهترین مسیر بین هر گره و تمام گرههای دیگر هم وجود دارد به نام الگوریتم فلوید-وارشال.
منابع
- ↑ Bowyer, A (2002-11). "LEDA—a platform for combinatorial and geometric computing Kurt Mehlhorn and Stefan Näher, Cambridge University Press, Cambridge, UK, 1999, £50 ($80), 1018 pages, ISBN 0-521-56329-1". Computer-Aided Design. 34 (13): 1047–1048. doi:10.1016/s0010-4485(01)00159-2. ISSN 0010-4485.
{{cite journal}}
: Check date values in:|date=
(help) - ↑ Goodrich, Michael T.; Tamassia, Roberto (2001). "Teaching internet algorithmics". Proceedings of the thirty-second SIGCSE technical symposium on Computer Science Education - SIGCSE '01. New York, New York, USA: ACM Press. doi:10.1145/364447.364561. ISBN 1581133294.
- ↑ ۳٫۰ ۳٫۱ Wallgrün، Jan Oliver (۲۰۰۹-۱۱-۱۰). Global Mapping: Minimal Route Graphs Under Spatial Constraints. Berlin, Heidelberg: Springer Berlin Heidelberg. صص. ۱۱۳–۱۴۶. شابک ۹۷۸۳۶۴۲۱۰۳۰۲۵.
توماس اچ کورمن، Charles E. Leiserson, رونالد ریوست، and کلیفورد استین (2001), "26", مقدمهای بر الگوریتمها (به انگلیسی) (2nd edition ed.), MIT Press and McGraw-Hill, p. 696–697 {{citation}}
: |edition=
has extra text (help)