(۰۳ بهمن ۱۳۹۰ ۰۵:۳۲ ب.ظ)fatima1537 نوشته شده توسط:  یعنی برای تبدیل گراف به دو بخش مجزا سعی کنیم یالهای کمتری برش زده شوند و همچنین یالهایی را برای برش انتخاب کنبم که اگر وزن مربوط به یالها را باهم جمع بزنیم دارای کمترین مقدار باشند.فکر میکنم منظور سئوال اینه که هم تعداد یالها کمتر باشه هم مجموع وزن یالها .
توی عنوان تاپیک نوشتید سئوال هوش ولی این سئوال مربوط به الگوریتم هست

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

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

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

(۰۳ بهمن ۱۳۹۰ ۰۳:۵۳ ق.ظ)fatima1537 نوشته شده توسط:  برش یک گراف با کمترین تعداد یال ممکن-این گزینه هم منظورش اینه که آیا اگر به وزن همه یالها یکی اضافه کنیم آیا باز هم برش کمینه گراف جدید تغییر خواد کرد؟ جوابش مثبته.

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