سلام و درود.
این سئوال اول فصل هشتم کتاب ساختمان پورانه:
اگر G یک گراف ساده از درجه n باشد، در صورتی که گراف G دارای ۵۶ یال باشد و مجموعه درجات رئوس مکمل گراف G برابر ۱۶۰ باشد مقدار n کدام است؟
خود آقا یوسفی جواب داده ولی خیلی نامفهومه میشه یه نفر بازش کنه!
جواب ۱۶ میشه
با تشکر
سلام.
اول باید تعداد رئوس رو پیدا کنیم.
جمع درجات رئوس یک گراف،میشه دو برابر تعداد یالها.
پس در گراف مکمل 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 برابر ۱۶ هستش.