در یک گراف با وزن های صحیح بزرگ تر از ۱، فرض کنید که وزن هر یال را یک واحد زیاد کنیم. در این صورت چند تا گزاره های زیر درست اند؟
(کارشناسی ارشد هوش-۹۰)
الف) برش کمینه (s,t) در هر دو گراف یکی است.
ب) درخت پوشای مینیمم هر دو گراف یکی است.
ج) کوتاه ترین مسیر بین دو راس مشخص در دو گراف شامل یالهای یکسان هستند.
جواب: ؟
دوستان لطفا با توضیح بفرمایند.
سلام. درخت پوشای مینیمم که تغییر نمیکنه. گزینه ب درسته. کوتاهترین مسیر لزوماً ثابت نیست. چون ممکنه یه مسیر که به عنوان کوتاه تر انتخاب شده، تعداد یال زیادی داشته باشه و با اضافه شدن وزن ها این مجموع بیشتر بشه. گزینه ج غلطه. منظور از برش کمینه نمیدونم چیه!
لزوما گزینه ی ج درست نیست
در درست بودن گزینه ب شکی نیست. (با این توضیح که وزن های گراف ها متمایز باشد)
گزینه ج هم لزوما برقرار نیست پس غلط است.
در مورد گزینه ۲ لطفا دوستان نظرشون رو بدهند.