تحقیق ترکیبات و نظریه گراف (3)

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

فرمت فایل word و قابل ویرایش و پرینت

تعداد صفحات: 27

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

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

1-ترکیبات:

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

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

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

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

احتمالاً اگر شخص آشنایی با ترکیبات نداشته باشد می گوید آری و سعی می کند با کوشش و

خطا اتاق را فرش کند ولی این کار شدنی نیست؟ ! و اثبات جالبی نیز دارد.

اثبات: جدول را بصورت شطرنجی رنگ می کنیم مانند شکل زیر:

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

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

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

(راهنمایی: ثابت کنید حتی سطر اول جدول را هم نمی توان پوشاند)

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

3-یک شبکه ی n*m از نقاط داریم یک مسیر فراگیر مسیری است که از خانه ی بالا سمت چپ

چطور دانلود کنم؟