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

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

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

بین هر دو راس از گراف G دقیقا" یک مسیر وجود دارد. اگر این گراف شامل 7 راس درجه یک و 5 راس درجه دو و k راس درجه سه باشد. k را بیابید.


نکته اول : فقط در گراف از نوع درخت بین هر دو راس دقیقا" یک مسیر وجود دارد.

بنابراین گراف مورد نظر درخت است.

نکته دوم : در هر درخت با مرتبه p و اندازه q داریم             q = p -1

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

مرتبه گراف مورد نظر (تعداد رئوس) برابر است با

                                                             p = 7+5+k = 12+k

و اندازه گراف مورد نظر (تعداد یالها) طبق نکته سوم برابر است با

                                             q = (7+10+3k)/2 = (17+3k)/2

از طرفی طبق نکته دوم داریم

                                                                  q = p -1= 11+k

و با برابر قرار دادن این دو مقدار q داریم

                                                3k+17 = 22+2k  -->  k = 5