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

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

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

درجه رئوس گراف همبند G به صورت a,b,5,4,3,2 است. کمترین مقدار a+b چیست؟


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

تعداد رئوس این گراف p= 6 است.

درجه یکی از رئوس 5 است. بنابراین از این راس به سایر رئوس یال وجود دارد. بنابراین تا اینجا درجه سایر رئوس حداقل 1 است.

درجه راس بعدی 4 است. بنابراین از چهار راس باقیمانده سه تا درجه 2 و یکی درجه 1 هستند.

درجه راس بعدی 3 است. در اینجا دو حالت داریم :

حالت اول - یال سوم این راس به راس درجه 1 قبلی می رود. بنابراین سه راس باقیمانده هر سه درجه 2 شده و a و b برابر 2 هستند.

حالت دوم - یال سوم این راس به یکی از رئوس درجه 2 قبلی می رود. بنابراین از سه راس باقیمانده یکی درجه 3 و یکی دیگر درجه 2 و آخری درجه 1 است. در نتیجه a و b برابر 3 و 1 می شوند.

در هر دو حالت مجموع a+b برابر 4 است.