تالار گفتمان مانشت

سلام دوستان
سال ۹۰ هوش مصنوعی سوالی مطرح شده که :
اگر به وزن هر یال گراف یک واحد اضافه بشه( با فرض اینکه یال ها همه اعداد صحیح هستند) در این صورت تعداد گزاره های درست چن تاست؟
الف - برش کمینه (s,t) در هر دو گراف یکی است
ب- درخت فراگیر کمینه هر دو گراف یکی است
ج- کوتاه ترین مسیر بین دو راس مشخص در دو گراف شامل یال های یکسانند

جواب= دو گزاره صحیح است
نادرستی گزینه ب که بدیهی است .
گزینه ج هم احساس میکنم باید اشتباه باشه!
گزینه الف هم اصلا نمیدونم برش کمینه چی هست!!!!!!!!!!!!!!!!!!!!!!
ممنون میشم دوستان نظرشون رو اعلام کنند

سلام،
کلید سنجش: "دو گزاره صحیح" - در مورد گزاره اول میشه مثال‌هایی آورد که با افزایش ثابت همه یال‌ها برش کمینه* تغییری نمی‌کنه، من البته این رو خیلی مطمئن نیستم و جایی هم مثال نقضش رو ندیدم و به احتمال زیاد درست هست. در مورد گزاره دوم درخت فراگیر کمینه هر دو گراف هم از نظر ساختاری یکی هست، برای مثال کراسکال رو روی یک لیست مرتب که یک افزایش روی تمام عناصر داشتیم مجددا اعمال کنید. اما در مورد گزاره سوم کوتاه‌ترین مسیر بین دو مسیر مشخص در دو گراف شامل یال‌های یکسان نیست، مسیری دارای یک یال یک واحد بهش اضافه میشه، دو یال دو واحد و n یال n واحد... . برای مثال بین X و Y دو مسیر داریم: مسیر مستقیم با اندازه ۷ و مسیر با سه یال ۲-۲-۲ که کوتاه‌ترین مسیر دومی هست اما وقتی در گراف دوم به همه یال‌ها یک مقدار اضافه می‌کنیم مسیر اول ۸ و مسیر دوم ۳-۳-۳ میشه که مطمئنا برخلاف قبل مسیر اول کوتاه‌تر هست.

--------------------

* در مورد گزینه اول:
قضیه برش کمینه و بیشینه مربوط به مبحث شبکه‌های شار یا جریان (Flow Networks) که تو فصل ۲۶ کتاب CLRS بهش اشاره شده که دارای یکسری قواعد هست که نمیشه اینجا به همش اشاره کرد، خیلی طولانی میشه؛ به صورت خلاصه اما:

منظور از S راس مبداء (منبع) و T راس مقصد (چاه) هست و صورت مسئله اینه که یک مدل برای انتقال جریان مواد از منبع به چاه از طریق مسیرهایی معین و با ظرفیت محدود (همون یال‌ها) پیدا کنیم. به عنوان مثال، جریان ورود و خروج آب، گاز، نفت در خط لوله و... برای مثال شما یک گراف با شش راس رو فرض کنید. منبع آب ما تهرانه فرضا و ۳۰ یال استانی ازش خارج شده، میگه مثلا من تا اصفهان ظرفیت انتقالم ۲۰ واحد، تا گیلان ۲۸ واحد، تا کرمان ۳۶ واحد و... (اعداد مثبت) و اون‌ها هم به همین ترتیب بین خودشون؛ حالا بیشترین یا کمترین ظرفیتی که من می‌تونم از تهران به اهواز آب‌رسانی کنم چه میزان هست؟ این رو میشه از طریق دنباله‌ای از وزن یال‌ها تشخیص داد. شبکه شار در نظریه گراف در راستای پیدا کردن بیشترین و کمترین مقدار جریان ممکن بین راس هاست.

و اما برش:
تو نظریه گراف منظور از برش، تقسیم رئوس گراف به دو زیرمجموعه ناتهی جدا از هم هست. یال‌های برش از یک برش به یال‌هایی گفته میشه که در مجموعه برش حاضر باشند. در مسئله برش کمینه هدف ما پیدا کردن این دو زیرمجموعه به نحوی هست که ظرفیت یال‌های برش رو Minimum کنیم.

فرضا ۶ تا راس داریم و قراره به دو زیرمجموعه ناتهی تقسیمشون کنیم و دو تا راه داریم: یا دنباله یال‌ها با وزن‌های ۴-۸-۲ رو حذف کنیم یا دنباله یال‌ها با وزن‌های ۴-۶-۲ رو که مطمئنا دومی (کمینه) رو انتخاب میشه و در واقع می‌گیم از طریق این سه یال یک برش کمینه با ظرفیت ۱۲ ایجاد کردیم. باید توجه کنیم که صرفا مجموع ظرفیت یال‌های جلورو در گراف رو در نظر می‌گیریم، نه همه یال‌هایی که برش می‌خورند.

ممنون که جواب دادید . دیگه داشتم نا امید میشدم




با توجه به توضیحات شما و این مطلبی که پیدا کردم (تصاویر ضمیمه شده)من اینطوری فهمیدم که:
از منبع یک یال با ظرفیت ۱۰ خارج میشه و یک یال با ظرفیت ۲۰/ یال گره a ظرفیت ۵ رو داره و ۱۵ تای دیگره رو نمیتونه عبور بده و اون ۵ تا رو به یال b میده که یال ظرفیتش بیشتره و همون ۵ تایی که بهش اومده رو عبور میده تازه از ۱۰ واحد خالی فضاش استفاده نمیکنه!
از طرفی یال c ظرفیتش ۱۰ هست و میتونه همونقدر که بهش اومده رو خارج کنهو به d میده پس چیزی رو هدر نمیده یال d هم ظرفیتش ۲۰ هست و توانایی عبور ۵ تا رو داره و چیزی که به چاه ریخته میشه میشه=۱۵
پس بیشترین جریان=۱۵
حالا من متوجه نشدم برشی که توی این تصویر گزاشته بر چه مبنایی هست و اگه ما گرافی با یال بیشتر داشتیم چند تا برش باید انجام بدیم ؟؟
اینی که من الان برداشت کردم ظرفیت کمینه است یا بیشینه؟؟؟؟؟؟؟؟؟؟؟؟ اگه این بیشینه است کمینش چی میشه