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

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

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

اگر A ماتریس مجاورت گراف G از مرتبه 4 باشد. حاصلضرب درایه قطری ماتریس A2 کدام عدد زیر نمی تواند باشد؟

                                                            3  ,  12   ,   18   ,   36


نکته : درایه های قطر اصلی A2 همان درجه رئوس گراف هستند.

در مورد اول فقط داریم  3*1*1*1=3 که دنباله 3,1,1,1 می تواند رئوس یک گراف باشد.

در مورد دوم داریم  4*3*1*1=12 که 4 نمی تواند درجه یک راس باشد.

و نیز داریم 3*2*2*1=12 ولی دنباله 3,2,2,1 می تواند رئوس یک گراف باشد.

در مورد سوم داریم 6*3*1*1=18 که 6 نمی تواند درجه یک راس باشد.

و نیز داریم 3*3*2*1=18 که در اینجا هم مجموع درجه رئوس نمی تواند فرد باشد.

در مورد چهارم داریم 3*3*2*2=36 که دنباله 3,3,2,2 می تواند رئوس یک گراف باشد.