آمار پرسش:

• پرسیده شده: 2014-06-17 10:53:06 -0500
• مشاهده شده: 276 بار
• بروز شده: 2014-08-11 11:55:52 -0500

پرسش‌های مشابه:

چرخاندن میز با n مهمان طوری که حداقل دو مهمان سرجای خود قرار بگیرند

دلقک ها ی رنگی

92 نفر دور میز - ظرفهای غذا

مساله ی مسابقه ی دانشجویی 93_ ماتریس

تعداد گراف‌های دو بخشی و غیردوبخشی $n$راسی و $2n$ یالی

200 دانش جو و 6 مساله

تورنمنت با تعداد زیادی مسیر همیلتونی

گروهی از دانش آموزان شامل حداقل نصف افراد ، هر پسر با تعداد فردی دختر دوست است

n نفر با کلاه های قرمز و آبی و حدس زدن بیشترین تعداد درست

n زیرمجموعه با میانگین اندازه ی داده شده و وجود دو زیرمجموعه با اشتراک زیاد.

نکاتی در مورد نوشتن پاسخ:

در این قسمت می‌تونی به یک پرسش پاسخ بدی. اگه می‌خوای در مورد پرسش بحث و اظهار نظر کنی از قسمت «ثبت نظر» استفاده کن.
پاسخت رو دقیق و کامل بنویس، از عکس استفاده کن و اگه لازمه به منابع (کتاب یا سایت) ارجاع بده.
اگه پرسش یا پاسخ‌ها مفید هستند حتما بهشون رای بده تا پرسش‌ها و پاسخ‌های خوب مشخص بشن.

استفاده از ویرایشگر:

توی قسمت پیش‌نمایش می‌تونی ببینی متنی که نوشتی چجوری روی سایت دیده میشه.
خیلی مهم: برای اینکه به خط بعد بری باید دوتا Enter بزنی.
می‌تونی از تگ‌های معمولی و ساده‌ی html هم استفاده کنی.
با دکمه‌هایی که بالای ویرایش‌گر قرار دارند کلی کار می‌شه کرد. از عکس‌گذاشتن بگیر تا لیست شماره‌دار. حتما امتحان‌شون کن.

علائم ریاضی:

برای نوشتن علائم ریاضی می‌تونی از Mathjax استفاده کنی. راهنمای Mathjax رو از سایت math.stackexchange بخون.
برای نوشتن عبارت ریاضی وسط جمله، اون عبارت رو بین دوتا $ قرار بده.
برای نوشتن عبارت ریاضی تو یه خط جدید اون رو بین دوتا $$ قرار بده.

برش ماکزیمم

5

فرض کنید گراف G ، $m$ یال دارد . ثابت کنید می توان راس های گراف G را به دو قسمت طوری افراز کرد که تعداد یالهایی که بین این دو بخش قرار می گیرد حداقل $\frac{m}{2}$ باشد .

روش-های-احتمالاتی

2014-06-17 10:53:06 -0500

حمید کاملی 2921 ● 30 ● 56 ● 83

پاک‌کردن   ویرایش سوال

نظرات

برش مینیمم داریم ولی برش ماکزیمم فک نکنم داشته باشیم . ( minimum cut & maximum flow) . اسم این چیزی که شما می خوای یک افراز بندیه .اسم سوالتو عوض کن و تگ گراف رو هم اضافه کن لطفا . :)

2014-06-17 17:43:09 -0500 محمدمهدی

برش ماکزیمم هم داریم . افراد زیادی تو دنیا دارن روی این مساله کار می کنند . و ثابت شده که در زمان چند جمله ای نمی توان برش ماکزیمم در گراف رو پیدا کرد .

2014-06-18 04:07:27 -0500 حمید کاملی

سلام میدونستید انجمن علمی نخبگان دانشگاه صنعتی شریف مسابقه تخصصی مهارت سنجی برنامه نویسی و داده کاوی گذاشته است آدرس سایتش www.fanavard.com

2015-08-06 08:51:07 -0500 امیر شکری

سلام میگم یک سر به سایت www.fanavard.ir بزنید. مسابقات برنامه نویسی شون شروع شده. گواهی رسمی از طرف دانشگاه شریف می ده. 50 تا سکه هم جایزشه

2016-10-26 08:09:12 -0500 امیر شکری

5

روش احتمالاتی برای حل این سوال :

راس ها را به صورت تصادفی در یکی از دو بخش ‎$A‎$‎‎‏ و ‎‎$‎B‎$‎‏ قرار می دهیم .

متغیر تصادفی ‎‎$‎‎X_i$‎‏ را برابر با یک در نظر می گیریم اگر یال ‎‎$‎i‎$‎‏ ام بین دو بخش ‎‎$‎A‎$‎‏ و ‎‎$‎B‎$‎‏ قرار گرفت و در غیر اینصورت برابر با صفر قرار می دهیم .

متغیر تصادفی ‎‎$‎X‎$‎‏ را برابر با تعداد یالهایی قرار می دهیم که بین دو بخش ‎‎$‎A‎$‎‏ و ‎‎$‎B‎$‎‏ قرار می گیرد.

بدیهی است که ‎$‎‎X=\sum_{i=1}^m X_i$‎‎

‏امید ریاضی متغیر تصادفی ‎‎$‎X_i‎$‎‏ برابر است با ‎‎$‎‎‎\frac{1}{2}‎$‎.‏ در نتیجه ‏امید‎ ریاضی متغیر تصادفی ‎‎$‎X‎$‎‏ به این صورت است .

‎‎$‎E[X]=\sum_{i=1}^m E[X_i]‎=‎‎\frac{m}{2}‎‎$‎

‎‏در نتیجه در بین تمام روشهای مختلف افراز کردن راس ها به دو قسمت افرازی وجود دارد که یالهایی که بین دو بخش قرار می گیرد حداقل ‎‎$‎‎‎\frac{m}{2}‎$‎‎ ‎‏است.

2014-06-18 04:09:25 -0500

حمید کاملی 2921 ● 30 ● 56 ● 83

پاک‌کردن   ویرایش پاسخ

4

ابتدا راس هارو به 2 دسته ی دل خواه تقسیم می کنیم.زیر گراف H رو تمام راس های G و یال های بین دو دسته فرض می کنیم. تا وقتی درجه راسی تو H کمتر از نصف درجه اش تو G است ، اون راس رو به دسته ی دیگر منتقل می کنیم . این الگوریتم یه جا تموم می شه چون تعداد یال های زیر گراف G با هر حرکت افزایش پیدا می کنه و این تعداد یال حد اکثر برابر تعداد یال های G است و بی نهایت نیست . بنابر این در پایان ایم اگوریتم درجه هر راس تو H بزرگتر مساوی درجه اش تو G است . از اونجا که $ 2e=\Sigma d$ پس تعداد یال های H حد اقل نصف یال های G است .

( کتاب وست ، بخش 1.3 )

2014-06-17 17:40:41 -0500

محمدمهدی 129 ● 3

پاک‌کردن   ویرایش پاسخ

نظرات

می شه این جواب رو با اکسترمال هم توضیح داد .

2014-06-18 04:08:22 -0500 حمید کاملی