گراف چرخ

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

گراف چرخ

هر گراف http://daneshnameh.roshd.ir/mavara/i...235250ba33.pngکه دارای http://daneshnameh.roshd.ir/mavara/i...5b7c4320d5.png راس باشد کهhttp://daneshnameh.roshd.ir/mavara/i...681ea4972b.png و یکی از رئوس از درجه ی http://daneshnameh.roshd.ir/mavara/i...7c20ccee4d.png و بقیه از درجه ی سه باشند، را یک گراف چرخ می نامیم- مانند مثال های زیر:

http://daneshnameh.roshd.ir/mavara/i...9/mco0086a.jpg

گراف چرخhttp://daneshnameh.roshd.ir/mavara/i...5b7c4320d5.png راسی را با http://daneshnameh.roshd.ir/mavara/i...b86e3d9653.png نمایش می دهیم.


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

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

نظریه گراف
http://daneshnameh.roshd.ir/mavara/i...up/5/54/ka.jpg

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

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







تعریف

فرض کنید V یک مجموعه ناتهی و E زیرمجموعه‌ای از http://daneshnameh.roshd.ir/mavara/i...903a12fbff.png باشد در این صورت زوج http://daneshnameh.roshd.ir/mavara/i...522221c8a7.png را یک گراف می نامند.V را مجموعه راس ها و E را مجموعه یال ها می گویند. اگر ترتیب قرار گرفتن راس ها در مجموعه E مهم باشد،گراف را گراف جهت‌دار می گویند و یال از راس http://daneshnameh.roshd.ir/mavara/i...43d8e4a234.png به سمت راس http://daneshnameh.roshd.ir/mavara/i...3b834e829d.png را به صورت http://daneshnameh.roshd.ir/mavara/i...04638e9d66.png نشان می‌دهند.در غیر این صورت گراف را بدون جهت می‌نامند و یال بین راس هایhttp://daneshnameh.roshd.ir/mavara/i...43d8e4a234.png وhttp://daneshnameh.roshd.ir/mavara/i...3b834e829d.png با نماد http://daneshnameh.roshd.ir/mavara/i...965136636c.png نشان می‌دهند.
http://daneshnameh.roshd.ir/mavara/i...7d/6n-graf.jpg

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

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

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

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

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

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

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

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

گراف کامل

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

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

• یک گراف کامل از مرتبه n،دارای n راس و http://daneshnameh.roshd.ir/mavara/i...7112077ad5.png یال است و آن را با http://daneshnameh.roshd.ir/mavara/i...3927880b06.png نشان می‌دهند.
• یک گراف کامل یک گراف منتظم از درجه n-1 است.

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

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




http://daneshnameh.roshd.ir/mavara/i...e_graph_K1.png http://daneshnameh.roshd.ir/mavara/i...e_graph_K2.png http://daneshnameh.roshd.ir/mavara/i...e_graph_K3.png http://daneshnameh.roshd.ir/mavara/i...e_graph_K4.png http://daneshnameh.roshd.ir/mavara/i...e_graph_K5.png http://daneshnameh.roshd.ir/mavara/i...e_graph_K6.png http://daneshnameh.roshd.ir/mavara/i...e_graph_K7.png http://daneshnameh.roshd.ir/mavara/i...e_graph_K8.png

گراف دو بخشی:

مفهوم شهودی:

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

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

• یادآوری: منظور از افراز یک مجموعه چون A به چند مجموعه، تقسیم مجموعه A به چند مجموعه ناتهی دیگر است که باهم اشتراکی نداشته باشند و اجتماع همه آنها برابر مجموعه A باشد. و در اینجا اگر V به عنوان مجموعه رئوس باشد افراز V به دو مجموعه X و Y (ناتهی) به این صورت است که: http://daneshnameh.roshd.ir/mavara/i...fac65c6f52.png

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

http://daneshnameh.roshd.ir/mavara/i...part-Graph.jpg

چرا که در این گراف مجموعه رئوس را می توان به دو مجموعه http://daneshnameh.roshd.ir/mavara/i...d849da3250.png و
http://daneshnameh.roshd.ir/mavara/i...2cb6ff278c.png چنان افراز نمود که هیچ دو راسی در این دو مجموعه با هم مجاور نباشند و هر یال تنها یک انتها در مجموعه اول و یک انتها در مجموعه دوم داشته باشد.

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

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

http://daneshnameh.roshd.ir/mavara/i...866e61cba2.png

پس:

http://daneshnameh.roshd.ir/mavara/i...4088de6cd7.png

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


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

گراف دو بخشی کامل یک گراف دو بخشی است که مجموع رئوس آن به دو مجموعه X و Y چنان افراز شده است و هر راس http://daneshnameh.roshd.ir/mavara/i...14a3a07f87.png در ان به هر راس http://daneshnameh.roshd.ir/mavara/i...bc0600c864.png وصل شده است. گراف دو بخشی کامل را با نماد http://daneshnameh.roshd.ir/mavara/i...37cbf386ba.png نشان می دهند که در آن m تعداد عناصر مجموعه X و n تعداد عناصر مجموعه Y است.

• به عنوان مثال گراف زیر یک گراف دو بخشی کامل http://daneshnameh.roshd.ir/mavara/i...6efb3503d7.png است.

http://daneshnameh.roshd.ir/mavara/i...part-Graph.jpg

• قضیه: در گراف دو بخشی کامل http://daneshnameh.roshd.ir/mavara/i...d7aa242df3.png همواره داریم:http://daneshnameh.roshd.ir/mavara/i...f11b75f34b.png که در آن q اندازه گراف مذکور است.

برهان:
می دانیم گراف http://daneshnameh.roshd.ir/mavara/i...d7aa242df3.png دارای m راس در یک مجموعه و n راس در مجموعه ای دیگر است.
تعداد کل راس ها P=m+n می باشد(مرتبه گراف). اما برای یافتن تعداد یالهای گراف دو بخشی کامل http://daneshnameh.roshd.ir/mavara/i...d7aa242df3.png ابتدا تعداد کل یالهای یک گراف کامل از مرتبه P=m+n را محاسبه کرده سپس تعداد کل یالهایی که راس های دو مجموعه را در خود دو مجموعه به هم وصل می کند از آن کم می کنیم. داریم:

http://daneshnameh.roshd.ir/mavara/i...ffb4b91174.png

http://daneshnameh.roshd.ir/mavara/i...e86629d0d6.png

http://daneshnameh.roshd.ir/mavara/i...dab9a20c33.png

• قضیه: اگر G یک گراف ساده و دو بخشی از مرتبه p و اندازه q باشد آنگاه: http://daneshnameh.roshd.ir/mavara/i...f1645249a2.png

برهان:
چون گراف دو بخشی است مطابق قضیه قبل حداکثر یال آن برابر است با: http://daneshnameh.roshd.ir/mavara/i...acaec32d03.png
که m تعداد یال بخش X و n تعداد یال بخش Y است.(بیشترین تعداد یال مربوط به زمانی است که گراف، دو بخشی کامل باشد).
از طرفی می دانیم که: http://daneshnameh.roshd.ir/mavara/i...d9f0184d7b.png پس: http://daneshnameh.roshd.ir/mavara/i...64150d7d03.png , داریم:

http://daneshnameh.roshd.ir/mavara/i...2e8347f054.png

چون u آهنگ تغییرات تعداد یال را نشان می دهد و http://daneshnameh.roshd.ir/mavara/i...f3097cd84b.png پس از http://daneshnameh.roshd.ir/mavara/i...a76a282ee5.png نتیجه می شود که: http://daneshnameh.roshd.ir/mavara/i...8888f26619.png

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

http://daneshnameh.roshd.ir/mavara/i...7f60f1184e.png

پس بیشترین مقدار u در نقطه http://daneshnameh.roshd.ir/mavara/i...8888f26619.png اتفاق می افتد، یعنی:

http://daneshnameh.roshd.ir/mavara/i...0ca1e07270.png

بنابراین تعداد کل یالها نمی تواند از http://daneshnameh.roshd.ir/mavara/i...87d793dca5.png بیشتر باشد و لذا

:http://daneshnameh.roshd.ir/mavara/i...f1645249a2.png

گراف بازه‌ای



فرض می کنیم مجموعه ای از بازه های باز داریم. اگر این بازه ها را به عنوان رئوس و اتصال دو راس را، به شرط ناتهی بودن اشتراک بازه های متناظر، یال ها در نظر بگیریم، گرافی می توان رسم کرد که به آن گراف بازی ها میگوییم. به عبارت دریگر گراف بازه ای متناظر با بازی های باز http://daneshnameh.roshd.ir/mavara/i...e0eff4d0fa.png گرافی است که رئوس آن بازه های باز http://daneshnameh.roshd.ir/mavara/i...e0eff4d0fa.png بوده و در صورتی دو راس مجاورند(میانشان یال وجود دارد) که بازه های متناظر آن دو راس اشتراک ناتهی داشته باشند.

• تذکر: از حساب دیفرانسیل و انتگرال به یاد داریم که بازه ی باز http://daneshnameh.roshd.ir/mavara/i...a1b72cd498.png مجموعه همه اعداد حقیقی بین دو عدد a و b(که شامل خود a و b نمی شود) است.

مـثال: به عنوان مثال می خواهیم گراف بازه ای متناظر با بازه های زیر را رسـم کنیم:
http://daneshnameh.roshd.ir/mavara/i...b5e57a79f9.png
پاسخ: دو بازه http://daneshnameh.roshd.ir/mavara/i...bf1c156dc1.png اشتراک ناتهی دارند، لذا راس های متناظر این دو بازه را با یک یال به هم وصل می کنیم. ولی دو بازه http://daneshnameh.roshd.ir/mavara/i...2ac95978da.png اشتراکشان تهی است، پس راس هایی متناظر این دو بازه به هم وصل نمی شوند. به این ترتیب به همین استدلال نمودار گراف بازه ای شش بازه فوق به صورت زیر در می آید:

http://daneshnameh.roshd.ir/mavara/i...baze-Graph.JPG

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

http://daneshnameh.roshd.ir/mavara/i...3/example1.jpg

سعی می کنیم بازه هایی را بیابیم که گراف متناظر آنها (گراف بازه ای آنها) به این صورت باشد.
5 بازه زیر را در نظر می گیریم:
http://daneshnameh.roshd.ir/mavara/i...eebcdf9aae.png
(دقت شود که دو بازه a و b نباید اشتراک داشته باشند)
مشاهده می شود گراف متناظر با این بازه ها به صورت گراف داده شده است پس این گراف بازه ای است.

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

http://daneshnameh.roshd.ir/mavara/i...6/example2.jpg

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

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

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

http://daneshnameh.roshd.ir/mavara/i.../44/4-cric.jpg

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

http://daneshnameh.roshd.ir/mavara/i...7/example3.jpg

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

http://daneshnameh.roshd.ir/mavara/i...9/example4.jpg

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

http://daneshnameh.roshd.ir/mavara/i...a/example5.jpg

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


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

http://daneshnameh.roshd.ir/mavara/i...6/example2.jpg

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

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

http://daneshnameh.roshd.ir/mavara/i...4/example6.jpg

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

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

http://daneshnameh.roshd.ir/mavara/i...6/example2.jpg

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