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

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

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

گرافی دارای 8 راس و 23 یال است. بیشتر مقدار تفاوت بزرگترین درجه راس از کمترین درجه راس چیست؟


گراف کامل 8 راسی دارای c(8*7)/2 = 28 یال است و ماکزیمم درجه راس آن 7 است.

برای داشتن مینمم درجه در یک راس از یکی از رئوس آن 5 یال بر می داریم.

در این حالت گراف 23 یالی شده و درجه آن راس نیز 2 خواهد شد.

بنابراین بیشترین مقدار این تفاوت 5 خواهد بود.