گراف (ساختار داده)

از ویکی‌پدیا، دانشنامهٔ آزاد
(تغییرمسیر از گراف (داده ساختار))
پرش به: ناوبری، جستجو

در علوم رایانه یک گراف، داده‌ساختاری انتزاعی است که هدفش به کارگیریِ مفهوم گراف از ریاضیات است. یک داده ساختار گراف اساساً از یک مجموعهٔ متناهی ِ زوج‌های مرتب- موسوم به یال- شامل واحدهایی به نام رأس یا گره تشکیل می‌شود؛ همانطور که در ریاضیات به ازای یک یال (u,v) می‌گوییم که u به v می‌رود یا u و v مجاوراند.

نمایش گراف‌ها[ویرایش]

به طور معمول دو راه برای نمایش یک گراف (G=(V,E وجود دارد: به صورت مجموعه‌ای از لیست‌های مجاورت یا به صورت یک ماتریس مجاورت. هر دو راه قابل اجرا برای گراف‌های جهت‌دار و بدون جهت است. نمایش لیست مجاورت معمولاً ترجیح داده می‌شود چرا که یک روش فشرده برای نمایش گراف‌های کم یال فراهم می‌کند.اگرگراف متراکم یا همان پر یال باشد، نمایشِ ماتریس مجاورت مقدم است. همچنین در مواقعی که نیاز داریم سریعاً بدانیم که آیا به ازای دو رأس داده شده یال متصل کنندهٔ بینشان وجود دارد یا خیر، از لیست مجاورت استفاده می‌کنیم. طبقه بندي انواع دوگان گراف دوگان گرافهايي که تا کنون در علوم مختلف تعريف و استفاده شده اند، بر اساس نحوه استخراج به دو گروه بر مبناي گراف اوليه و مفهومي تقسيم بندي شده اند. در ادامه وجه تسميه و مشخصات آنها شرح داده شده اند.

دوگان گراف بر مبناي گراف اوليه

اين نوع دوگان گراف از گراف اوليه استخراج مي شود. به عبارت اين نوع دوگان گراف از گراف اوليه ديگر بعد از اينکه گراف اوليه بر اساس ديدگاههاي رايج آن استخراج شد، سپس دوگان گراف آن بر اساس قوانين خاصي استخراج مي شود. در اين طبقه دو نوع دوگان يعني دوگان گراف وروني و دوگان گراف خطي را مي توان گنجاند. دوگان گراف وروني تعريف: دوگان گراف وروني يك گراف مسطح، گرافي است كه گرههاي آن نماهاي گراف اوليه بوده و يالهاي آن بيانگر ارتباطات همجواري در گراف اوليه باشد اين نوع دوگان داراي ويژگيهاي زير است: -دوگان گراف وروني يك گراف مسطح يك گراف مسطح است (كه ممكن است يال موازي و حلقه نيز داشته باشد(. - اگر G يك گراف همبند وG‘ ، دوگان گراف وروني آن باشد، آنگاه G نيز، دوگان گراف ورونيG‘ خواهد بود. -- دوگانهاي گراف وروني يك گراف منحصر به فرد نيستند ويك گراف ميتواند چندين دوگان گراف وروني غير يك ريخت داشته باشد. زيرا با تغيير نمايش گراف اوليه دوگان گراف وروني آن نيز تغيير مي‌كند اين نوع دوگان گراف بيشتر در مسائلي كه در آنها نياز به تقسيم بندي فضا است استفاده شده است. به عنوان مثال الگوريتم توليد پليگونهاي تيسن از روي تعدا نقاط یمی از موارد کاربرد این نوع دوگان است. از دوگان وروني گراف براي تقريب الگوريتمهاي کوتاه ترين مسي بر مبناي معيار فاصله استفاده کرده اند. چون تعداد گرهها در دوگان وروني گراف به مراتب کمتر از گراف اوليه است، به همين دليل آنها نشان داده اند که جواب تقريبي مساله کوتاه ترين مسير بر مبناي فاصله را ميتوان در دوگان وروني گراف اوليه محاسبه کرد. Wallgrun و]2008[ نشان داده است که از دوگان وروني گراف مي توان در مسائل طراحي حرکت رباتها استفاده برد. طراحي حرکت يک ربات در يک محدوده بسته بايد بر اساس مشاهدات لحظه اي ربات انجام شود به نحوي که بدون برخورد با موانع و ديوارها با پيمودن کوتاه ترين مسير به مقصد مورد نظر برسد. وي نشان داده است که ربات مورد نظر بايد بر روي دوگان وروني گراف مشاهداتش حرکت کند. وي همچنين چگونگي ستخراج اين دوگان وروني گراف را بر اساس مشاهدات ربات بيان کرده است. منابع: 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

الگوریتم‌های گراف[ویرایش]

الگوریتم‌های گراف زمینهٔ مهم علاقه در علوم رایانه به حساب می‌آیند. برخی از عملیاتِ مربوط به گراف‌ها عبارتند از: پیدا کردن مسیری بین دو گره، مانند جستجوی عمق اول و جستجوی سطح اول و پیدا کردن کوتاهترین مسیر از یک گره به دیگری، مانند الگوریتم دیکسترا. یک روش برای پیدا کردن کوتاهترین مسیر بین هر گره و تمام گره‌های دیگر هم وجود دارد به نام الگوریتم فلوید-وارشال.

منابع[ویرایش]