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

مجموعه درجات رئوس مکمل گراف

ارسال:
  

iCanDoIt پرسیده:

مجموعه درجات رئوس مکمل گراف

سلام و درود.

این سئوال اول فصل هشتم کتاب ساختمان پورانه:
اگر G یک گراف ساده از درجه n باشد، در صورتی که گراف G دارای ۵۶ یال باشد و مجموعه درجات رئوس مکمل گراف G برابر ۱۶۰ باشد مقدار n کدام است؟

خود آقا یوسفی جواب داده ولی خیلی نامفهومه میشه یه نفر بازش کنه!
جواب ۱۶ میشهBig Grin
با تشکر
نقل قول این ارسال در یک پاسخ

۲
ارسال:
  

Iranian Wizard پاسخ داده:

RE: مجموعه درجات رئوس مکمل گراف

سلام.
اول باید تعداد رئوس رو پیدا کنیم.
جمع درجات رئوس یک گراف،میشه دو برابر تعداد یالها.
پس در گراف مکمل G،چون جمع درجات شده ۱۶۰،پس تعداد یالها،۸۰ هستش.
از طرفیم تعداد یالهای گراف اصلی،۵۶ یال هستش.
همونطور که میدونید تعداد یالهای گراف مکمل برابر (تعداد حداکثر یالها) منهای (تعداد یالهای گراف اصلی) هستش.
پس اگر تعداد رئوس رو برابر m بگیریم.داریم:
[tex]80\: =\: \binom{m}{2}\: -\: 56[/tex]
که محاسبش بصورت زیر هستش:
[tex]\binom{m}{2}\: =\: 136\: \: \: \rightarrow\: \: \frac{m(m-1)}{2}\: =\: 136\: \: \: \: \rightarrow\: \: \: m(m-1)=272=17\: \times\: 16\: \: \: \: \rightarrow\: \: \: m=17[/tex]
حالا که تعداد رئوس شد ۱۷ ،پس حداکثر درجه ی گره ها میتونه ۱۶ باشه(۱۶ یال به بقیه رئوس ها وصل باشه)
پس حداکثر درجه یا همون n برابر ۱۶ هستش.
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  مجموعه تمارین و سوالات امتحانی درس طراحی الگوریتم دانشگاه MIT (سال ۲۰۰۰-۲۰۱۲) Farid_Feyzi ۵ ۷,۲۲۱ ۳۰ آبان ۱۳۹۹ ۱۰:۱۵ ب.ظ
آخرین ارسال: s-taheri
  رنگ کردن رئوس گراف( ارشد علوم کامپیوتر ۹۸ ) ss311 ۰ ۱,۸۸۶ ۰۳ اسفند ۱۳۹۸ ۱۲:۴۳ ب.ظ
آخرین ارسال: ss311
  تعداد مسیرها در گراف ss311 ۰ ۱,۷۹۱ ۰۸ بهمن ۱۳۹۸ ۱۲:۴۷ ب.ظ
آخرین ارسال: ss311
  طراحی گرافیکی simaakbari ۰ ۲,۲۴۰ ۱۶ خرداد ۱۳۹۸ ۰۴:۵۴ ب.ظ
آخرین ارسال: simaakbari
  مجموعه آموزش تصویری شبکه های پتری رنگی net work ۰ ۲,۰۶۱ ۲۲ فروردین ۱۳۹۸ ۰۳:۲۷ ب.ظ
آخرین ارسال: net work
  مجموعه آموزش تصویری ابزار شبیه سازی و بررسی پروتکل امنیتی اسکایتر net work ۰ ۲,۳۱۷ ۲۲ فروردین ۱۳۹۸ ۰۳:۲۵ ب.ظ
آخرین ارسال: net work
  مجموعه آموزشی رایگان برنامه نویسی متلب net work ۰ ۱,۹۳۷ ۲۲ فروردین ۱۳۹۸ ۰۳:۲۱ ب.ظ
آخرین ارسال: net work
  کوتاه ترین مسیر در گراف Sanazzz ۳ ۳,۶۲۶ ۰۷ فروردین ۱۳۹۸ ۰۲:۵۷ ق.ظ
آخرین ارسال: Sanazzz
  نگاشت شرکت پذیر مجموعه ای لطفا کمک Sanazzz ۳ ۳,۶۸۹ ۰۲ اسفند ۱۳۹۷ ۰۳:۲۷ ب.ظ
آخرین ارسال: Sanazzz
  سوالات ارشد آزاد مجموعه کامپیوتر ۹۲ yahyazahedi ۱ ۵,۴۹۰ ۲۷ بهمن ۱۳۹۷ ۱۲:۴۰ ب.ظ
آخرین ارسال: serv24

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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