دانلود مقاله ترکیبات و نظریه‌ی گراف

در این مقاله می خواهیم به دو مبحث بزرگ از ریاضیات گسسته با نامهای ترکیبات و نظریه‌ی گراف بپردازیم که در این دوران شاهد پیشرفت چشمگیر آنها می باشیم .

این دو مبحث بدلیل آنکه دارای کاربرد وسیعی در علم کامپیوتر و برنامه سازی های کامپیوتری می‌باشند حائز اهمیت فراوان می باشند .

1-ترکیبات :
شاید در نگاه اول ترکیبات یک بخش معماگونه و سطحی از ریاضیات به نظر برسد که دارای کاربرد چندانی نبوده و فقط مفهوم های انتزاعی را معرفی می کند ولی این شاخه از ریاضیات دارای گستره‌ی وسیع بوده و دارای شاخه های زیادی نیز می باشد .

ابتدا به مسأله ای زیبا از ترکیبات برای آشنا شدن بیشتر با این مبحث ارائه می کنیم .

سوال : یک اتاقی مشبک شده به طول 8 و عرض 8 داریم که خانه‌ی بالا سمت چپ و خانه‌ی پایین سمت راست‌ آن حذف شده است (مانند شکل زیر)








حال ما دو نوع موزاییک داریم .

یکی 2*1 ( ) و دیگری 1×2 ( ) سوال این است که آیا می توان این اتاق را با این دو نوع موزائیک فرش کرد .

احتمالاً اگر شخص آشنایی با ترکیبات نداشته باشد می گوید «آری» و سعی می کند با کوشش و
خطا اتاق را فرش کند ولی این کار شدنی نیست ؟!

و اثبات جالبی نیز دارد .

اثبات : جدول را بصورت شطرنجی رنگ می کنیم مانند شکل زیر :
حال با کمی دقت متوجه می شویم که هر موزائیک یک خانه از خانه های سیاه و یک خانه از خانه‌های سفید را می پوشاند یعنی اگر قرار باشد که بتوان با استفاده از این موزائیک ها جدول پوشانده شود باید تعداد خانه های سیاه با تعداد خانه های سفید برابر باشد ولی این گونه نیست زیرا تعداد خانه های سفید جدول برابر 32 و تعداد خانه های سیاه برابر 30 می باشد .

در نتیجه این کار امکان امکان پذیر نیست .

این مسأله مربوط به مسائل رنگ آمیزی در ترکیبات بوده که دارای دامنه‌ی وسیعی از مسائل دشوار و پیچیده می باشد در زیر چند نمونه از مسائل آسان و سخت را بیان می کنیم .

1-ثابت‌کنید هیچ جدولی را نمی توان به موزائیک هایی به شکل و پوشاند .

(راهنمایی: ثابت کنید حتی سطر اول جدول را هم نمی توان پوشاند)
2-ثابت کنید یک مهره‌ی اسب نمی تواند از یک خانه‌ی دلخواه صفحه‌ی n*4 شروع به حرکت کند و تمام خانه ها را طی کند .

3-یک شبکه‌ی n*m از نقاط داریم یک مسیر فراگیر مسیری است که از خانه‌ی بالا سمت چپ
شروع به حرکت کرده و از همه‌ی خانه هر کدام دقیقاً یک بار عبور کند و به خانه‌ی سمت راست پایین برود ثابت کنید شرط لازم و کافی برای وجود یک مسیر فراگیر در شبکه‌ی n*m آن است که لااقل یکی از m یا n فرد باشد (مرحله‌ی دوم المپیاد کامپیوتر ایران) در شکل زیر یک مسیر فراگیر را برای جدول 5*4 می بینیم .

B
4-ثابت کنید شرط لازم کافی برای پوشش جدول n*m با موزائیک های 2*1 یا 1*2 آن است که یا m یا n زوج باشند .

حال می‌خواهیم یک مبحث مهم از ترکیبات به نام استقراء را معرفی کنیم.

استقراء بعنی رسیدن ازجزء به کل و هم ارز است با اصل خوشترتیبی زیر مجموعه‌ها( اصل خوشتربینی بیان می‌کند که هر مجموعه متناهی از اعداد عضوی به نام کوچکترین عضو دارد).

برای اثبات حکمی به کمک استقراء لازم است:
1) حکم را برای یک پایه دلخواه(که معمولاً کوچک باشد) ثابت کنیم.

2) حکم را برای یک k دلخواه فرض می‌گیریم.

3) به کمک قسمت 2 حکم را برای ثابت می‌کنیم.

بسیاری از گزاره‌ها به کمک این استقراء که در ظاهر ساده است ثابت می‌شود:
یک مثال ساده:
ثابت کنید: .

برای که داریم و حکم برقرار است:
فرض کنیم برای درست باشد حکم را برای ثابت می‌کنیم داریم:


که این قسمت طبق فرض بردار می‌باشد
و برای نیز حکم مسأله برقرار است.

یک مثال سخت:
این سئوال در المپیاد کامپیوتر امسال مطرح شده و ما فقط یک قسمت آنرا بطور خلاصه بیان می‌کنیم.

سئوال: در روز A دارای تعداد مجموعه می‌باشد بطوریکه هیچ مجموعه‌‌ای زیرمجموعه دیگری نیست یعنی اکر )
حل شایان در روز B می‌آید از روی مجموعه‌های A تمام مجموعه‌هایی را نمی‌سازیم که دارای دو شرط زیر می‌باشند:
1- هر مجموعه‌ای دلخواه در روز B با تمام مجموعه‌ها در روز A اشتراک دارد.

2-اگر از یک مجموعه دلخواه در روز B یک عضو را حذف کنیم آنگاه دیگر شرط 1 برقرار نباشد( که به این شرط، شرط مینیمالی می‌گوئیم:
حال فراز در روز C از روی مجموعه‌های B تمام مجموعه‌هایی با دو شرط بالا را می‌سازد ثابت کنید ( یعنی تمام مجموعه‌های روز اول در روز سوم نیز تولید شده‌اند)
اثبات: ابتدا لم زیر را ثابت می‌کنیم: لم: به ازای هر مجموعه دلخواه در روز A مثل در روز B n تتا مجموعه وجود دارند بطوریکه هر کدام از آنها دقیقاً یکی از اعضای را دارند( ممکن است اعضای دیگری نیز داشته باشند ولی هر کدام دقیقاً یکی از را دارند.) اثبات لم: با استقراء روی تعداد مجموعه‌های روز اول حکم را ثابت می‌کنیم.

برای یک مجموعه در روز A وضعیت مجموعه‌ها در روزهای C,B,A مشخص شده‌اند: و حکم برقرار است زیرا حال فرض کنیم حکم برای درست باشد حکم را برای بدین ترتیب ثابت می‌کنیم که: اگر ثابت کنیم لم برای یک مجموعه دلخواه در روز A برقرار است اثبات لم کامل است یک مجموعه دلخواه در A را در نظر می‌گیریم مثل حال مجموعه را حذف می‌کنیم حال طبق فرض مجموعه هست که از هر کدام از دقیقاً یک عضو دارد.

حال وقتی که مجموعه را اضافه می‌کنیم دوحالت پیش می‌آید: - مجموعه قسمت فرض، هرکدام از آن مجموعه‌ها دارای دو شرط 1و2 می‌باشند.

2) تمام اعضای در می‌باشد که در این صورت چون نسیت پس عضوی دارد که در نیست و می‌توانیم آن عضو را به مجموعه اضافه کرده حال این مجموعه شرط 1 را دارا می‌باشند ولی شاید بعضی از آنها شرط 2 را نداشته باشند که می‌توان با حذف تعدادی از اعضاء آنها را به حالت مینیمال رساند و شرط 2 نیز برقرار ساخت و اثبات لم کامل است.

حال فرض کنیم عضوی از A باشد که در C نیامده باشد ثابت می‌کنیم این عضو هر دو شرط را برای مجموعه B دارا می‌باشد و چون C تمام مجموعه‌هایی است که این دو شرط را برای مجموعه B دارند پس آن عضو A نیز باید در C نیز بیاید اول آن عضو A باید با هر کدام از اعضای B اشتراک دارد زیرا هر کدام از اعضای B با هر کدام از اعضای A اشتراک دارند و طبق لم نیز هر کدام از اعضای A مینیمال نیز می‌باشند و حکم درست است.

اصل لانه کبوتری: اصلی ساده در ترکیبات است که بسیاری از مسائل با آن حل می‌شوند و صورت آن به شرح زیر است: اصل لانه کبوتری: اگر مروارید را در داخل k جعبه بگذاریم حتماً‌ جعبه‌ای وجود دارد که حداقل عدد مروارید در آن می‌باشد.

یکی از مثالهای ساده و زیبای این اصل سئوال زیر است: در جمعی n نفر حضور دارند بعضی از اشخاص این جمع با هم دست می‌دهند ثابت کنید این جمع دو نفر وجود دارند که با تعداد برابر دست داده‌اند.

اثبات: هر نفر می‌تواند با 0 تا n-1 نفر دست دهد حال اگر فردی باشد که با همه دست داده باشد آنگاه فردی نیست که با کسی دست نداده باشد و بالعکس بنابراین در این جمع هیچکاه دو نفر وجود ندارد که یکی با 0 و دیگری با n-1 نفر دست داده باشد.

حال فرض کنیم هیچ شخصی وجود نداشته باشد که به تعداد برابری دست داده باشند و چون تعداد این دست دادنها از 0 تا n-1 است ( کلاً n عدد) پس هم باید 0 بیاید و هم n-1 که این خلاف گفته‌های بالا می‌باشد.

یک مثال نسبتاً سخت: ثابت کنید اعداد در مجموعه وجود دارند که در معادله‌ای زیر صدق بکند:( همه ها نمی‌توانند صفر باشند.

اثبات: ابتدا همه را تنها با دو عدد 1و 0 جایگذاری می‌کنیم که این به حالت امکان‌پذیر است سپس اگر هیچکدام از این جایگذاری‌ها به پیمانه صفر نشدند پس طبق اصل لانه کبوتری دو جایگذاری می‌باشند که باقیمانده یکسانی نسبت به دارند( زیرا باقیمانده‌ها باید از 1 تا باشد و ما جایگذاری داریم.) حال اگر ما جایگذاری اول را A و جایگذاری دوم را B بگیریم A-B یک جایگذاری مطلوب است و همچنین تمام ها نیز د رمجموعه قرار نمی‌گیرند.

چند سئوال: ثابت کنید در بین هر 6 نفر یا 3 نفر هستند که دو به دو یکدیگر را می‌شناسند یا 3 نفر هستند که دوبه‌دو یکدیگر را نمی‌شناسند( آشنایی رابطه‌ای دو طرفه است یعنی اگر B,A را بشناسد B نیز A را می‌شناسد.

2- اعدادی حقیقی تا را دور دایره نوشته‌ایم بطوریکه برای یک می‌باشد.

حال ما از یک نقطه دلخواه شروع می‌کنیم و درجهت عقربه‌های ساعت حرکت را ادامه می‌دهیم حال اگر از رأس شروع کرده‌باشیم مجموعه زیر را Sمی‌نامیم: یعنی به عدد اول 3 را ضرب در عدد دوم و در عدد n ام درجهت عقربه‌های ساعت را ضرب می‌کنیم برای شکل زیر اگر از دو عدد شروع کنیم برابر: ثابت کنید مکانی وجود دارد که اگر از آن شروع به حرکت کنیم S بزرگتر مساوی می‌شود.

( مرحله دوم المپیاد کامپیوتر ایران) در آخر بخش ترکیبات نیز چند مسأله که در المپیاد‌ها مطرح شده می‌آوریم: 1- درجه ولی تعداد مهره وجود دارد حال اگر در خانه بیش از یک مهره قرار داشت می‌توان یکی از دو حرکت زیر را انجام داد.

1- دو مهره را انتخاب کرده و یکی را حذف کرده و دیگری را به خانه سمت راستی برد.

2- دو مهره را انتخاب کرده و یکی را حذف کرده و دیگری را به خانه سمت راست برد.

ثابت کنید اگر تعداد مهره‌ها بیشتر مساوی باشد می‌توان با استفاده از این دو عمل یک مهره را به خانه گوشه سمت راست و بالا انتقال داد( مرحله دوم المپیاد ریاضی) 2- در کهکشان راه شیری بیش از یک میلیون ستاره قرار دارد فاصله دو به دوی این ستاره‌ها را حساب می‌کنیم ثابت کنید در این اعداد لااقل 79 عدد متمایز قرار دارد.( مرحله دوم المپیاد ریاضی).

3- تعداد جداول که با 1و 1- پرشده و حاصلضرب اعداد هر سطر وهر ستون نیز مثبت است ( مرحله دوم المپیاد کامپیوتر) یک سئوال سخت: 4- ثابت کنید ماکزیمم تعداد زیرمجموعه‌های که از مجموعه می‌توان انتخاب کرد بطوریکه هیچ زیرمجموعه‌ای، زیرمجموعه، زیرمجموعه دیگر نباشد می‌باشد.

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

تعریف گراف: گراف را با مجموعه رئوس 7 و مجموعه یالهای E تعریف می‌کنند بطوریکه هر یال دو رأس را به هم وصل می‌کند( یالها ممکن است جهت‌دار باشند) معمولاً گراف را در صفحه با نقطه برای نمایش رأسها و خط برای نمایش یالهای استفاده می‌شود مثلاً: یک گراف جهت‌دار یک گراف ساده یک مسیر در گراف از رأس u بربه رأس v مسیری است از یالها از u بهv بطوریکه رأس تکراری نرویم مثلاً در گراف زیر یک مسیر از رأس u به رأس v مشخص شده( به صورت یالهای هاشور خورده).

یک گراف را همبندی می‌نامیم اگر بین هر دو رأس آن یک مسیر وجود داشته باشد.

مثلاً شکلهای زیر را ببینید.

یک گراف ناهمبند یک گراف همبند یک دور گراف مسیری را از رأس u به خود رأس u می‌باشد که حداقل یک یال داشته باشد مثلاً دور زیر: یک درخت یک گراف همبندی دور می‌باشد.

یک زیرگراف از G گرافی است که و می‌باشد.

یک زیرگراف القایی زیرمجموعه‌ای از رئوس است بطوریکه تمام یالهای G دو سرش در این رئوس باشد.

درجه یک رأس در یک گراف ساده عبارت است از تعداد یالهایی که آن رأس رویشان قرار دارد برای مثال درجه رئوس گراف زیر روی هر رأس نوشته شده‌است.

درجه رأس V را باdeg(v) نمایش دهیم.

قضیه: اگر تعداد یالهای گراف را با e نمایش دهیم داریم: اثبات: زیرا هر یال درجه 2 رأس هرکدام یکی افزایش می‌دهد.

یکی ازنتایج بسیار مهم این قضیه آن است که تعداد رأس با درجه فرد رد یک گراف زوج است با استفاده از این قضیه کوچک مسائلی حل می‌شوند که در حالت عادی و بدون استفاده از گراف بسیار سخت بودند.

سئوال: یک رشته کوه عبارت است از: یک خم چندضلعی شکل از (a,0) و (b,0) در نیم صفحه بالای فرض کنیم شایان و فراز به ترتیب در نقاط(a,0) و (b,0) واقع باشند ثابت کنید شایان و فراز با سوزوی رشته کوه بطوریکه در همه زمانها ارتفاع‌های آنها بالای محور افقی یکی باشد یکدیگر را ملاقات می‌کنند( راهنمای: گرافی را برای مدلسازی حرکت تعریف کنید و از زوجیت تعداد رأسها با درجه فرد استفاده کنید) سئوال از کتاب D-west بوده و طرح این سئوال از دی‌ها ضمن می‌باشد.

مثال: ثابت کنید هردرخت حداقل دو برگ دارد( برگ به رأس در گراف گویند که درجه‌اش یک می‌باشد).

اثبات: طولانی‌ترین مسیر را در درخت در نظر می‌گیریم.

مانند شکل زیر فرض کنیم دو سیر مسیر رئوس v,u باشند چون گراف دورندار پس v,u فقط به v u یکی از رئوس مسیر وصل می‌باشند همچنین چون v,u نمی‌توانند به رأس از خارج مسیر وصل باشند( چون در آن صورت مسیر بلند‌تری بوجود می‌آید) پس درجه هرکدام از v,u یک می‌باشد و حکم اثبات شد حال با حل یک مثال این بخش را به پایان می‌بریم و به سراغ جورسازی در گرافها می‌رویم: این سئوال درمرحله دوم المپیاد کامپیوتر ایران سال 84 مطرح شد.

سئوال: در یک کشور می خواهیم تعدادی جاده بین شهرهای کشور بسازیم بطوریکه خواص زیر را دارا باشد.( بعضی ازجاده‌ها را نمی‌توان ساخت) 1) از هر شهر به شهر دیگری مسیر باشد.

2) اگر یکی از این جاده‌ها حذف شود شرط الف از امتیاز بیفتد.

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

اثبات: یک یال را بد می‌گوئیم اگر بین دو برگ باشد از بین تمام نقشه‌های قابل ساخت طرحی را در نظر می‌گیریم که کمترین تعداد یال بد را داشته باشد .

حال می‌آئیم نقشه را از پایتخت آویزان می‌کنیم فرض کنیم دو برگ v,u به هر یال داشته باشند مانند شکل زیر: بدیهی است که روی مسیر v تاr همه رئوس از درجه دو می‌باشد حال می‌آئیم نقشه زیر را به نقشه زیر تبدیل می‌کنیم.

اکنون در این نقشه می‌توان دید که مجموع فواصل کمتر مساوی مجموع فواصل درخت قبل است پس این نقشه نیز قابل ساخت می‌باشد و همچنین در این نقشه از تعداد یالهای یکی کم شده و این خلاف فرض ما مبنی بر مینیمم بدون تعداد یالهای بدتناقض دارد در نتیجه درخت اولیه نباید هیچ یال بدی داشته باشد و حکم مسأله اثبات شد.

در این اثبات از قضیه زیر استفاده شده‌است.

اگر یک زیر درخت از گراف G باشد و e و e1 دو یال باشند که در یک دور G شرکت دارند و داریم و آنگاه گراف نیز یک درخت است حال چند مسأله از گراف مقدماتی بیان می‌کنیم.

1- ثابت کنید اگر درجه هر رأس گراف بیشتر مساوی p باشد آنگاه مسیری به طول p در این گراف وجود دارد.

2- منظور از مرکز یک درخت رأسی است ماکزیمم فاصله آن تا تمام رئوس مینیمم باشد مثلاً در درخت زیر مرکز با حروف C مشخص شده‌است.

حال ثابت کنید هردرخت یا یک یا دو مرکز مجاور دارد.

3- می‌خواهیم اعداد 1 تا e را به یالهای گراف G نسبت دهیم بطوریکه برای هر رأس v بزرگترین مقسوم‌‌علیه مشترک یالهای مجاور این رأس یک باشد ثابت کنید برای هر گراف این کار امکان‌پذیر است مثلاً برای گراف زیر یک عددگذاری مشخص شده‌است.

4- در یک اتاق n 2 نفر حضور دارند ثابت کنید دو نفر وجود دارند که تعداد آشناهای مشترک آن دو زوج است( آشنایی یک رابطه دوطرفه است).

جورسازی در گراف یک جورسازی در گراف مجموعه‌ای از یالهای دوبه دو مجزا از رأس می‌باشد.

به هر رأسی که در جورسازی شرکت کند یک رأس آلوده می‌گوئیم مثلاً درگراف زیر یک جورسازی با خطوط‌ هاشور خورده مشخص شده‌اند.

یک جورسازی را ماکزیمم می‌گوئیم اگر ماکزیمم تعداد یالهای ممکن را داشته باشد.

یک گراف را دوبخشی می‌نامیم اگر بتوان مجموعه رئوس این گراف را به دو بخش B,A تبدیل کرد که هر یال یک رأس در بخش A یک رأس در بخش B داشته باشد حال دو قضیه مهم در گرافهای دوبخشی را در زیر می‌آوریم.

قضیه یک: هرگراف G یک زیرگراف G1 دارد که لااقل نصف یالهای G را دارد.

قضیه دو: یک گراف G دوبخشی است اگر و فقط اگر دور فرد نداشته باشد.

حال در یک گراف دو بخشی با بخشهای Y,Z می‌گوئیم یک جورسازی بخش X را می‌پوشاند اگر و فقط اگر جورسازی دارای اندازه X باشد قضیه فیلیپ حال شرطی لازم و کافی را برای وجودیک جورسازی به اندازه X در گراف با بخشهای Y,X ارائه می‌دهد.

قضیه فیلیپ‌هال: در یک گراف دو بخشی با افراز مضاعف Y,X یک جورسازی به اندازه X وجود دارد اگر و فقط اگر به ازای هر زیر مجموعه رئوس X مانند X داشته باشیم (n(s) را مجموعه همسایه‌های رئوس S می‌نامیم).

اثبات لازم‌بودن این قضیه تا حدود زیادی بدیهی بوده و اثبات کافی بودن آن مقداری پیچیده و از راههای مختلفی صورت می‌گیرد.

یکی از این راههای استقراء روی می‌باشد که ما به سبب طولانی‌بودن آن در اینجا شرح نمی‌دهیم.

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

مثال: شایان و فراز برروی جایگشت 1 تا n بازی زیر را انجام می‌دهند.

ابتدا جایگشت دلخواهی را روی تخته می نویسد سپس شایان از روی این جایگشت با استفاده از عمل زیر جایگشت را می سازد که تاکنون روی تخته سیاه نوشته نشده و آنرا روی تخته می‌نویسد.

حرکت) در هر عمل شخصی که نوبتش است دو عدد j,I را انتخاب کرده و جای اعداد مکان i و مکان j را با هم عوض می‌کند.

پس از شایان فراز نیز با استفاده از همین قانونها حرکت انجام می‌دهد شخصی که در نوبت خویش نتواند بازی کند بازنده است.

ثابت کنید شایان استراتژی برد دارد.

شاید در نگاه اول این مسأله مسأله‌ای سخت به نظر برسد ولی کافیست برای این مسأله گراف زیر را مدلسازی کنیم: به هر جایگشت یک رأس نسبت داده و د و رأس را به هم وصل کنیم اگر با استفاده از حرکت بالا قابل تبدیل به هم باشند با کمی دقت متوجه می‌شویم که این گراف یک جورسازی کامل دارد ( یعنی جورسازی که اندازه آن است و n تعداد رأسها می‌باشد) حال شایان کافیست با هر حرکت و زاویه رأس که با مکان فعلی فراز جور شده‌ برود درنتیجه شایان همواره یک حرکت برای رفتن دارد وشایان هیچگاه نمی‌بازد و چون بازی پایان دارد پس شایان برنده بازی می‌باشد.

چند مقاله از جورسازی ( منبع کتاب D.west ) 1- فرض کنید گردایه‌ای از زیر مجموعه‌های یک مجموعه Y باشد یک دستگاه از نماینده‌های متمایز (SDR) برای A مجموعه‌ای از عناصر متمایز در Y است بطوریکه ثابت کنید A دارای یک SDR است اگر و فقط اگر به ازای هر داشته باشیم مسأله بعدی یک مسأله مشکل تقریباً پیچیده‌ای مارکوس – ری و فلوید می‌باشد.

2- در یک جزیره خالص n زوج متأهل، که هر زوج متشکل از یک شکارچی یک شکارچی و یک کشاورز است.

وزارت شکار جزیره را به ناحیه n ناحیه شکار باندازه برابر تقسیم می‌کند.وزارت ازدواج تأکید می‌کند که ناحیه ازدواج و ناحیه کشاورزی واگذار شده به هر زوج باید با هم تداخل داشته باشند در کمال شگفتی این امکان پذیر است.

وزارت مذهب آن را یک معجزه اعلام می‌کند ثابت کنید که این یک معجزه نیست به این ترتیب که نشان دهید ناحیه‌ها را همواره می‌توان چنان جور کرد که ناحیه‌های هر زوج در مساحتی به اندازه حداقل مشترک باشند در حالیکه هر ناحیه مساحت 1 داشته باشند همچنینن ثابت کنید هیچ مساحت بزرگتری را نمی‌توان تضمین کرد.

در آخر این مقاله نیز چند مسأله‌ای قشنگ را از ترکیبات و گراف ارائه می‌دهیم.

1- صفحه 6×6 را با استفاده از موزائیک‌های 2×1 و 1×2 پوشاندیم ثابت کنید خطی افقی یا عمودی در این جدول وجود دارد که بطوریکه هیچ موازئیکی را قطع نمی‌کند.

2- 17 نفر از سه کشور مختلف گردهم آمدند و هر دو نفری هم تنها با استفاده از یکی از 3 زبان می‌توانند با هم ارتباط برقرار کنند.

ثابت کنید3 نفر وجود دارند که دوبه‌دو با استفاده از یک زبان با هم صحبت می‌کنند.

3- در یک گراف جهت‌دار رأسی با 4n یال ثابت کنید که یک دور معکوس در این گراف وجود دارد یک دور معکوس دوری است که مرتب جهت یالهای آن عوض می‌شود مثل: 4- یک جدولی n ×m را که با 0و 1 پوشاندیم را ستون متعادل می‌نامیم اگر هر دو ستونی که کنار هم می‌گذاریم دارای تعداد برابری 00و 01و 10و 11 باشد مثلاً یک جدول 5× 4 را در شکل زیر می‌بینیم.

الف) ثابت کنید برای هر K جدول ستون متعادل وجود دارد.

ب) می‌دانیم هیچ جدول ستون متعادل وجود ندارد با استفاده از این مطلب ثابت کنید هیچ جدول نیز و جود ندارد.

بسم الله الرحمن الرحیم «سازمان ملی پرورش استعدادهای درخشان» «مدرسه شهید سلطانی» «کرج» ترکیبیات و نظریه گراف دبیر : آقای توکلی ارائه دهندگان : فراز بیگلری شایان احسانی بهار 1384