تبیان، دستیار زندگی

مقدمه ای از نظریه گراف

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

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

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

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

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

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

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

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

اندازه گراف

اندازه گراف تعداد یال های یک گراف است و به صورت |(E(G| بیان می‌شود.

درجه راس ها

در نظریه گراف ها، درجه یك راس به تعداد یال هاى متصل به آن راس گفته میشود. به عبارت دیگر. درجه یك راس تعداد همسایگى (مجاورت) هاى مستقیم یك راس را بیان میكند. از آنجا كه هر یال در گراف دو راس را به هم وصل میكند، مجموع درجه راس هاى یك گراف با دو برابر تعداد یال هاى ان گراف برابر است.

انواع گراف

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

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

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

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

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

گراف اویلری و همیلتونی:

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

مثال‌هایی از گراف کامل

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

گراف دو بخشی:

فرض کنید در یک شرکت صنعتی تعدادی شغل بدون متصدی می باشند و تعدادی متقاضی برای این مشاغل اعلام آمادگی نموده اند. حال این سوال مطرح می شود که آیا می توان به هر متقاضی شغلی متناسب او اختصاص داد؟
برای حل چنین مسئله ای که به مسئله ی تخصیص موسوم است، با استفاده از گراف می توان وضعیت های خاص را پیاده سازی نمود. بدین ترتیب که گروهی که متقاضی مشاغل هستند در مجموعه ای به نام X و مجموعه مشاغل بدون متصدی را در مجموعه ای به نام Y قرار می دهیم. گراف رسم شده چنین است که به بعضی از اعضای مجموعه X یک یا چند عضو از مجموعه Y توسط یال ها وصل می نماید.
به عبارت دیگر گراف بوجود امدی دارای یالهای xy است که مر متقاضی x را از مجموعه X به شغلهای مناسب y از مجموعه Y متصل می نماید. به عبارت دقیقتر هیچ دو راس متعلق به مجموعه X(متفاضیان) یا هیچ دو راس متعلق به مجموعه Y(مشاغل) توسط هیچ یالی به هم متصل نمی باشند. چنین گرافی را گراف دوبخشی یا دوپارچه می گویند.

در نظریه گراف، یک درخت گرافی است که هر دو راس آن بوسیله دقیقاً یک یال به هم متصل شده اند، یک جنگل گرافی است که دو راس آن با بیشتر از یک راس به هم متصل اند. یک جنگل در واقع از اتصال، مجموعه ای از درخت ها به وجود می آید.

تعریف ها:

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

اگر یک جنگل با n راس باشد آن گاه از شرایط زیر پیروی می کند:
T یک درخت است.
T مداری ندارد و n-1 یال دارد.
T همبند است و n-1 یال دارد.
هر دو راس T با مسیر منحصر به فرد به هم متصل می شوند.
T مداری ندارد و با افزودن یگ یال جدید دقیقاً یک مدار بوجود می آید.

ماتریس مجاورت گراف

تعریف

ماتریس مجاورت گراف، ماتریس است که خصوصیات و ویژگی های یک گراف را به طور خلاصه نمایش می دهد.
ماتریس مجاورت گراف، ماتریسی است که ویژگی های زیر را دارد:
1) ماتریس مربعی است که تعداد سطر و ستون آن برابر با اندازه (تعداد راس) گراف می باشد.
2) این ماتریس فقط از اعداد یک و صفر تشکیل شده است.
3)رایه های واقع بر قطر اصلی آن فقط و فقط از صفر تشکیل شده باشد.
4)مهمتر از همه این است که این ماتریس باید متقارن باشد.
به کمک این ماتریس می توانیم به آسانی، یک گراف را رسم کنیم. هر سطر نشان می دهد که آن راس مربوط به آن سطر به چه روسی متصل است به ازای هر یالی که آن راس به راس دیگری متصل می شود، عدد یک را می گذاریم و اگر دو راس به هم متصل نباشند، عدد صفر را می گذاریم. پس تعدا یک های یک سطر درجه آن سطر می باشد.

قضایای مربوط به ماتریس مجاورت گراف:

1)اگر M ماتریس مجاورت یک گراف باشد، آنگاه درایه های واقع بر سطر iام ستون iام ماتریس M به توان دو برابر با درجه راس iام است.