رتبه برتر کنکور..

کتاب آنلاین کنکور و کنکور ارشد

 
مرتبه و اندازه گراف
نویسنده : مهندس ضیابری - ساعت ٩:٠٩ ‎ب.ظ روز ۱۸ اسفند ۱۳۸٩
 

مرتبه گرافی 8 و اندازه آن 27 است. درجه چند راس آن ماکزیمم است؟


گراف دارای p= 8 راس و q=27 یال است.

اگر گراف کامل بود تعداد یال راس اول 7 تا و تعداد یال راس دوم 6 تا و ... و درنتیجه تعداد کل یالها 28 تا بود.

نکته : تعداد ماکزیمم یالها در یک گراف کامل برابر p(p -1)/2 است.

در این گراف کامل فرضی درجه تمامی رئوس 7 است.

حال اگر از این گراف کامل یک یال کم شود تعداد یالها 27 شده و 6 راس هنوز دارای درجه 7 هستند.