سوال ۶۴ کنکور ارشد علوم کامپیوتر ۱۴۰۵
اهمیت
۰/۵
فرض کنید یک گراف بدون جهت وزندار و یالی با حداکثر وزن در باشد. فرض کنید یک درخت پوشای با حداقل وزن در وجود دارد که شامل یال است. کدامیک از عبارات زیر همواره درست است؟
پاسخ صحیح: گزینهٔ D — یک مجموعه برش در وجود دارد که تمام یالهای آن حداکثر وزن را دارند.
پاسخ تشریحی
Let be the maximum edge weight in , so and for every edge . We are told some minimum spanning tree contains .
ادامهٔ پاسخ تشریحی ویژهٔ مشترکان است.
مشاهدهٔ پاسخ کامل#minimum-spanning-tree#cut-property#maximum-weight-edge#cycle-property#graph-theory