زمان کنونی: ۱۰ آذر ۱۳۹۹, ۰۶:۱۵ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

تست در مورد راس گراف

ارسال:
  

vijay پرسیده:

تست در مورد راس گراف

[تصویر:  63562_1_1379095921.png]
جواب ۱ است.چرا؟؟؟؟

۰
ارسال:
  

parsaNA پاسخ داده:

RE: تست در مورد راس گراف

این همون گراف پترسونه . این گراف دور به طول فرد داره و دوبخشی نیست . گفته زیر مجموعه های دو عضوی از مجموعه ۵ عضوی ای که داده پس تعداد رئوس گراف می شه [tex]\binom{5}{2}=10[/tex] . هر راس این گراف با [tex]\binom{3}{2}=3[/tex] راس دیگه همسایه و مجاور محسوب می شه . یعنی هر راس گراف درجه اش ۳ می شه . چون این گراف ۳-منتظم هست پس [tex]n\times d=2e[/tex] که n تعداد راس‌ها و d هم درجه همه رئوس است . پس این گراف [tex]10\times 3=30[/tex] پس ۱۵ یال دارد .

یه قضیه داریم که هر گرافی که عدد کروماتیکش ۲ باشه دوبخشیه و بالعکس . این گراف عدد کروماتیکش دو نیست پس دو بخشی هم نیست . شکل خود گراف رو هم برای این سوال کشیدم‌:

[تصویر:  attachment.php?aid=2424]


فایل‌(های) پیوست شده

۰
ارسال:
  

vijay پاسخ داده:

تست در مورد راس گراف

ترکیب ۲ از ۳ را از کجا می فهمیم
به غیر از پترسون بودن از روی مجموعه میشه فهمید؟؟؟؟

ارسال:
  

parsaNA پاسخ داده:

RE: تست در مورد راس گراف

(۳۰ دى ۱۳۹۰ ۰۱:۰۴ ق.ظ)vijay نوشته شده توسط:  ترکیب ۲ از ۳ را از کجا می فهمیم
به غیر از پترسون بودن از روی مجموعه میشه فهمید؟؟؟؟

صورت سوال گفته‌، رئوس در صورتی مجاورند که اشتراکات دوبه دوی اعضای آنها تهی باشه . پس مثلا زیرمجموعه {۱,۲} با زیر مجموعه هایی که شامل ۱ و ۲ هستند نمی تونه مجاور بشه . پس می مونه ۳ تا عدد ۳ و ۴ و ۵ . حالا از این ۳ تا عدد می خواهیم زیر مجموعه های دوتایی پیدا کنیم که می شه ترکیب ۲ از ۳ .

روشهای تشخیص گراف دوبخشی:

  1. رنگ آمیزی‌: باید بشه با ۲ تا رنگ رنگ آمیزی کرد.
  2. افراز به دو مجموعه جدا از هم
  3. حداکثر تعداد یالها در گراف دوبخشی n راسی‌، [tex]\left \lfloor \frac{n^{2}}{4} \right \rfloor[/tex] میشه
  4. گراف دوبخشی نباید دارای دور به طول فرد باشه


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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  رنگ کردن رئوس گراف( ارشد علوم کامپیوتر ۹۸ ) ss311 ۰ ۴۴۱ ۰۳ اسفند ۱۳۹۸ ۱۲:۴۳ ب.ظ
آخرین ارسال: ss311
  تعداد مسیرها در گراف ss311 ۰ ۴۱۱ ۰۸ بهمن ۱۳۹۸ ۱۲:۴۷ ب.ظ
آخرین ارسال: ss311
  فاصله دو راس(دکتری ۹۷) ss311 ۱ ۵۹۹ ۱۷ خرداد ۱۳۹۸ ۰۶:۱۱ ب.ظ
آخرین ارسال: Jooybari
  کوتاه ترین مسیر در گراف Sanazzz ۳ ۱,۲۵۲ ۰۷ فروردین ۱۳۹۸ ۰۲:۵۷ ق.ظ
آخرین ارسال: Sanazzz
  تست در مورد درخت Sanazzz ۲ ۸۳۴ ۰۴ بهمن ۱۳۹۷ ۰۶:۴۰ ب.ظ
آخرین ارسال: Sanazzz
  درخواست کتاب شبکه کراس راس ویرایش هفتم fallah_o68 ۱ ۱,۶۷۲ ۰۷ مهر ۱۳۹۷ ۱۲:۱۲ ق.ظ
آخرین ارسال: mraict@gmail.com
  کتاب خوب در باره نظریه گراف ماهی ۲۵۸ ۰ ۵۷۶ ۲۸ شهریور ۱۳۹۷ ۱۲:۲۸ ب.ظ
آخرین ارسال: ماهی ۲۵۸
  یافتن مسیر در گراف کامل دو بخشی Sepideh96 ۳ ۱,۰۱۱ ۲۶ بهمن ۱۳۹۶ ۱۲:۴۲ ب.ظ
آخرین ارسال: αɾια
  رنگ آمیزی راسهای گراف ss311 ۲ ۷۲۳ ۰۳ بهمن ۱۳۹۶ ۰۱:۲۳ ق.ظ
آخرین ارسال: ss311
  سوال در مورد ساختن یک گراف دانش محدود zahra89 ۰ ۵۷۱ ۰۲ بهمن ۱۳۹۶ ۰۳:۴۱ ب.ظ
آخرین ارسال: zahra89

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close