موضوع مقاله: رنگ‌آمیزی گراف | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # رنگ‌آمیزی گراف | مقدمه: در نظریه گراف، رنگ‌آمیزی گراف یکی از حالت‌های خاص مسئله‌های برچسب‌گذاری گراف است. | ## بخش 1: رنگ‌آمیزی گراف | رویکرد کلی آن استفاده از نظیر کردن رنگهایی به یالها یا راس‌هاست که این رنگ‌آمیزی محدودیت خاصی را رعایت کند. در ساده‌ترین حالت، رنگ‌آمیزی‌ای مورد نظر است که در آن هیچ دو راس مجاوری هم رنگ نباشند (رنگ‌آمیزی راسها). علاوه بر مسئله‌های کلاسیک تعریف شده در این زمینه، با در نظر گرفتن محدودیت‌های مختلفی روی نوع گرافها، روی روش رنگ‌آمیزی و حتی تعداد و رنگ عناصر گراف مسئله‌های متنوعی با کاربردهای وسیع در صنعت و علوم تعریف و حل می‌شود. تاریخچه اولین نتیجه‌های بدست آمده در مورد رنگ‌آمیزی گراف از تلاش‌های انجام شده بر روی گراف‌های مسطح برای حل مسئله رنگ‌آمیزی نقشه بدست آمد. در آن زمان فرانسیس گوتری ادعا کرد که رنگ‌آمیزی نقشه ایالت‌های مختلف بریتانیا روی نقشه، به‌طوری‌که هیچ دو ایالت مجاوری همرنگ نشوند، می‌تواند با ۴ رنگ انجام شود (شرط کافی). برادر گوتری این مسئله را برای معلم ریاضی خود آگوستوس دو مورگان، در کالج دانشگاهی فرستاد. دو مورگان، این مسئله را در سال ۱۸۵۲ میلادی در نامه‌ای که به ویلیام همیلتون نوشت مطرح کرد. در همان سال آلفرد کمپ، نتایج بدست آمده را منتشر کرد و برای یک دهه تصور می‌شد این مسئله حل‌شده‌است. برای تلاش‌های کمپ در این زمینه او به عنوان یکی از اعضای جامعه سلطنتی و بعدها به عنوان ریاست انجمن ریاضی شهر لندن انتخاب شد. در سال1890 Heawood، ادعا کرد که استدلال کمپ اشتباه بوده‌است و اثبات این مسئله را برای ۵ رنگ منتشر کرد. رنگ‌آمیزی راسی معمولاً تا زمانی که ذکر نشده‌است، منظور از رنگ‌آمیزی گراف یک رنگ‌آمیزی مناسب رأس‌های یک گراف است. یا به عبارتی یک برچسب‌گذاری رأس‌های گراف است به شکلی که هیچ دو راسی که یک یال آن‌ها را متصل می‌کنند همرنگ نباشند. از آنجایی که یک طوقه نمی‌تواند این ویژگی را داشته باشد، این گراف‌ها باید بدون طوقه باشند. استفاده از رنگ‌ها برای این رنگ‌آمیزی گراف به استفاده آن‌ها در رنگ‌آمیزی نقشه بازمی‌گردد. به رنگ‌آمیزی که در آن حداکثر از k رنگ استفاده می‌شود، رنگ-امیزی k تایی گفته می‌شود. به کوچکترین عددی که می‌توان رأس‌های یک گراف را رنگ‌آمیزی کرد را با (X)G نشان می‌دهیم. گرافی که می‌توان آن را با یک رنگ‌آمیزی k تایی رنگ کرد، گراف k رنگ شونده نامیده می‌شود. مجموعه‌ای از رأس‌های یک گراف که همرنگ رنگ شده‌اند یک کلاس رنگی را تشکیل می‌دهند. | ## بخش 2: رنگ‌آمیزی گراف | چندجمله‌ای رنگی چندجمله‌ای‌های رنگی به تعداد روش‌های رنگ‌آمیزی یک گراف گفته می‌شود که تعداد رنگ‌های مورد استفاده از تعداد مشخصی بیشتر نشود. با ۴ رنگ این کار را می‌توان با ۷۲ = ۴×۱۲ + ۲۴ روش رنگ کرد (اگر حتماً از هر ۴ رنگ استفاده کنیم ۲۴ = !۴ روش ممکن است). تعداد رنگ‌ها ۱ ۲ ۳ ۴ …تعداد حالت‌های رنگ‌آمیزی ۰ ۰ ۱۲ ۷۲ … چندجمله‌ای رنگی تابعی است به صورت (P(G, t که تعداد حالت‌های رنگ‌آمیزی t-تایی گراف G را می‌شمارد. همان‌طور که از اسم ان مشخص است این تعداد یک چندجمله‌ای است که برای مثال فوق (P(G, t) = t(t − 1)2(t − ۲ پس برای این گراف P(G، ۴) = ۷۲ روش خواهیم داشت. به توابع چندجمله‌ای رنگی برای گراف‌های خاص زیر توجه کنید: +چندجمله‌ای رنگی برای گراف‌های خاص مثلثی K3 گراف کامل Kn درخت با n راس گراف مسیر pn گراف دوری Cn گراف پترسن رنگ‌آمیزی یالی رنگ‌آمیزی یالی یک گراف به نوعی از رنگ‌آمیزی گراف گفته می‌شود که در آن یال‌ها طوری رنگ می‌شوند که هیج راسی وجود نداشته باشد که مرتبط با ۲ یال همرنگ باشد. یک رنگ‌آمیزی یال‌های یک گراف با k رنگ یک رنگ‌آمیزی یالی k-رنگی نام دارد که برابر با تعداد تعداد حالت‌های تطابق تایی متناظر می‌باشد. کاربردها مسئله چندجمله ای‌های فامی در شرکت شیمیایی J&J، جین متصدی انبار کردن ترکیب‌های شیمیایی در انبار شرکت است. چون بعضی از انواع ترکیب‌ها (نظیر اسید و بازها) نباید در مجاورت هم نگهداری شوند، تصمیم می‌گیرد که از همکارش جان بخواهد که انبار را به ناحیه‌های جدا از هم ذخیره‌سازی تقسیم کند که بتوان مواد شیمیایی ناسازگار با هم را در بخش‌های جدا از یکدیگر انبار کرد. اگر شرکتی ۲۵ ترکیب شیمیایی بفروشد، فرض کنیدc1، c2، …، c25=v مجموعهٔ رأس‌ها باشد. تعریف: اگر(G=(V,E گرافی بی سو باشد، یک رنگ آمیزی خاص G وقتی صورت می‌گیرد که رأس‌های G را به قسمی رنگ زنیم که اگر a , b یالی از G باشد، آن گاه a و b رنگ‌های مختلف داشته باشند. (بنابراین رأس‌های مجاور رنگ‌های مختلف دارند) مینیمم تعداد رنگ‌های لازم برای رنگ کردن G را عدد فامی G می‌نامند و با(χ(G نشان می‌دهند. اگر به یاری جین دربارهٔ مشکل انبار برگردیم، متوجه می‌شویم که تعداد بخش‌های ذخیره‌سازی که جان باید بسازد برابر با (χ(G ی گرافی است که با c1، c2، …، c25=vساختیم. قبل از انجام هرکاری دربارهٔ چگونگی تعیین عدد فامی گراف، به مطلب وابستهٔ زیر توجه می‌کنیم. حدود ۱۸۵۰، فرانسیس گاتری (۱۸۳۱–۱۸۹۹) بعد از نشان دادن چگونگی رنگ آمیزی استان‌های نقشهٔ انگلیس تنها با چهار رنگ، به مسئلهٔ کلی علاقه‌مند شد. در آن زمان فردریک گاتری (۱۸۳۳–۱۸۶۶) دانشجوی اوگاستس دمورگن (۱۸۰۶–۱۸۷۱) بود که مسئله را (در ۱۸۵۲) با ویلیام همیلتن (۱۸۰۵–۱۸۶۵) در میان گذاشت. بعداً در ۱۸۷۸، جامعهٔ علمی از طریق اطلاعیهٔ آرثر کیلی (۱۸۲۱–۱۸۹۵) در گردهمایی انجمن ریاضی لندن از مسئله آگاه شد. مدت کوتاهی بعد از آن، سرآلفرد کمپ (۱۸۴۹–۱۹۲۲)، ریاضیدان انگلیسی، برهانی پیدا کرد که بیش از یک دهه غیرقابل تردید باقی‌ماند. بعداً در ۱۸۹۰ پرسی جان هیوود (۱۸۶۱–۱۹۵۵)، ریاضیدان دیگر انگلیسی در کار کمپ خطایی یافت. | ## بخش 3: رنگ‌آمیزی گراف | مسئله تا سال ۱۹۷۶ حل نشده ماند، تا اینکه سرانجام کنت آپل و ولفگانک هیکن آن را حل کردند. در برهان آن‌ها تحلیل کامپیوتری بسیار پیچیده‌ای از پیکر بندی‌های (کاهش پذیر) ۱۹۳۶ به کار رفته‌است. گر چه تنها چهار رنگ برای رنگ آمیزی خاص ناحیه‌های یک نقشهٔ هامنی مورد نیاز است، ولی برای رنگ آمیزی خاص رأس‌های گراف‌های غیر هامنی بیش از چهار رنگ لازم است. آنچه را که چندجمله‌ای فامی G می‌نامند نیز به دست خواهیم آورد و چگونگی استفاده از آن را در محاسبه (χ(G خواهیم دید. مثال ۱: برای گراف G در شکل ۱، از رأس a شروع می‌کنیم و سپس در هر رأس، عدد فامی لازم برای رنگ آمیزی رأس‌های G را که برای آن‌ها در نظر گرفته‌ایم می‌نویسیم. وقتی به رأس b می‌رویم، عدد ۲ نیاز ما به رنگ دوم است و اگر به صورت الفبایی تا f پیش برویم متوجه می‌شویم که برای رنگ آمیزی خاص a,b،c,d،e,f به دو رنگ نیاز داریم. برای رأُس g، رنگ سومی لازم است؛ این رنگ سوم را می‌توان برای رأس h هم به کار برد، زیرا g , h یالی از G نیست. بنابراین، اگر بتوانیم راهی برای رنگ آمیزی خاص رأسهای G با چهار رنگ تعیین کنیم، آن گاه می‌دانیم که χ(G)=۴. یک راه انجام این کار، این است که رأس‌های e ,f، g را با رنگ آبی، رأس‌های b و j را با رنگ‌های قرمز، رأس‌های c و h را با رنگ سفید و رأسهای a , d، i را با رنگ سبز رنگ بزنیم. فرض کنید G گرافی بی سو ست و λ عدد صحیح مثبت معرّف تعداد رنگ‌های است که برای رنگ آمیزی خاص رأس‌های G موجودند. هدف ما یافتن چندجمله‌ای (P(G، λ برحسب متغیر λ است که بیان می‌کند به چند راه مختلف رأس‌های G را، با استفاده از حداکثر λ رنگ، رنگ کنیم. در نتیجه دو رنگ آمیزی خاص چنین گرافی به مفهوم زیر متمایز در نطر گرفته می‌شوند: رنگ آمیزی خاص (رأس‌های G) که حداکثر λ رنگ به کار می‌برد تابعی مانند f با حوزهٔ V و حوزهٔ تمام ۳٬۲٬۱، …، λ است، که در آن، برای رأس‌های مجاور f(u)≠f(v),u،v∈V. وقتی (λ=n=χ(G، برای اولین بار P(G، λ)>۰ ج) برای هر مسیر در شکل ۴ تعداد انتخاب‌ها در هر رأس متوالی را در نظر می‌گیریم. چون (P(G1،۱)=۰=P(G2،۱، ولی (χ(G1)=χ(G2)=۲، P(G1،۲)=۲=P(G2،۲، اگر پنج رنگ موجود باشند، می‌توانیم به‌طور خاص G1 را به۳۲۰ راه رنگ بزنیم؛ G2 را نیز می‌توان به همین طریق به۱۲۸۰ راه رنگ کرد. در بسیاری از موارد در ریاضیات گسسته، برای حلّ مسائل با حالت‌های زیاد روش‌هایی که به کار رفته‌اند، تفکیک این حالت‌ها به دو یا چند حالت کمتر است. با استفاده از این زیر گراف‌های خاص، اینک به قضیهٔ اصلی می‌رسیم: قضیه ۱ (قضیهٔ تجزیه برای چندجمله‌ای‌های فامی): اگر(G=(V,E گرافی همبند باشد و e∈E، آن گاه: (P(Ge، λ)=P(G، λ)+P('Ge، λ برهان: فرض کنید e=a,b. آن رنگ آمیزیهایی که در آن‌ها a و b دارای رنگ‌های متفاوت اند رنگ آمیزی‌های خاص G هستند. | ## جمع‌بندی | مثال ۶: محاسبات زیر ،(P(G، λ را برای G که دوری به درازای ۴ است ،(شکل۶) به دست می‌دهد.