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

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

ارسال:
  

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. گراف دوبخشی نباید دارای دور به طول فرد باشه


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



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

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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