بازی مکعب ها در گرافها

[Borna66]

بازی مكعب هاي رنگي با چهار مکعب انجام می گیرد.ابتدا وجه های مکعب هارا رنگ می کنیم.دررنگ آمیزی وجه های هر مکعب، تمام رنگ های قرمز(R)،سفید(w)،آبی(B)،زرد(Y)،ب ه کار رفته اند.مامی توانیم این چهارمکعب را به صورت های مختلفی رنگ آمیزی کنیم،که در این جا برای نمونه، شکل 1 را آورده ايم .

http://pnu-club.com/imported/2009/04/1807.jpg
هدف این بازی، چیدن این مکعب ها در یک ستون است به طوری که در هر طرف این ستون، هر چهار رنگ(مختلف)دیده شوند. به روش هاي مختلف مي توان اين مكعب ها را روي هم چيد، با اين وجود ممكن است حتي يك جواب هم نداشته باشيم .
قبل از حل ،شما را با چند مفهوم ساده ی نظریه ي گراف آشنا می کنیم.
تعریف گراف: یک گراف شامل یک مجموعه ي V از راس هااست که با یک مجموعه ی E متشکل از زیر مجموعه های 2 عضوی V که یال نامیده می شوند،جفت شده اند.
مثال:
{ V = { a,b,c,d
{{ E ={{a,b},{a,d},{d,c},{c,b},{b,d


http://pnu-club.com/imported/2009/04/151.gif
واصطلاحا" می گوییم یال های {a,b}و {a,d}از راس a خارج (یا به آن وارد)شده اند.
تعریف طوقه:يالي كه از راسa به خودش رسم مي شود را یک طوقه می نامند و با {a} نمايش مي دهند .

http://pnu-club.com/imported/2009/04/1808.jpg
تعریف زیر گراف:زیر گراف، گراف 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 وجه زرد داریم.

http://pnu-club.com/imported/2009/04/1809.jpg
چهار مکعب را كه در یک ستون، روی هم قرار گرفته اند،درنظر مي گيريم و طرفين روبه روی هم در این ستون را بررسی می کنیم. برای دو طرف روبه روي هم در این ستون، یک زیر گراف از این گراف را متناظر می کنیم،با این خاصیت که :اين زير گراف داراي چهار راس(رنگ) و چهار يال بوده و هر نشان یک بار به کار رود.(در اين زير گراف، متناظر با هر راس ، دو يال قرار دارد.)حال اگر بتوانیم نتیجه ی مشابهی را برای دو طرف دیگر این ستون به دست آوریم حل مساله تمام است.برای این کار به زیر گراف دوم، مشابه شکل (3)الف،نیاز داریم که شامل هیچ یالی از شکل (3)الف نباشد. مطابق شکل (3)ب،چنین زیر گرافی وجود دارد.

http://pnu-club.com/imported/2009/04/1810.jpg
شکل(4)،نشان می دهد که چگونه می توان این مکعب ها را با توجه به اطلاعات ارائه شده به وسیله ی زیر گراف های شکل (3) مرتب کنیم.

http://pnu-club.com/imported/2009/04/1811.jpg
به طور کلی به ازای هر چهار مکعب دلخواه، یک گراف نشان دار می سازیم و می کوشیم که در آن دو زیر گراف چنان بیابیم که:
1- هر زیر گراف شامل هر 4 راس باشد و به ازای هر نشان به کار رفته، یک یال ،یعنی روی هم 4 یال داشته باشد.
2- در هر زیر گراف،هر راس دقیقا"روی دو یال قرار داشته باشد.(طوقه دو بار به حساب می آید.)
3- هیچ یال نشان دار گراف،نشان دار هم زمان در هر دو زیر گراف نباشد.