آمار پرسش:

• پرسیده شده: 2016-08-30 14:43:17 -0600
• مشاهده شده: 423 بار
• بروز شده: 2016-09-05 02:45:26 -0600

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

شبکه $n\times n$ پایدار

پیدا کردن گراف دوبخشی کامل یکرنگ

حداکثر تعداد یال‌های گراف بدون مثلث

آیا گراف قویا همبند است؟

اثبات همبند بودن مکمل گراف ناهمبند

همه را با تلفن خبر کنید - دوره ی 05 - مرحله ی 1

رنگ‌آمیزی صفحه بخش‌بندی شده توسط دایره‌ها با دو رنگ

دنباله ی درجات گراف

پیدا کردن مولفه های قویا همبند گراف جهت دار

انگور، آن هم از نوع «درختی» - آزمون دوم آزمایشی شاززز

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

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

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

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

علائم ریاضی:

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

ثابت کنید تورنومنتی با دقیقا دو کینگ وجود ندارد (و در نتیجه حداقل سه کینگ دارد...)

2

ثابت کنید در تورنومنتی که $n>=3$ راس دارد ممکن نیست که دقیقا دو کینگ داشته باشد.. .

تورنومنت : گراف کامل جهت دار

کینگ : به راسی می گویند که به تمام رئوس دیگر گراف با مسیری به اندازه حداکثر طول دو یال بتواند برود.

گراف کینگ

2016-08-30 14:43:17 -0600

دباغها 204 ● 5 ● 7 ● 13

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

نظرات

+1 . مرسی که سوالهات رو اینجا با بچه ها به اشتراک می زاری.

2016-09-05 09:59:46 -0600 حمید کاملی

:) خواهش استاد

2016-09-05 12:24:45 -0600 دباغها

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

2016-10-26 08:14:11 -0600 امیر شکری

2

راهنمایی : فرض خلف کنید که دقیقا دو کینگ وجود دارد .. سپس یک کینگ دیگر هم پیدا کنید.

لم : هر تورنومنتی حداقل یک کینگ دارد . اثبات

اثبات :

فرض کنید دو کینگ u و v باشند و $u \to v$ . چون که v کینگ است پس باید بتوان به واسطه راس دیگری از v به u رفت . پس $n - 1 > d(u)$ یعنی رئوسی وجود دارند که u را برده اند. حال این مجموعه رئوس را یک زیرتورنومنت درنظر بگیرید، در این زیرتورنومنت حداقل یک کینگ وجود دارد. این راس را w بنامید. از آنجایی که $w \to u$ پس w به تمام رئوس باخته از u هم با دو یال میتواند برود ... پس w کینگ گراف است... و از آنجایی که v و w هم بدیهتا متفاوت اند .. پس حداقل 3 کینگ وجود دارد.

2016-09-05 02:43:28 -0600

دباغها 204 ● 5 ● 7 ● 13

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

نظرات

قشنگ بود.

2016-09-06 07:34:47 -0600 محمد شاه وردی