آمار پرسش:

• پرسیده شده: 2014-07-09 08:27:22 -0500
• مشاهده شده: 324 بار
• بروز شده: 2014-08-14 11:50:43 -0500

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

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

دلقک ها ی رنگی

برش ماکزیمم

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

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

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

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

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

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

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

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

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

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

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

علائم ریاضی:

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

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

6

ثابت کنید یک تورنمنت با $n$ راس وجود دارد که حداقل $\frac{n!}{2^{n-1}}$ تا مسیر همیلتونی دارد .

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

2014-07-09 08:27:22 -0500

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

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

نظرات

راهنمایی : یک جایگشت تصادفی در نظر بگیرید . احتمال اینکه این جایگشت نشان دهنده ی یک مسیر همیلتونی باشد را بدست آورید . و سپس از خطی بودن امید ریاضی استفاده کنید.

2014-07-15 14:25:27 -0500 حمید کاملی

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

2015-08-06 08:49:10 -0500 امیر شکری

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

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

3

یک راه حل احتمالاتی :

یک تورنمنت تصادفی از بین همه ی تورنمنت ها انتخاب می کنیم . به این صورت که هر یال را با احتمال $\frac{1}{2}$ جهت گذاری میکنیم.

برای هر جایگشت $a$ متغیر $X_a$ را برابر با یک قرار می دهیم اگر ترتیب رئوس متناظر با این جایگشت یک مسیر همیلتونی باشد و در غیر اینصورت برابر با صفر قرار می دهیم . متغیر تصادفی $X$ را برابر با تعداد مسیرهای همیلتونی در این تورنمنت تعریف می کنیم .

فرض کنید $S_n$ مجموعه ی تمام جایگشت های $n$ راس باشد . بدیهی است که

$X=\sum_{a \in S_n} X_a$

جایگشت $a$ در صورتی معادل یک مسیر همیلتونی است که جهت گذاری یالها برای $1\leq i \leq n-1$ از $a_i$ به $a_{i+1}$ باشد .

در واقع در صورتی یک جایگشت معادل با یک مسیر همیلتونی است که تمام یالهای ان رو به جلو باشد .

پس داریم $E[X_a]=\frac{1}{2^{n-1}}$

با توجه به خطی بودن امید ریاضی داریم $E[X]=\sum_{a\in S_n} E[X_a]=\frac{n!}{2^{n-1}}$

پس یک تورنمنت وجود دارد که تعداد مسیرهای همیلتونی ان حداقل $\frac{n!}{2^{n-1}}$ است.

2014-08-14 11:50:43 -0500

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

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