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

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

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

گرافی دارای 13 راس و درجه هر راس 2 است. این گراف حداکثر چند دور دارد؟


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

در ساده ترین حالت گراف می تواند یک 13 ضلعی باشد که فقط یک دور دارد.

در حالت بعدی می تواند ترکیبی از یک مثلث و یک 10 ضلعی باشد که دو دور دارد.

در حالت بعدی می تواند دو مثلث و یک 7 ضلعی باشد که سه دور دارد.

ودر حالت آخر می تواند سه مثلث و یک 4 ضلعی باشد که جهار دور دارد.