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

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

ارسال:
  

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


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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
Tongue بخش گراف: محاسبه ماکزیمم طول دور یک گراف ashena1 ۱ ۸۸۴ ۰۴ شهریور ۱۳۹۳ ۰۴:۰۷ ب.ظ
آخرین ارسال: fatemeh69
  سوال : گسسته - گراف - قضیه اویلر Morris ۲ ۱,۱۹۰ ۱۳ مرداد ۱۳۹۳ ۰۸:۴۸ ب.ظ
آخرین ارسال: Morris
  سوال تعداد مسیرها در یک گراف دوبخشی amir2930 ۱ ۷۴۹ ۱۳ مرداد ۱۳۹۳ ۰۶:۳۳ ب.ظ
آخرین ارسال: Morris
  نامساوی در گراف با دوری به طول ۵ amir2930 ۳ ۸۲۰ ۲۷ خرداد ۱۳۹۳ ۰۷:۲۰ ق.ظ
آخرین ارسال: amir2930
  سوال تعداد یالهای گراف amir2930 ۴ ۸۹۸ ۲۶ خرداد ۱۳۹۳ ۱۲:۳۹ ب.ظ
آخرین ارسال: amir2930
  سوال زوج مرتب در گراف همبند amir2930 ۴ ۷۱۹ ۲۶ خرداد ۱۳۹۳ ۰۹:۰۰ ق.ظ
آخرین ارسال: amir2930
  سوال افراز گراف به مثلث amir2930 ۱ ۵۸۷ ۲۵ خرداد ۱۳۹۳ ۰۲:۴۰ ب.ظ
آخرین ارسال: Jooybari
  سوال از تطابق در گراف دوبخشی amir2930 ۳ ۹۱۵ ۲۴ خرداد ۱۳۹۳ ۱۱:۳۵ ق.ظ
آخرین ارسال: Jooybari
  تست گسسته موضوع گراف hana.rahmati ۱ ۷۰۵ ۲۰ اسفند ۱۳۹۲ ۰۲:۱۲ ق.ظ
آخرین ارسال: Jooybari
  تست گسسته موضوع گراف hana.rahmati ۱ ۵۶۴ ۲۰ اسفند ۱۳۹۲ ۰۱:۴۴ ق.ظ
آخرین ارسال: Jooybari

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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