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

در یک گراف با وزن های صحیح بزرگتر از ۱ فرض کنید وزن هر یال را ۱ واحد زیاد کنیم انکاه
برش کمینه (S,T) در هر دو گراف یکی است

لطفا توضیح دفید برش کمینه جیه؟

برش یک گراف با کمترین تعداد یال ممکن

(03 بهمن 1390 03:53 ق.ظ)fatima1537 نوشته شده توسط: [ -> ]برش یک گراف با کمترین تعداد یال ممکن-این گزینه هم منظورش اینه که آیا اگر به وزن همه یالها یکی اضافه کنیم آیا باز هم برش کمینه گراف جدید تغییر خواد کرد؟ جوابش مثبته.

ممنون از جوابتان
ولی برش یک گراف با کمترین تعداد یال ممکن یعنی چی؟

یعنی برای تبدیل گراف به دو بخش مجزا سعی کنیم یالهای کمتری برش زده شوند و همچنین یالهایی را برای برش انتخاب کنبم که اگر وزن مربوط به یالها را باهم جمع بزنیم دارای کمترین مقدار باشند.فکر میکنم منظور سئوال اینه که هم تعداد یالها کمتر باشه هم مجموع وزن یالها .
توی عنوان تاپیک نوشتید سئوال هوش ولی این سئوال مربوط به الگوریتم هست

(03 بهمن 1390 05:32 ب.ظ)fatima1537 نوشته شده توسط: [ -> ]یعنی برای تبدیل گراف به دو بخش مجزا سعی کنیم یالهای کمتری برش زده شوند و همچنین یالهایی را برای برش انتخاب کنبم که اگر وزن مربوط به یالها را باهم جمع بزنیم دارای کمترین مقدار باشند.فکر میکنم منظور سئوال اینه که هم تعداد یالها کمتر باشه هم مجموع وزن یالها .
توی عنوان تاپیک نوشتید سئوال هوش ولی این سئوال مربوط به الگوریتم هست

ممنون از جوابهایتان و لی به کمانم گراره مذکور درست هست جون اصل سوال این است که از 3 گزاره ریر چند تایش درباره گرافی با وزنهایی بزرگتر از 1 که وزن هریال ان را یکی اضافه کرده ایم درست هست
برش کمینه (S,T) در هر دو گراف یکی است
درخت فراگیر کمینه هر دو گراف یکی است
کوتاهترین مسیر بین دو راس مشخص در دو گراف شامل یالهای یکسانی هستند

جواب 2 اعلام شده بود و می دانم که گزاره سوم غلط است
لطفا بگویید چرا گزاره اول درست هست

با شکل نمایش دادم. در شکل الف برزش کمینه گراف مشخص شده و در شکل ب اگر وزن هر یال ۱ واحد اضافه شود باز هم برش تغییری نمیکند
من متوجه صورت سئوال نشده بودم چون ضمیمه نشده بود ولی ظاهرا گفته ازبین جملات زیر کدام درست است.ارسالم رو اصلاح کردم
یه توضیح دیگه ای باشکل برای برش کمینه دادم . که حداقل یالهای ممکن برش داده شده اند