حداکثر تعداد یال‌های گراف بدون مثلث
اثبات همبند بودن مکمل گراف ناهمبند
همه را با تلفن خبر کنید - دوره ی 05 - مرحله ی 1
رنگ‌آمیزی صفحه بخش‌بندی شده توسط دایره‌ها با دو رنگ
پیدا کردن مولفه های قویا همبند گراف جهت دار
انگور، آن هم از نوع «درختی» - آزمون دوم آزمایشی شاززز
یافتن کوتاه ترین دور در گراف ساده
فرض کنید که $n$ و $k$ داده شده‌باشند. ثابت کنید که $m$ای وجود دارد به طوری که اگر یال‌های گراف دوبخشی کامل $m,m$ را به صورت دلخواه با $k$ رنگ، رنگ آمیزی کنیم؛ در آن زیر گراف دوبخشی کامل $n,n$ وجود دارد که یال‌های آن همرنگ است.
سلام میدونستید انجمن علمی نخبگان دانشگاه صنعتی شریف مسابقه تخصصی مهارت سنجی برنامه نویسی و داده کاوی گذاشته است آدرس سایتش www.fanavard.com
2015-08-06 06:48:49 -0500 امیر شکریسلام میگم یک سر به سایت www.fanavard.ir بزنید. مسابقات برنامه نویسی شون شروع شده. گواهی رسمی از طرف دانشگاه شریف می ده. 50 تا سکه هم جایزشه
2016-10-26 10:30:20 -0500 امیر شکریابتدا توجه کنید که اگر ما یک گراف دو بخشی کامل $m,m'$ را بدست آوریم که شرط مسأله را دارا باشد(فرض کنید $m>m'$) آن‌گاه گراف دوبخشی کامل $m,m$ نیز شرط مسأله را دارد.
فرض کنید که ما در بخش اول $nk$ رأس بگذاریم. حال اگر یک رأس $v$ در بخش دوم قرار دهیم، یال بین $v$ و رأسی مانند $u$ از بخش اول $k$ رنگ می‌تواند بگیرد. بنابراین در کل حالات رنگ آمیزی یال‌های بین رأس اول و بخش اول برابر $k^{nk}$ است. حال اگر ما در بخش دوم به تعداد $k^{nk}n + 1$ رأس بگذاریم، طبق اصل لانه کبوتری حداقل $n$ رأس وجود دارد که نحوه رنگ آمیزی آن‌ها با رئوس بخش اول یکسان است. این مجموعه رئوس را با $\mathcal{A}$ نمایش می‌دهیم.این بدین معنی است که یال‌های بین یک رأس از بخش اول با یک رأس از $\mathcal{A}$ رنگ یکسانی دارند.
حال چون ما $nk$ رأس در بخش اول داریم و یال‌ها با $k$ رنگ، رنگ آمیزی شده‌اند؛ بنابراین طبق اصل لانه کبوتری حداقل $n$ تا رأس وجود دارد که رنگ یال‌های آن‌ها با رئوس $\mathcal{A}$ یکسان است. بنابراین ما یک زیرگراف دوبخشی کامل حداقل $n,n$ تایی داریم که رنگ یال‌ها در آن یکسان است. بنابراین یک زیرگراف دوبخشی کامل $n,n$ یکرنگ خواهیم داشت. حال طبق آن‌چه در ابتدای جواب آوردیم، حکم ثابت می‌شود.