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

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

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

گرافی که دنباله درجه راسهایش 3,2,2,1,1,1,1,1 باشد چگونه گرافی است؟


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

بنابراین
                                                          q=(1/2).(3+2+2+5)=6

نکته دوم : اگر p مرتبه و q اندازه گراف و q<p -1 باشد گراف ناهمبند است.

نکته سوم : گرافی همبند است که بین هر دو راس متمایز آن حداقل یک مسیر وجود داشته باشد.

در نتیجه در این مسئله گراف مورد نظر ناهمبند است.