رنگ‌آمیزی گراف

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
یک رنگامیزی گراف پترسن به کمک 3 رنگ (کمترین تعداد رنگ ممکن).

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

رنگامیزی گراف کاربردهای زیادی در زمینه‌های عملی و تئوری گوناگون دارد. علاوه بر مساله‌های کلاسیک تعریف شده در این زمینه، با در نظر گرفتن محدودیت‌های مختلفی روی نوع گرافها، روی روش رنگامیزی و حتی تعداد و رنگ عناصر گراف مساله‌های متنوعی با کاربردهای وسیع در صنعت و علوم تعریف و حل می‌شود. با وجود اینکه این مساله از نظر علمی هنوز در حال رشد و بررسی بیشتر می‌باشد، با ظهور جدول سودوکو در بین عموم مردم شناخته و مشهور شده است.

تاریخچه[ویرایش]

یک رنگامیزی ۴ رنگه نقشه ایالات متحده ( بدون در نظر گرفتن آبها، کشورهای همسایه و متن نام ایالت‌ها).

اولین نتیجه‌های بدست آمده در مورد رنگامیزی گراف از تلاش‌های انجام شده بر روی گراف‌های مسطح برای حل مساله رنگامیزی نقشه بدست آمد. در آن زمان فرانسیس گوتری ادعا کرد که رنگامیزی نقشه ایالت‌های مختلف بریتانیا روی نقشه، به طوری که هیچ دو ایالت مجاوری همرنگ نشوند، می تواند با ۴ رنگ انجام شود( شرط کافی ). برادر گوتری این مساله را برای معلم ریاضی خود آگوستوس دو مورگان، در کالج دانشگاهی فرستاد. دو مورگان، این مساله را در سال ۱۸۲۵ میلادی در نامه‌ای که به ویلیام همیلتون نوشت مطرح کرد. در سال ۱۸۷۹ آرتور کیلی این مساله را در انجمن ریاضی شهر لندن مطرح کرد. در همان سال آلفرد کمپ، نتایج بدست آمده را منتشر کرد و برای یک دهه تصور می‌شد این مساله حل‌شده است. برای تلاش‌های کمپ در این زمینه او به عنوان یکی از اعضای جامعه سلطتنتی و بعدها به عنوان ریاست انجمن ریاضی شهر لندن انتخاب شد.

در سال Heawood، ادعا کرد که استدلال کمپ اشتباه بوده است و اثبات این مساله را برای 5 رنگ منتشر کرد. در قرن معاصر او تلاش‌های زیادی برای اثبات روش‌های رنگامیزی نقشه با تعداد ۴ رنگ صورت گرفت که در نهایت در سال ۱۹۷۶ توسط Kenneth Appel وWolfgang Haken این مساله به کمک ایده‌های خود Heawood و کمپ انجام شد که در آن زمان به دلیل استفاده از کامپیوتر برای اثبات مساله، شدیداً مورد قبول واقع نشد.

رنگامیزی گراف از اوایل دهه ۷۰ به عنوان یک مساله الگوریتمی مورد بررسی قرار گرفته است، به طوری که جزء یکی از ۲۱ مساله NP-Complete که Karp معرفی کرد قرار گرفته.

واژه‌ها و اصطلاحات[ویرایش]

این گراف به 12 روش می‌تواند رنگامیزی 3 رنگه شود.

رنگامیزی راسی[ویرایش]

معمولاً تا زمانی که ذکر نشده است، منظور از رنگامیزی گراف یک رنگامیزی مناسب راس‌های یک گراف است. یا به عبارتی یک برچسب گزاری راس‌های گراف است به شکلی که هیچ دو راسی که یک یال انها را متصل می‌کنند همرنگ نباشند. از انجایی که یک طوقه نمی‌تواند این ویژگی را داشته باشد، این گراف‌ها باید بدون طوقه باشند.

استفاده از رنگ‌ها برای این رنگامیزی گراف به استفاده آنها در رنگامیزی نقشه بازمی‌گردد. چرا که از تعداد رنگ‌های کمی برای این منظور استفاده می‌کنیم. به طور طبیعی هر رنگ را متناظر یکی از اعداد طبیعی {...و3و2و1} در نظر می‌گیریم.

به رنگامیزی که در آن حداکثر از k رنگ استفاده می‌شود، رنگ-امیزی k تایی گفته می‌شود. به کوچکترین عددی که می‌توان راس‌های یک گراف را رنگامیزی کرد را با (X(G نشان می‌دهیم. گرافی که می‌توان آن را با یک رنگامیزی k تایی رنگ کرد، گراف k رنگ شونده نامیده می‌شود. مجموعه‌ای از راس‌های یک گراف که همرنگ رنگ شده‌اند یک کلاس رنگی را تشکیل می‌دهند. هر کلاس رنگی یک مجموعه مستقل را تشکیل می‌دهد.

تمامی گراف‌های غیرایزومرفیک از درجه 3 و تعداد روش‌های رنگامیزی آنها.

چندجمله‌ای رنگی[ویرایش]

چند جمله‌ای های رنگی به تعداد روش‌های رنگ‌امیزی یک گراف اطلاق می‌شود که تعداد رنگ‌های مورد استفاده از تعداد مشخصی بیشتر نشود. برای مثال گراف شکی سمت چپ با 12 روش با 3 رنگ، رنگامیزی می‌شود. رنگامیزی آن با 2 رنگ غیر ممکن است. با 4 رنگ این کار را می‌توان با 72 = 4.12 + 24 روش رنگ کرد( اگر حتماً از هر 4 رنگ استفاده کنیم 24 = !4 روش ممکن است.). برای گراف فوق جدول تعداد حالت‌های ممکن به صورت زیر خواهد بود.

تعداد رنگ‌ها 1 2 3 4
تعداد حالت‌های رنگامیزی 0 0 12 72

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

(P(G, t) = t(t − 1)2(t − 2

پس برای این گراف P(G، 4) = 72 روش خواهیم داشت.

به توابع چندجمله‌ای رنگی برای گراف‌های خاص زیر توجه کنید:

چندجمله‌ای رنگی برای گراف‌های خاص
مثلثی K3 t(t-1)(t-2)
گراف کامل Kn t(t-1)(t-2) \cdots (t-(n-1))
درخت با n راس t(t-1)^{n-1}
گراف مسیر pn t(t-1)^{n-1}
گراف دوری Cn (t-1)^n+(-1)^n(t-1)
گراف پترسن t(t-1)(t-2)(t^7-12t^6+67t^5-230t^4+529t^3-814t^2+775t-352)

رنگامیزی یالی[ویرایش]

رنگامیزی یالی یک گراف به نوعی از رنگامیزی گراف اطلاق می‌شود که در آن یال‌ها طوری رنگ می‌شوند که هیج راسی وجود نداشته باشد که مرتبط با 2 یال همرنگ باشد. یک رنگامیزی یال‌های یک گراف با k رنگ یک رنگامیزی یالی k-رنگی نام دارد که برابر با تعداد تعداد حالت‌های تطابق تایی متناظر می‌باشد.

کاربردها[ویرایش]

مساله چندجمله ای های فامی[ویرایش]

در شرکت شیمیایی J&J ، جین متصدی انبار کردن ترکیب های شیمیایی در انبار شرکت است . چون بعضی از انواع ترکیب ها ( نظیر اسید و بازها ) نباید در مجاورت هم نگهداری شوند ، تصمیم می گیرد که از همکارش جان بخواهد که انبار را به ناحیه های جدا از هم ذخیره سازی تقسیم کند که بتوان مواد شیمیایی ناسازگار با هم را در بخش های جدا از یکدیگر انبار کرد . چطور می تواند تعداد بخش های ذخیره سازی را که همکارش باید بسازد معین کند ؟ اگر شرکتی 25 ترکیب شیمیایی بفروشد ، فرض کنیدc1، c2،…، c25}=v} مجموعۀ رأس ها باشد .به ازای 1≤i≤y≤25 یال{ci، cj}را ، اگر ضروری است که ci و cj در بخش های جدا از هم انبار شوند ،رسم می کنیم . این عمل ، گراف بی سوی (G=(V،E را به ما می دهد . اینک مفهوم زیر را معرفی می کنیم .

تعریف : اگر(G=(V،E گرافی بی سو باشد ، یک رنگ آمیزی خاص G وقتی صورت می گیرد که رأس های G را به قسمی رنگ زنیم که اگر {a ، b} یالی از G باشد ، آن گاه a و b رنگ های مختلف داشته باشند . (بنابراین رأس های مجاور رنگ های محتلف دارند) مینیمم تعداد رنگ های لازم برای رنگ کردن G را عدد فامی G می نامند و با(χ(G نشان می دهند . اگر به یاری جین دربارۀ مشکل انبار برگردیم ، متوجه می شویم که تعداد بخش های ذخیره سازی که جان باید بسازد برابر با (χ(G ی گرافی است که با c1، c2،…، c25}=v}ساختیم . امّا چگونه (χ(G را حساب کنیم؟ قبل از انجام هرکاری دربارۀ چگونگی تعیین عدد فامی گراف ، به مطلب وابستۀ زیر توجه می کنیم .

حدود 1850 ، فرانسیس گاتری (1831-1899) بعد از نشان دادن چگونگی رنگ آمیزی استان های نقشۀ انگلیس تنها با چهار رنگ ، به مسألۀ کلی علاقه‌مند شد . اندکی بعد از آن ، « مسئله چهار رنگ » را به برادر کوچکش فردریک نشان داد . در آن زمان فردریک گاتری (1833-1866) دانشجوی اوگاستس دمورگن (1806-1871) بود که مسأله را (در 1852) با ویلیام همیلتن (1805-1865) در میان گذاشت . این مسئله مورد توجه همیلتن قرار نگرفت و حدود 25 سال مسکوت ماند . بعداً در 1878 ، جامعۀ علمی از طریق اطلاعیۀ آرثر کیلی (1821-1895) در گردهمایی انجمن ریاضی لندن از مسئله آگاه شد . کیلی در 1879 مسئله را در اولین مجلۀ گزارش انجمن سلطنتی جغرافیا بیان کرد . مدت کوتاهی بعد از آن ، سرآلفرد کمپ (1849-1922) ، ریاضیدان انگلیسی ، برهانی پیدا کرد که بیش از یک دهه غیر قابل تردید باقی‌ماند . بعداً در 1890 پرسی جان هیوود (1861-1955) ، ریاضیدان دیگر انگلیسی در کار کمپ خطایی یافت . مسئله تا سال 1976 حل نشده ماند ، تا اینکه سرانجام کنت آپل و ولفگانک هیکن آن را حل کردند . در برهان آنها تحلیل کامپیوتری بسیار پیچیده‌ای از پیکر بندی های ( کاهش پذیر ) 1936 به کار رفته است .

گر چه تنها چهار رنگ برای رنگ آمیزی خاص ناحیه های یک نقشۀ هامنی مورد نیاز است ، ولی برای رنگ آمیزی خاص رأس های گراف های غیر هامنی بیش از چهار رنگ لازم است . با چند مثال کوچک شروع می کنیم . در این صورت راهی برای تعیین (χ(Gاز زیر گراف های کوچکتر G خواهیم یافت . آنچه را که چند جمله ای فامی G می نامند نیز به دست خواهیم آورد و چگونگی استفاده از آن را در محاسبه (χ(G خواهیم دید .

مثال 1 : برای گراف G در شکل 1 ، از رأس a شروع می کنیم و سپس در هر رأس ، عدد فامی لازم برای رنگ آمیزی رأس های G را که برای آنها در نظر گرفته‌ایم می نویسیم . وقتی به رأس b می رویم ، عدد 2 نیاز ما به رنگ دوم است و اگر به صورت الفبایی تا f پیش برویم متوجه می شویم که برای رنگ آمیزی خاص {a،b،c،d،e،f} به دو رنگ نیاز داریم . برای رأُس g ، رنگ سومی لازم است ؛ این رنگ سوم را می توان برای رأس h هم به کار برد ، زیرا {g ، h} یالی از G نیست . پس χ(G)=3 .

مثال 2 : الف ) برای هر χ(K n )=n ،n≥1.

ب ) عدد فامی گراف شکل 2 (هرشل) برابر 2 است .

ج )اگر G گراف پترسن باشد آن گاه χ(G)=3 .

مثال 3 : فرض کنید G گرافی است که در شکل 3 نشان داده‌ایم . برای {U={b،f،h،i ، زیر گراف القایی (U) از G ، با K4 یکریخت است ، به قسمی که(χ(G)≥χ(K4 . بنابراین ، اگر بتوانیم راهی برای رنگ آمیزی خاص رأسهای G با چهار رنگ تعیین کنیم ، آن گاه می دانیم که χ(G)=4 . یک راه انجام این کار ، این است که رأس های e ،f ، g را با رنگ آبی ، رأس های b و j را با رنگ های قرمز ، رأس های c و h را با رنگ سفید و رأسهای a ، d ، i را با رنگ سبز رنگ بزنیم .

اینک به روشی برای تعیین (χ(G برمی گردیم . آنچه مطرح می کنیم از بسط مقالۀ تحقیقی [22] ، اثر رید گرفته شده است .

فرض کنید G گرافی بی سو ست و λ عدد صحیح مثبت معرّف تعداد رنگ های است که برای رنگ آمیزی خاص رأس های G موجودند . هدف ما یافتن چند جمله ای (P(G،λ برحسب متغیر λ است که بیان می کند به چند راه مختلف رأس های G را ، با استفاده از حداکثر λ رنگ ، رنگ کنیم . در سراسر این بحث ، رأس های گراف بی سوی (G=(V،E به وسیله برچسب ها از هم متمایزند . در نتیجه دو رنگ آمیزی خاص چنین گرافی به مفهوم زیر متمایز در نطر گرفته می شوند : رنگ آمیزی خاص (رأس های G) که حداکثر λ رنگ به کار می برد تابعی مانند f با حوزۀ V و حوزۀ تمام {3،2،1،…،λ} است ، که در آن ، برای رأس های مجاور f(u)≠f(v)،u،v∈V . لذا تفاوت رنگ آمیزی خاص از متفاوت بودن این تابع ها معلوم می شود .

مثال 4 : الف ) اگر (G=(V،E با V|=n|و E=∅ ، آن گاه G عبارت از n نقطۀ تنهاست ، و بنابر اصل ضرب P(G،λ)=λn .

ب) اگر G=Kn ، آن گاه حداقل باید n رنگ موجود باشد تا G را به طور خاص رنگ بزنیم . در اینجا ، بنابر اصل ضرب ، (P(G،λ)=λ(λ-1)(λ-2)…(λ-n+1 ، که آن را با λ(n نشان می دهیم . به ازای P(G،λ)=0 ، λ<n و راهی برای رنگ آمیزی خاص Kn وجود ندارد . وقتی (λ=n=χ(G، برای اولین بار P(G،λ)>0

ج) برای هر مسیر در شکل 4 تعداد انتخاب ها در هر رأس متوالی را در نظر می گیریم . اگر به صورت الفبایی پیش برویم ، در میابیم که P(G1،λ)=λ(λ-1)3 و P(G2،λ)=λ(λ-1)4 . چون (P(G1،1)=0=P(G2،1 ، ولی (χ(G1 )=χ(G2 )=2 ، P(G1،2)=2=P(G2،2 ، اگر پنج رنگ موجود باشند ، می توانیم به طور خاص G1 را به320 راه رنگ بزنیم ؛ G2 را نیز می توان به همین طریق به1280 راه رنگ کرد .

(به طور کلی :اگر G مسیری با n رأس باشد ، آن گاهP(G،λ)=λ(λ-1)n-1)

د ) اگر G از مؤلفه های C1،C2،…،Ck ساخته شده باشد ، آن گاه باز بنابر اصل ضرب ، نتیجه می شود که (P(G،λ)=P(C1،λ).P(C2،λ)…P(Ck،λ .

به عنوان نتیجه ای از مثال 4 (د) توجه خود را بر گراف های همبند متمرکز می کنیم . در بسیاری از موارد در ریاضیات گسسته ، برای حلّ مسائل با حالت های زیاد روش هایی که به کار رفته‌اند ، تفکیک این حالت ها به دو یا چند حالت کمتر است . ما نیز همین روش را برای حل مسأله به کار می بریم . برای انجام این کار به مفاهیم و نماد گذاری زیر نیاز داریم . فرض کنید(G=(V،E گرافی بی سو باشد . برای e={a،b}∈E فرض می کنیم Ge معرف زیر گراف G حاصل از حذف e از G ، بدون برداشتن رأس های a و b است ؛ یعنی به صورت Ge=G-e می باشد . از Ge ، زیرا گراف دوّمی از G با اتصال رأس های a و b به دست می آید . این زیر گراف دوم را با 'Ge نشان می دهیم .

مثال 5 : شکل5 ، Ge و'Ge را برای گراف G با یالی که با e مشخص شده است نشان می دهد . توجه کنید که چگونه اتصال a و b در 'Ge از اتصال دو جفت از یال های {d،b} ، {d،a}، {a،c} ، {b،c} نتیجه می شود .

با استفاده از این زیر گراف های خاص ، اینک به قضیۀ اصلی می رسیم :

قضیه 1 ( قضیۀ تجزیه برای چند جمله ای های فامی ) : اگر(G=(V،E گرافی همبند باشد و e∈E ، آن گاه: (P(Ge ، λ)=P(G ، λ)+P('Ge ، λ

برهان : فرض کنید{e={a،b . تعداد راه های رنگ آمیزی خاص رأسهای Ge با (حداکثر) λ رنگ برابر(P(Ge ، λ است . آن رنگ آمیزیهایی که در آنها a و b دارای رنگ های متفاوت اند رنگ آمیزی های خاص G هستند . آن رنگ آمیزیهای Ge که رنگ آمیزیهای خاص G نیستند .وقتی رخ می دهند که a و b یک رنگ داشته باشند . امّا هر یک از این رنگ آمیزی ها متناظر با یک رنگ آمیزی خاص برای 'Ge است . این افراز(P(Ge ، λ رنگ آمیزی به دو زیر مجموعۀ مجزای مشخص شده ، از معادلۀ (P(Ge ، λ)=P(G ، λ)+P('Ge ، λ نتیجه می شود .

مثال 6 : محاسبات زیر ،(P(G،λ را برای G که دوری به درازای 4 است ،(شکل6) به دست می دهد .

از مثال 2 (ج) ،P(Ge،λ)=λ(λ-1)3 . با Ge '= K3 داریم P('Ge ، λ)=λ(3 . بنابراین P(G،λ) = λ(λ-1)3-λ(λ-1)(λ-2) = λ(λ-1)[(λ-1)2-(λ-2)] = λ(λ-1)[λ2-3λ+3]=λ4-4λ3+6λ2-3λ

چون P(G،1)=0 در حالی که P(G،2)=2>0 ، داریم χ(G)=2.

قضیه 2 : برای هر گراف G ، جملۀ ثابت در(P(G،λ برابر 0 است .

برهان : برای هر گراف G ، χ(G)>0 ، زیرا V≠ ∅ . اگر تعداد(P(G،λ دارای جملۀ ثابت a باشد ، آن گاه P(G،0)=a≠0 . این مطلب نتیجه می دهد که تعداد a راه برای رنگ کردن خاص G با 0 رنگ وجود دارد .

قضیه 3 : فرض کنید(G=(V،E با E|>0|. در این صورت مجموع ضریب ها در(P(G،λ برابر با 0 است .

برهان : چون E|≥1|، پس χ(G)≥2 . در نتیجه P(G،1)=0 برابر مجموع ضریب ها در(P(G،λ است .

منابع[ویرایش]

Cormen, T. H.; Leiserson, C. E.; Rivest, R. L. (1990), Introduction to Algorithms (1st ed.), The MIT Press

ویکی انگلیسی