X
تبلیغات
IT فکر کنید - جزوه بخش گراف در ساختمان داده
رییس اداره تعاون کار و رفاه اجتماعی شهرستان کنگان و مدرس دانشگاه
 جزوه بخش گراف در ساختمان داده

نظریه گراف شاخه‌ای از ریاضیات است که دربارهٔ گراف ها بحث می‌کند. به صورت شهودی، گراف نموداری است، شامل تعدادی رأس، که با یال‌هایی‌ به هم وصل شده‌اند

تعریف دقیق‌تر گراف به این صورت است، که گراف مجموعه‌ای از رأس‌ها است، که توسط خانواده‌ای از زوج‌های مرتب که همان یال‌ها هستند به هم مربوط (وصل) شده‌اند.

یال‌ها بر دو نوع ساده و جهت دار هستند، که هر کدام در جای خود کاربردهای بسیاری دارد. مثلاً اگر صرفاً اتصال دو نقطه -مانند اتصال تهران و زنجان با کمک آزادراه- مد نظر شما باشد، کافیست آن دو شهر را با دو نقطه نمایش داده، و اتوبان مزبور را با یالی ساده نمایش دهید. اما اگر بین دو شهر جاده‌ای یکطرفه وجود داشته باشد آنگاه لازمست تا شما با قرار دادن یالی جهت دار مسیر حرکت را در آن جاده مشخص کنید. همچنين براى اينكه فاصله بين دو شهر را در گراف نشان دهيد، ميتوانيد از گراف وزن دار استفاده كنيد و مسافت بين شهر ها را با يك عدد بر روى هر يال نشان دهيد.

آغاز نظریهٔ گراف به سدهٔ هجدهم بر می‌گردد. اولر ریاضیدان بزرگ مفهوم گراف را برای حل مسئله پل‌های کونیگسبرگ ابداع کرد اما رشد و پویایی این نظریه عمدتاً مربوط به نیم سدهٔ اخیر و با رشد علم انفورماتیک بوده‌است.

مهم‌ترین کاربرد گراف مدل‌سازی پدیده‌های گوناگون و بررسی بر روی آنهاست. با گراف می‌توان به راحتی یک نقشه بسیار بزرگ یا شبکه‌ای عظیم را در درون یک ماتریس به نام ماتریس وقوع گراف ذخیره کرد و یا الگوریتمهای‌ مناسب مانند الگوریتم دایسترا یا الگوریتم کروسکال و ... را بر روی آن اعمال نمود.

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

نظریه گراف یکی از پرکاربردترین نظریه‌ها در شاخه‌های مختلف علوم مهندسی (مانند عمران)، باستان‌شناسی (کشف محدوده یک تمدن) و ... است.

روابط میان راس های یک گراف را می‌توان با کمک ماتریس بیان کرد .

براى نمايش تصويرى گراف ها معمولا از نقطه يا دايره براى كشيدن راس ها و از كمان يا خط راست براى كشيدن يال بين راس ها استفاده ميشود

انواع گراف :

گراف ساده: هر گراف G زوج مرتبی مانند (V,E) است که در آن V مجموعه‌ای متناهی و ناتهی است و E زیرمجموعه‌ای از تمام زیرمجموعه‌های دو عضوی V می‌باشد. اعضای V را رأسهای G و اعضای E را یالهای G مینامیم. به بیان ساده تر بین دو رأس یک گراف ساده حداکثر یک یال وجود دارد.

گراف چندگانه: هرگاه بین دو رأس متمایز از یک گراف بیش از یک یال وجود داشته باشد، آن را یک گراف چند گانه می‌گوییم.

گراف جهت دار: هر گراف G زوج مرتبی مانند (V,E) است که در آن V مجموعه‌ای متناهی و ناتهی است و E زیرمجموعه‌ای از مجموعهٔ تمام زوج مرتب‌های متشکل از اعضای V است.

گراف مسطح: گراف مسطح گرافی است که می‌توان آن را در یک صفحه محاط کرد به گونه‌ای که یال هایش یکدیگر را تنها در راس ها قطع کنند.

گراف وزن دار: در يك گراف وزن دار، به هر يال يك وزن (عدد) نسبت داده ميشود. معمولا اعداد حقيقى به عنوان وزن يال ها استفاده ميشوند. اما بسيارى از الگوريتم هاى پر كاربرد فقط براى گراف هايى كه داراى وزن صحيح يا مثبت هستند طراحى شده اند.

خصوصیات گراف‌های خاص

  • اگر درجهٔ همهٔ راس‌ها در گراف ساده با هم برابر و برابر بزرگترین درجهٔ ممکن (یعنی p-1 ) باشد، گراف مورد نظر منتظم کامل است. در این گونه گراف ها، رابطهٔ میان رأس‌ها و یال‌ها چنین است:

که در آن تعداد راسها، و تعداد یالها است.

  • اگر گراف همبند باشد (یعنی از هر نقطه بتوان به یک نقطه دلخواه دیگر رسید) ولی دور نداشته باشد (یعنی هیچ نقطه‌ای از دوراه به نقطهٔ بعدی نرسد) می‌گویند گراف درختی است. در اينگونه گراف ها فرمول زير صدق ميكند (شرط لازم):

که در آن تعداد رأس‌ها، و تعداد یال‌ها است.[۱]

  • گراف اویلری و همیلتونی:گاهی اوقات ما می خواهیم در یک گراف حرکت کنیم.به اینصورت که از راسی به راسی دیگر برویم.در اینصورت ممکن است برای ما مهم باشد که از روی یال یا راس تکراری حرکت نکنیم(مشابه مسالهٔ فروشندهٔ دوره گرد).این مساله در صرفه جویی زمان و هزینه هم مهم است.(یعنی مبحث بهینه سازی).دراینجا دو موضوع گرافهای اویلری(دور زدن در گراف بدون یال تکراری)و همیلتونی(دور زدن بدون راس تکراری) مطرح می‌شود.براحتی می‌توان بررسی کرد که راسهای گراف اویلری باید درجهٔ زوج داشته باشند.اما اینکه شرایط کامل لازم و کافی برای همیلتونی بودن یک گراف چیست هنوز حل نشده مانده است

کاربردها گراف

از گراف ها براى حل مسايل زيادى در رياضيات و علوم كامپيوتر استفاده ميشود. ساختار هاى زيادى را ميتوان به كمك گراف ها به نمايش در آورد. براى مثال براى نمايش چگونگى رابطه وب سايت ها به يكديگر ميتوان از گراف جهت دار استفاده كرد. به اين صورت كه هر وب سايت را به يك راس در گراف تبديل ميكنيم و در صورتيكه در اين وب سايت لينكى به وب سايت ديگرى بود، يك يال جهت دار از اين راس به راسى كه وب سايت ديگر را نمايش ميدهد وصل ميكنيم

|+| نوشته شده توسط عبدالمجید دراهکی در شنبه 12 دی1388  |
 
 
بالا