تركيبات و نظريه‌ي گراف

در اين مقاله مي خواهيم به دو مبحث بزرگ از رياضيات گسسته با نامهاي تركيبات و نظريه‌ي گراف بپردازيم كه در اين دوران شاهد پيشرفت چشمگير آنها مي باشيم .
اين دو مبحث بدليل آنكه داراي كاربرد وسيعي در علم كامپيوتر و برنامه سازي هاي كامپيوتري مي‌باشند حائز اهميت فراوان مي باشند .
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 جدول ستون متعادل وجود دارد.
ب) مي‌دانيم هيچ جدول ستون متعادل وجود ندارد با استفاده از اين مطلب ثابت كنيد هيچ جدول نيز و جود ندارد.

فایل : 27 صفحه

فرمت : Word