رنگ‌آمیزی گراف
کاربردها > مسئله چندجمله ای‌های فامی

در شرکت شیمیایی J&J، جین متصدی انبار کردن ترکیب‌های شیمیایی در انبار شرکت است. چون بعضی از انواع ترکیب‌ها (نظیر اسید و بازها) نباید
در مجاورت هم نگهداری شوند، تصمیم می‌گیرد که از همکارش جان بخواهد که انبار را به ناحیه‌های جدا از هم ذخیره‌سازی تقسیم کند که بتوان مواد
شیمیایی ناسازگار با هم را در بخش‌های جدا از یکدیگر انبار کرد. چطور می‌تواند تعداد بخش‌های ذخیره‌سازی را که همکارش باید بسازد معین کند؟
اگر شرکتی ۲۵ ترکیب شیمیایی بفروشد، فرض کنیدc1، c2، …، c25=v مجموعهٔ رأس‌ها باشد. به ازای ۱≤i≤y≤۲۵ یال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 را حساب کنیم؟ قبل از انجام هرکاری دربارهٔ چگونگی تعیین عدد فامی گراف، به مطلب وابستهٔ زیر توجه می‌کنیم.
حدود ۱۸۵۰، فرانسیس گاتری (۱۸۳۱–۱۸۹۹) بعد از نشان دادن چگونگی رنگ آمیزی استان‌های نقشهٔ انگلیس تنها با چهار رنگ، به مسئلهٔ کلی علاقه‌مند شد. اندکی بعد از آن، «مسئله چهار رنگ» را به برادر کوچکش فردریک نشان داد. در آن زمان فردریک گاتری (۱۸۳۳–۱۸۶۶) دانشجوی اوگاستس دمورگن (۱۸۰۶–۱۸۷۱) بود که مسئله را (در ۱۸۵۲) با ویلیام همیلتن (۱۸۰۵–۱۸۶۵) در میان گذاشت. این مسئله مورد توجه همیلتن قرار نگرفت و حدود ۲۵ سال مسکوت ماند. بعداً در ۱۸۷۸، جامعهٔ علمی از طریق اطلاعیهٔ آرثر کیلی (۱۸۲۱–۱۸۹۵) در گردهمایی انجمن ریاضی لندن از مسئله آگاه شد. کیلی در ۱۸۷۹ مسئله را در اولین مجلهٔ گزارش انجمن سلطنتی جغرافیا بیان کرد. مدت کوتاهی بعد از آن، سرآلفرد کمپ (۱۸۴۹–۱۹۲۲)، ریاضیدان انگلیسی، برهانی پیدا کرد که بیش از یک دهه غیرقابل تردید باقی‌ماند. بعداً در ۱۸۹۰ پرسی جان هیوود (۱۸۶۱–۱۹۵۵)، ریاضیدان دیگر انگلیسی در کار کمپ خطایی یافت. مسئله تا سال ۱۹۷۶ حل نشده ماند، تا اینکه سرانجام کنت آپل و ولفگانک هیکن آن را حل کردند. در برهان آن‌ها تحلیل کامپیوتری بسیار پیچیده‌ای از پیکر بندی‌های (کاهش پذیر) ۱۹۳۶ به کار رفته‌است.
گر چه تنها چهار رنگ برای رنگ آمیزی خاص ناحیه‌های یک نقشهٔ هامنی مورد نیاز است، ولی برای رنگ آمیزی خاص رأس‌های گراف‌های غیر هامنی بیش از چهار رنگ لازم است.
با چند مثال کوچک شروع می‌کنیم. در این صورت راهی برای تعیین (χ(Gاز زیر گراف‌های کوچکتر G خواهیم یافت. آنچه را که چندجمله‌ای فامی G می‌نامند نیز به دست خواهیم آورد و چگونگی استفاده از آن را در محاسبه (χ(G خواهیم دید.
مثال ۱: برای گراف G در شکل ۱، از رأس a شروع می‌کنیم و سپس در هر رأس، عدد فامی لازم برای رنگ آمیزی رأس‌های G را که برای آن‌ها در نظر گرفته‌ایم می‌نویسیم. وقتی به رأس b می‌رویم، عدد ۲ نیاز ما به رنگ دوم است و اگر به صورت الفبایی تا f پیش برویم متوجه می‌شویم که برای رنگ آمیزی خاص a,b،c,d،e,f به دو رنگ نیاز داریم. برای رأُس g، رنگ سومی لازم است؛ این رنگ سوم را می‌توان برای رأس h هم به کار برد، زیرا g , h یالی از G نیست. پس χ(G)=۳.
مثال ۲: الف) برای هر χ(K n )=n ,n≥۱.
ب) عدد فامی گراف شکل ۲ (هرشل) برابر ۲ است.
ج) اگر G گراف پترسن باشد آن گاه χ(G)=۳.
مثال ۳: فرض کنید G گرافی است که در شکل ۳ نشان داده‌ایم. برای U=b,f،h,i، زیر گراف القایی (U) از G، با K4 یکریخت است، به قسمی که(χ(G)≥χ(K4. بنابراین، اگر بتوانیم راهی برای رنگ آمیزی خاص رأسهای G با چهار رنگ تعیین کنیم، آن گاه می‌دانیم که χ(G)=۴. یک راه انجام این کار، این است که رأس‌های e ,f، g را با رنگ آبی، رأس‌های b و j را با رنگ‌های قرمز، رأس‌های c و h را با رنگ سفید و رأسهای a , d، i را با رنگ سبز رنگ بزنیم.
اینک به روشی برای تعیین (χ(G برمی گردیم. آنچه مطرح می‌کنیم از بسط مقالهٔ تحقیقی [۲۲]، اثر رید گرفته شده‌است.
فرض کنید G گرافی بی سو ست و λ عدد صحیح مثبت معرّف تعداد رنگ‌های است که برای رنگ آمیزی خاص رأس‌های G موجودند. هدف ما یافتن چندجمله‌ای (P(G، λ برحسب متغیر λ است که بیان می‌کند به چند راه مختلف رأس‌های G را، با استفاده از حداکثر λ رنگ، رنگ کنیم.
در سراسر این بحث، رأس‌های گراف بی سوی (G=(V,E به وسیله برچسب‌ها از هم متمایزند. در نتیجه دو رنگ آمیزی خاص چنین گرافی به مفهوم زیر متمایز در نطر گرفته می‌شوند: رنگ آمیزی خاص (رأس‌های G) که حداکثر λ رنگ به کار می‌برد تابعی مانند f با حوزهٔ V و حوزهٔ تمام ۳٬۲٬۱، …، λ است، که در آن، برای رأس‌های مجاور f(u)≠f(v),u،v∈V. لذا تفاوت رنگ آمیزی خاص از متفاوت بودن این تابع‌ها معلوم می‌شود.
مثال ۴: الف) اگر (G=(V,E با V|=n|و E=∅، آن گاه G عبارت از n نقطهٔ تنهاست، و بنابر اصل ضرب P(G، λ)=λn.
ب) اگر G=Kn، آن گاه حداقل باید n رنگ موجود باشد تا G را به‌طور خاص رنگ بزنیم. در اینجا، بنابر اصل ضرب، (P(G، λ)=λ(λ-۱)(λ-۲)…(λ-n+1، که آن را با λ(n نشان می‌دهیم. به ازای P(G، λ)=۰، λ<n و راهی برای رنگ آمیزی خاص Kn وجود ندارد. وقتی (λ=n=χ(G، برای اولین بار P(G، λ)>۰
ج) برای هر مسیر در شکل ۴ تعداد انتخاب‌ها در هر رأس متوالی را در نظر می‌گیریم. اگر به صورت الفبایی پیش برویم، در میابیم که P(G1، λ)=λ(λ-1)3 و P(G2، λ)=λ(λ-1)4. چون (P(G1،۱)=۰=P(G2،۱، ولی (χ(G1)=χ(G2)=۲، P(G1،۲)=۲=P(G2،۲، اگر پنج رنگ موجود باشند، می‌توانیم به‌طور خاص G1 را به۳۲۰ راه رنگ بزنیم؛ G2 را نیز می‌توان به همین طریق به۱۲۸۰ راه رنگ کرد.
(به‌طور کلی :اگر G مسیری با n رأس باشد، آن گاهP(G، λ)=λ(λ-1)n-1)
د) اگر G از مؤلفه‌های C1،C2، …،Ck ساخته شده باشد، آن گاه باز بنابر اصل ضرب، نتیجه می‌شود که (P(G، λ)=P(C1، λ).P(C2، λ)…P(Ck، λ.
به عنوان نتیجه‌ای از مثال ۴ (د) توجه خود را بر گراف‌های همبند متمرکز می‌کنیم. در بسیاری از موارد در ریاضیات گسسته، برای حلّ مسائل با حالت‌های زیاد روش‌هایی که به کار رفته‌اند، تفکیک این حالت‌ها به دو یا چند حالت کمتر است. ما نیز همین روش را برای حل مسئله به کار می‌بریم. برای انجام این کار به مفاهیم و نمادگذاری زیر نیاز داریم.
فرض کنید(G=(V,E گرافی بی سو باشد. برای e=a,b ∈E فرض می‌کنیم Ge معرف زیر گراف G حاصل از حذف e از G، بدون برداشتن رأس‌های a و b است؛ یعنی به صورت Ge=G-e می‌باشد. از Ge، زیرا گراف دوّمی از G با اتصال رأس‌های a و b به دست می‌آید. این زیر گراف دوم را با 'Ge نشان می‌دهیم.
مثال ۵: شکل۵، Ge و'Ge را برای گراف G با یالی که با e مشخص شده‌است نشان می‌دهد. توجه کنید که چگونه اتصال a و b در 'Ge از اتصال دو جفت از یال‌های d,b، d,a، a,c، b,c نتیجه می‌شود.
با استفاده از این زیر گراف‌های خاص، اینک به قضیهٔ اصلی می‌رسیم:
قضیه ۱ (قضیهٔ تجزیه برای چندجمله‌ای‌های فامی): اگر(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، λ نتیجه می‌شود.
مثال ۶: محاسبات زیر ،(P(G، λ را برای G که دوری به درازای ۴ است ،(شکل۶) به دست می‌دهد.
از مثال ۲ (ج) ،P(Ge، λ)=λ(λ-1)3. با Ge '= K3 داریم P('Ge، λ)=λ(3. بنابراین P(G، λ) = λ(λ-1)3-λ(λ-۱)(λ-۲) = λ(λ-۱)[(λ-1)2-(λ-۲)] = λ(λ-۱)[λ2-3λ+۳]=λ4-4λ3+6λ2-3λ
چون P(G،۱)=۰ در حالی که P(G،۲)=۲>۰، داریم χ(G)=۲.
قضیه ۲: برای هر گراف G، جملهٔ ثابت در(P(G، λ برابر ۰ است.
برهان: برای هر گراف G، χ(G)>0، زیرا V≠ ∅. اگر تعداد(P(G، λ دارای جملهٔ ثابت a باشد، آن گاه P(G،۰)=a≠۰. این مطلب نتیجه می‌دهد که تعداد a راه برای رنگ کردن خاص G با ۰ رنگ وجود دارد.
قضیه ۳: فرض کنید(G=(V,E با E|>0|. در این صورت مجموع ضریب‌ها در(P(G، λ برابر با ۰ است.
برهان: چون E|≥۱|، پس χ(G)≥۲. در نتیجه P(G،۱)=۰ برابر مجموع ضریب‌ها در(P(G، λ است.
این گراف به ۱۲ روش می‌تواند رنگ‌آمیزی ۳ رنگه شود.
تمامی گراف‌های غیرایزومرفیک از درجه ۳ و تعداد روش‌های رنگ‌آمیزی آنها.