گراف چرخ

[رزیتا]

گراف چرخ

این مطلب از بخش آموزش وب‌سایت المپیاد کامپیوتر رشد،انتخاب شده که با فرمت pdf نیز در وب‌سایت المپیاد رشدموجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس فهرست مطالب کامپیوتر مراجعه کنید.

گراف چرخ

هر گراف

که دارای

راس باشد که

و یکی از رئوس از درجه ی

و بقیه از درجه ی سه باشند، را یک گراف چرخ می نامیم- مانند مثال های زیر:

گراف چرخ

راسی را با

نمایش می دهیم.


پیوند های خارجی

http://Olympiad.roshd.ir/computer/content/pdf/0081.pdf

[رزیتا]

نظریه گراف

• تعریف
• انواع گراف‌ها
• گراف‌ها و ساختار داده‌ها
• مسایل گراف
• الگوریتم‌های مهم
• همچنین ببینید
• پیوندهای خارجی

در ریاضی و علوم کامپیوتر، نظریه گرافعلمی است که به مطالعه گراف‌ها می‌پردازد.گراف مجموعه‌ای از راس‌هاست که بوسیله یال‌ها به هم وصل شده‌اند.به عبارت ساده‌تر به مجموعه‌ای از نقاط که بوسیله خطوط به هم وصل شده‌‌اند، گراف گویند. مفهوم گراف در سال 1736 توسط اویلر و با طرح راه‌حلی برای مساله پل konigsberg ارائه شد و به تدریج توسعه یافت.گراف‌ها امروزه کاربرد زیادی در علوم دارند. از گراف‌ها در شبکه‌ها،طراحی مدارهای الکتریکی, اصلاح هندسی خیابان‌ها برای حل مشکل ترافیک،و.... استفاده میشود.







تعریف

فرض کنید V یک مجموعه ناتهی و E زیرمجموعه‌ای از

باشد در این صورت زوج

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

به سمت راس

را به صورت

نشان می‌دهند.در غیر این صورت گراف را بدون جهت می‌نامند و یال بین راس های

و

با نماد

نشان می‌دهند.

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

گراف‌ها دارای انواع متعددی هستند که به برخی از آنها اشاره می‌کنیم:

• گراف همبند
• گراف ناهمبند
• گراف کامل
• گراف اویلری
• گراف همیلتونی
• گراف درختی
• گراف مسطح
• گراف دو بخشی
• گراف چندبخشی
• گراف k-مکعب
• گراف چرخ
• گراف ستاره‌ای
• گراف بازه‌ای
• گراف اشتراکی
• گراف منظم
• گراف جهت‌دار

گراف‌ها و ساختار داده‌ها

هر گراف را می‌توان با یک ماتریس نمایش داد ، که به آن ماتریس مجاورت گراف گویند. در این روش از آرایه هااستفاده می‌کنیم.این ماتریس به تعداد راس‌های گراف دارای سطر و ستون است.وعدد 1 نشان دهنده وجود یک یال بین دو راس و عدد 0 نشان دهنده عدم وجود ارتباط بین دو راس است.یعنی ماتریس ما شامل دو عدد صفر و یک است. با استفاده از این ماتریس می‌توان رئوسی را که با یک راس در ارتباط‌اند و نیز رئوسی را که با هیچ راس دیگری ارتباط ندارند رامشخص کرد.
مسایل گراف

• تئوری رنگ آمیزی
• قضیه چهار رنگ
• مسائل حل نشده در رنگ آمیزی
• مسائل موجود در زمینه مسیر
  • هفت پل konisberg
• Minimum spanning tree
  • درخت steiner
  • مساله کوتاهترین مسیر
  • مساله پستچی چینی
  • مساله فروشنده دوره گرد

الگوریتم‌های مهم

• الگوریتم kruskal
• الگوریتم prim
• الگوریتم کوتاهترین مسیر

[رزیتا]

گراف کامل

• مثال‌هایی از گراف کامل
• همچنین ببینید
• پیوند خارجی

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

• یک گراف کامل از مرتبه n،دارای n راس و
  
  یال است و آن را با
  
  نشان می‌دهند.
• یک گراف کامل یک گراف منتظم از درجه n-1 است.

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

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

[رزیتا]

گراف دو بخشی:

مفهوم شهودی:

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

تعریف گراف دوبخشی:
گراف دوبخشی گرافی است که بتوان مجموعه رئوس آن را به دو مجموعه X و Y چنان افراز نمود که هر یال آن دارای یک انتها در X و یک انتها در Y باشد، به گونه ای که هیچ دوراسی در X یا در Y با هم مجاور نباشند. چنین افرازی را دوبخشی کردن گراف می نامند.

• یادآوری: منظور از افراز یک مجموعه چون A به چند مجموعه، تقسیم مجموعه A به چند مجموعه ناتهی دیگر است که باهم اشتراکی نداشته باشند و اجتماع همه آنها برابر مجموعه A باشد. و در اینجا اگر V به عنوان مجموعه رئوس باشد افراز V به دو مجموعه X و Y (ناتهی) به این صورت است که:
  

به عنوان مثال گراف زیر یک گراف دو بخشی است:

چرا که در این گراف مجموعه رئوس را می توان به دو مجموعه

و

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

• قضیه: اگر گراف k-منتظم، دارای دوبخش X و Y باشد، آنگاه تعداد عناصر X و Y باهم برابر است.

برهان:
فرض می کنیم X دارای m راس و Y دارای n راس از راسهای گراف دو بخشی k-منتظم می باشد. یشان می دهیم که: m=n.
از هر راس در مجموعه X به تعداد k، یال خارج می شود(چرا؟) پس تعداد کل یالها(q) برابر است با: q=km
چون جمعا" m+n راس داریم، لذا مطابق قضیه مجموع درجه های راس ها و تعریف گراف k-منتظم داریم:

پس:

و لذا حکم برقرار است.


گراف دو بخشی کامل:

گراف دو بخشی کامل یک گراف دو بخشی است که مجموع رئوس آن به دو مجموعه X و Y چنان افراز شده است و هر راس

در ان به هر راس

وصل شده است. گراف دو بخشی کامل را با نماد

نشان می دهند که در آن m تعداد عناصر مجموعه X و n تعداد عناصر مجموعه Y است.

• به عنوان مثال گراف زیر یک گراف دو بخشی کامل
  
  است.

• قضیه: در گراف دو بخشی کامل
  
  همواره داریم:
  
  که در آن q اندازه گراف مذکور است.

برهان:
می دانیم گراف

دارای m راس در یک مجموعه و n راس در مجموعه ای دیگر است.
تعداد کل راس ها P=m+n می باشد(مرتبه گراف). اما برای یافتن تعداد یالهای گراف دو بخشی کامل

ابتدا تعداد کل یالهای یک گراف کامل از مرتبه P=m+n را محاسبه کرده سپس تعداد کل یالهایی که راس های دو مجموعه را در خود دو مجموعه به هم وصل می کند از آن کم می کنیم. داریم:

• قضیه: اگر G یک گراف ساده و دو بخشی از مرتبه p و اندازه q باشد آنگاه:
  

برهان:
چون گراف دو بخشی است مطابق قضیه قبل حداکثر یال آن برابر است با:

که m تعداد یال بخش X و n تعداد یال بخش Y است.(بیشترین تعداد یال مربوط به زمانی است که گراف، دو بخشی کامل باشد).
از طرفی می دانیم که:

پس:

, داریم:

چون u آهنگ تغییرات تعداد یال را نشان می دهد و

پس از

نتیجه می شود که:

ضمنا" می دانیم که:

پس بیشترین مقدار u در نقطه

اتفاق می افتد، یعنی:

بنابراین تعداد کل یالها نمی تواند از

بیشتر باشد و لذا

:

[رزیتا]

گراف بازه‌ای



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

گرافی است که رئوس آن بازه های باز

بوده و در صورتی دو راس مجاورند(میانشان یال وجود دارد) که بازه های متناظر آن دو راس اشتراک ناتهی داشته باشند.

• تذکر: از حساب دیفرانسیل و انتگرال به یاد داریم که بازه ی باز
  
  مجموعه همه اعداد حقیقی بین دو عدد a و b(که شامل خود a و b نمی شود) است.

مـثال: به عنوان مثال می خواهیم گراف بازه ای متناظر با بازه های زیر را رسـم کنیم:

پاسخ: دو بازه

اشتراک ناتهی دارند، لذا راس های متناظر این دو بازه را با یک یال به هم وصل می کنیم. ولی دو بازه

اشتراکشان تهی است، پس راس هایی متناظر این دو بازه به هم وصل نمی شوند. به این ترتیب به همین استدلال نمودار گراف بازه ای شش بازه فوق به صورت زیر در می آید:

نحوه تشخیص گراف بازه ای:
سوالی که پیش می آید این است که چگونه می توان تشخیص داد که یک گراف بازه ای است یا نه؟
به عنوان مثال می خواهیم تحقیق کنیم که آیا این گراف بازه ای است یا نه:

سعی می کنیم بازه هایی را بیابیم که گراف متناظر آنها (گراف بازه ای آنها) به این صورت باشد.
5 بازه زیر را در نظر می گیریم:

(دقت شود که دو بازه a و b نباید اشتراک داشته باشند)
مشاهده می شود گراف متناظر با این بازه ها به صورت گراف داده شده است پس این گراف بازه ای است.

حال به این نمونه توجه کنید. می خواهیم بازه ای بودن این گراف را بررسی کنیم:

قبل از بررسی کردن به توضیحات زیر توجه کنید:

• در حالت کلی می توان گفت هر گراف دلخواه دارای یک دور از مرتبه 4 گراف بازه ای نمی باشد.

برهان
فرض می کنیم دور مرتبه 4 مقابل خود یک گراف یا قسمتی از یک گراف باشد:

نشان می دهیم این گراف و یا گرافی شامل این دور بازه ای نمی باشد. به برهان خلف اگر این گراف یا گراف شامل ایت دور بازه ای باشد:
روی محور اعداد حقیقی برای هر یک از راس ها بازه ای به صورت زیر در نظر می گیریم:
چون a با b مجاور است باید روی محور اعداد بازه های متناظر با این دو راس دارای اشتراک باشند مطابق شکل:

از طرفی c نیز با b مجاور است و با a مجاور نمی باشد پس بازه متناظر با c با بازه b اشتراک دارد ولی با بازه متناظر a اشتراک ندارد. مطابق شکل:

حال چون d هم با a و هم با c مجاور است پس بازه متناظر با راس d باید به گونه ای اشد که هم به a و هم به c اشتراک داشته باشد و این تناقض است چرا که در این صورت d با b هم اشتراک پیدا می کند در حالی که از b به d یالی رسم نشده است.

پس فرض خلف باطل و حکم برقرار است.


پس در این گراف چون abcd یک دور با طول 4 است بنابر دلایل ذکر شده بازه ای نمی باشد.

روش دیگری که می توان بوسیله آن تعیین نمود که گراف بازه ای نمی باشد این است که اگر در گرافی حفره وجود داشت آن گراف بازه ای نمی باشد. مشاهده می شود این روش تعمیمی بر روش استدلال گفته شده در بالا است.
البته این شرط، یک شرط کافی برای غیر بازه ای بودن گراف است و اگر در گرافی حفره مشاهده نشد نمی توان نتیجه گرفت لزوما گراف بازه ای است.

به عنوان مثال گراف زیر دارای حفره نمی باشد ولی در عین حال بازه ای نیز نمی باشد:

• یادآوری(تعریف حفره): در گراف ها هر چهار ضلعی یا n ضلعی (n>3) که بدون قطر باشد را یک حفره می گوییم.

به عنوان مثال در گراف قبلی به صورت:

abcd یک حفره محسوب می شود و لذا گراف همان طور که گفته شد بازه ای نمی باشد.