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

یک رنگامیزی گراف پترسن به کمک 3 رنگ (کمترین تعداد رنگ ممکن).

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

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

تاریخچه

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

اولین نتیجه‌های بدست آمده در مورد رنگامیزی گراف از تلاش‌های انجام شده بر روی گراف‌های مسطح برای حل مساله رنگامیزی نقشه بدست آمد. در آن زمان Francis Guthrie ادعا کرد که رنگامیزی نقشه ایالت‌های مختلف بریتانیا روی نقشه، به طوری که هیچ دو ایالت مجاوری همرنگ نشوند، می تواند با 4 رنگ انجام شود( شرط کافی ). برادر Guthrie این مساله را برای معلم ریاضی خود Augustus de Morgan، در University College فرستاد. de Morgan، این مساله را در سال 1825 میلادی در نامه‌ای که به William Hamilton نوشت مطرح کرد. در سال 1879 Arthur Cayley این مساله را در انجمن ریاضی شهر London مطرح کرد. در همان سال Alfred Kempe، نتایج بدست آمده را منتشر کرد و برای یک دهه تصور می‌شد این مساله حل‌شده است. برای تلاش‌های Kempe در این زمینه او به عنوان یکی از اعضای جامعه سلطتنتی و بعدها به عنوان ریاست انجمن ریاضی شهر London انتخاب شد.

در سال Heawood، ادعا کرد که استدلال Kempe اشتباه بوده است و اثبات این مساله را برای 5 رنگ منتشر کرد. در قرن معاصر او تلاش‌های زیادی برای اثبات روش‌های رنگامیزی نقشه با تعداد 4 رنگ صورت گرفت که در نهایت در سال 1976 توسط Kenneth Appel وWolfgang Haken این مساله به کمک ایده‌های خود Heawood و Kempe انجام شد که در آن زمان به دلیل استفاده از کامپیوتر برای اثبات مساله، شدیدا مورد قبول واقع نشد.

رنگامیزی گراف از اوایل دهه 70 به عنوان یک مساله الگوریتمی مورد بررسی قرار گرفته است، به طوری که جزء یکی از 21 مساله 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}$
گراف دوری 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 ترکیب شیمیایی بفروشد ، فرض کنیدc₁, c₂,…, c₂₅}=v} مجموعۀ رأس ها باشد .به ازای 1≤i≤y≤25 یال{c_i, c_j}را ، اگر ضروری است که c_i و c_j در بخش های جدا از هم انبار شوند ،رسم می کنیم . این عمل ، گراف بی سوی (G=(V,E را به ما می دهد . اینک مفهوم زیر را معرفی می کنیم .

تعریف : اگر(G=(V,E گرافی بی سو باشد ، یک رنگ آمیزی خاص G وقتی صورت می گیرد که رأس های G را به قسمی رنگ زنیم که اگر {a , b} یالی از G باشد ، آن گاه a و b رنگ های مختلف داشته باشند . (بنابراین رأس های مجاور رنگ های محتلف دارند) مینیمم تعداد رنگ های لازم برای رنگ کردن G را عدد فامی G می نامند و با(χ(G نشان می دهند . اگر به یاری جین دربارۀ مشکل انبار برگردیم ، متوجه می شویم که تعداد بخش های ذخیره سازی که جان باید بسازد برابر با (χ(G ی گرافی است که با c₁, c₂,…, c₂₅}=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 ، با K₄ یکریخت است ، به قسمی که(χ(G)≥χ(K₄ . بنابراین ، اگر بتوانیم راهی برای رنگ آمیزی خاص رأسهای 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,λ)=λⁿ .

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

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

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

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

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

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

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

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

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

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

از مثال 2 (ج) ،P(G_e,λ)=λ(λ-1)³ . با G_e '= K₃ داریم P(^'G_e , λ)=λ⁽³ . بنابراین P(G,λ) = λ(λ-1)³-λ(λ-1)(λ-2) = λ(λ-1)[(λ-1)²-(λ-2)] = λ(λ-1)[λ²-3λ+3]=λ⁴-4λ³+6λ²-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

ویکی انگلیسی