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

رنگ‌آمیزی گراف : یک رنگامیزی گراف پترسن به کمک ۳ رنگ (کمترین تعداد رنگ ممکن).

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

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

تاریخچه :

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

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

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

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

عدد رنگی :

شکل 1 یک گراف 3- رنگی.

عدد رنگی k- رنگ آمیزی رأسی G تخصیص k رنگ،۱‚۲‚... ‚k، به رأسهای G است؛ رنگ آمیزی سره‌است اگر هیچ دو رأس مجاور متمایز داری یک رنگ نباشند. لذا k- رنگ آمیزی رأسی سرهٔ گراف بدون طوقه G، افراز(۱,x۲,…,xk - ۱ (H)Ӽ. چنین گراف‌هایی را اولین بار دیراک (۱۹۵۲) بررسی کرده‌است. گراف k – بحرانی گرافی است k- رنگی و بحرانی؛ هر گراف k- رنگی دارای زیرگراف k- بحرانی است. یک گراف ۴- بحرانی را که منسوب به گروتسش (۱۹۵۸) است در شکل ۲ نشان داده‌ایم. یک پیامد سادهٔ تعریف، آن است که هر گراف بحرانی همبند است. قضایای زیر بعضی از ویژگی‌های اساسی گراف‌های بحرانی را ثابت می‌کنند.

چندجمله‌ای رنگی :

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

چند جمله‌ای‌های رنگی به تعداد روش‌های رنگ‌امیزی یک گراف اطلاق می‌شود که تعداد رنگ‌های مورد ساتفاده از تعداد مشخصی بیشتر نشود. برای مثال گراف شکی سمت چپ با ۱۲ روش با ۳ رنگ، رنگامیزی می‌شود. رنگامیزی آن با ۲ رنگ غیر ممکن است. با ۴ رنگ این کار را می‌توان با ۷۲ = ۴٫۱۲ + ۲۴ روش رنگ کرد(اگر حتما از هر ۴ رنگ استفاده کنیم ۲۴ =!۴ روش ممکن است.).

تعداد رنگ‌ها	۱	۲	۳	۴	…
تعداد حالت‌های رنگامیزی	۰	۰	۱۲	۷۲	…

چندجمله‌ای رنگی تابعی است به صورت (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)(t7 − 12t6 + 67t5 − 230t4 + 529t3 − 814t2 + 775t − 352)

به نقل از : http://fa.wikipedia.org

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

مطالب مشابه :

اعداد رمزی

فعالیت تکمیلی برای شناخت اعداد و رنگ ها

قضیه رمزی(ramsey)

آموزش جمع اعداد با حاصل دو رقمی

فعالیت تکمیلی برای شناخت اعداد و رنگ ها

آموزش ساخت برنامه رنگ آمیزی نقاشی با آدوب فلش ( یه شروع کلیدی )

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

جمع اعداد یک رقمی با حاصل دو رقم در پایه ی اول