شنبه 5 شهریور 1390
نوع مطلب :
بازی مكعب های رنگی با چهار مکعب انجام می گیرد.ابتدا وجه های مکعب هارا رنگ می کنیم.دررنگ آمیزی وجه های هر مکعب، تمام رنگ های قرمز(R)،سفید(w)،آبی(B)،زرد(Y)،به کار رفته اند.مامی توانیم این چهارمکعب را به صورت های مختلفی رنگ آمیزی کنیم،که در این جا برای نمونه، شکل 1 را آورده ایم .
هدف این بازی، چیدن این مکعب ها در یک ستون است به طوری که در هر طرف این ستون، هر چهار رنگ(مختلف)دیده شوند. به روش های مختلف می توان این مكعب ها را روی هم چید، با این وجود ممكن است حتی یك جواب هم نداشته باشیم .
قبل از حل ،شما را با چند مفهوم ساده ی نظریه ی گراف آشنا می کنیم.
تعریف گراف: یک گراف شامل یک مجموعه ی V از راس هااست که با یک مجموعه ی E متشکل از زیر مجموعه های 2 عضوی V که یال نامیده می شوند،جفت شده اند.
مثال:
{ V = { a,b,c,d
{{ E ={{a,b},{a,d},{d,c},{c,b},{b,d
واصطلاحا" می گوییم یال های {a,b}و {a,d}از راس a خارج (یا به آن وارد)شده اند.
تعریف طوقه:یالی كه از راسa به خودش رسم می شود را یک طوقه می نامند و با {a} نمایش می دهند .
تعریف زیر گراف:زیر گراف، گراف G ،گرافی است که مجموعه ی راس ها ویال هایش،زیر مجموعه ی راس ها ویال های گراف G باشد.
حال به حل مساله می پردازیم.
در جریان حل این مساله ، گراف ما را یاری می کند که وضعیت را بهتر مجسم کنیم.در شکل 2 گرافی با چهار راس R,W,B,Y داریم.برای کشیدن گراف مربوطه،در هر مکعب هر سه جفت وجه روبه روی هم را بررسی می کنیم.مثلا" در مکعب(1)دو وجه روبه روی هم زرد وآبی هستند.پس یالی بین راس Y و راس B رسم می کنیم و آن را با (1) (که نشان گر مکعب 1 است)نشان می دهیم.دو یال دیگری که در این گراف با (1) نشان شده اند،متناظر دو وجه سفید و زرد و دو وجه قرمز وسفیدمکعب 1 هستند که روبروی هم می باشند. همین کار را برای مکعب های دیگر نیز انجام داده ایم وبه گراف شکل (2) رسیده ایم.برای طوقه ها نیز به همین روش،مثلا" طوقه ای که در راس B با 3 نشان گذاری شده است،دو وجه آبی روبه روی هم رادر مکعب3 نشان می دهد. این گراف 12 یال دارد و این یال ها به 4دسته ی3تایی تقسیم می شوند که یال های هر دسته با شماره ی یکی از مکعب ها،نشان گذاری شده است.در هر راس، تعداد یال هایی که از آن راس خارج یا به آن واردمی شوند،برابر است باتعداد وجه هایی از هر چهار مکعب که به آن رنگ هستند.(هر طوقه را دوبار می شماریم.)بنابراین گراف شکل (2)به ما می گوید که در این چهار مکعب،5 وجه قرمز،7 وجه سفید،6 وجه آبی و 6 وجه زرد داریم.
چهار مکعب را كه در یک ستون، روی هم قرار گرفته اند،درنظر می گیریم و طرفین روبه روی هم در این ستون را بررسی می کنیم. برای دو طرف روبه روی هم در این ستون، یک زیر گراف از این گراف را متناظر می کنیم،با این خاصیت که :این زیر گراف دارای چهار راس(رنگ) و چهار یال بوده و هر نشان یک بار به کار رود.(در این زیر گراف، متناظر با هر راس ، دو یال قرار دارد.)حال اگر بتوانیم نتیجه ی مشابهی را برای دو طرف دیگر این ستون به دست آوریم حل مساله تمام است.برای این کار به زیر گراف دوم، مشابه شکل (3)الف،نیاز داریم که شامل هیچ یالی از شکل (3)الف نباشد. مطابق شکل (3)ب،چنین زیر گرافی وجود دارد.
شکل(4)،نشان می دهد که چگونه می توان این مکعب ها را با توجه به اطلاعات ارائه شده به وسیله ی زیر گراف های شکل (3) مرتب کنیم.
به طور کلی به ازای هر چهار مکعب دلخواه، یک گراف نشان دار می سازیم و می کوشیم که در آن دو زیر گراف چنان بیابیم که:
1- هر زیر گراف شامل هر 4 راس باشد و به ازای هر نشان به کار رفته، یک یال ،یعنی روی هم 4 یال داشته باشد.
2- در هر زیر گراف،هر راس دقیقا"روی دو یال قرار داشته باشد.(طوقه دو بار به حساب می آید.)
3- هیچ یال نشان دار گراف،نشان دار هم زمان در هر دو زیر گراف نباشد.
منبع :كتاب ریاضیات گسسته و تركیبیاتی
نویسنده : رالف .پ.گریمالدی
مترجم: بیژن شمس،محمد علی رضوانی
تبلیغات 
توپ قرمز پلاستیكی
" چیست؟
" 
