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

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

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

کدام دنباله زیر می تواند دنباله درجه راسهای یک گراف باشد؟

                             5,3,3,2,0    4,3,2,2,0    3,3,2,2,0    5,4,3,2,0


این گراف 5 راس دارد یعنی مرتبه گراف 5 است.

بنابراین درجه هیچ راسی نباید از 4  بیشتر باشد.

در نتیجه دو دنباله اول و آخر اشتباه هستند.

در دنباله دوم  درجه یکی از رئوس 4 است یعنی به تمام راسهای دیگر یال دارد .

بنابراین این دنباله نمی تواند راسی با درجه صفر داشته باشد.

دنباله سوم  صحیح است.

نکته : مجموع درجه های راسهای هر دنباله عددی زوج است .(زیرا هر یال دو راس دارد)

توجه کنید که مطالب بالا در مورد گراف ساده می باشد.