پاورپوینت رنگ آمیزی گراف ها

بخشی از پاورپوینت

اسلاید 1 :

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

اسلاید 2 :

سر فصل مطالب :
اصول رنگ آمیزی گراف ها
تاریخچه
کاربردها

اسلاید 3 :

اصول رنگ آمیزی گراف :
در نظریه گراف، رنگآمیزی گراف یکی از حالتهای خاص برچسب گذاری گراف است. رویکرد کلی آن نظیر کردن رنگهایی به المان های یک گراف است به طوری که این رنگ آمیزی محدودیت خاصی را برآورده کند.

اسلاید 4 :

اصول رنگ آمیزی گراف :
انواع حالت های رنگ آمیزی گراف :
رنگ آمیزی رأس ها : در این حالت رنگآمیزی باید به گونه ای باشد که درآن هیچ دو راس مجاوری هم رنگ نباشند.

رنگ آمیزی یال ها : در این حالت رنگآمیزی باید به گونه ای باشد که درآن هیچ دو یال مجاوری هم رنگ نباشند.

رنگ آمیزی سطح : در این حالت رنگ آمیزی باید به گونه ای باشد که در آن هیچ دو ناحیه ی گراف که مرز مشترک دارند همرنگ نباشند.

اسلاید 5 :

تاریخچه


اولین نتیجههای بدست آمده در مورد رنگ آمیزی گراف از تلاشهای انجام شده بر روی گرافهای مسطح برای حل مساله رنگ آمیزی نقشه بدست آمد.
در آن زمان Francis Guthrie ادعا کرد که رنگ آمیزی نقشه ایالتهای مختلف بریتانیا روی نقشه، به طوری که هیچ دو ایالت مجاوری همرنگ نشوند، میتواند با ۴ رنگ انجام شود. برادر Guthrie این مساله را برای معلم ریاضی خود Augustus de Morgan، در College of Londonفرستاد و او این مساله را در سال ۱۸۲۵ میلادی در نامهای که به William Hamilton نوشت مطرح کرد.

اسلاید 6 :

تاریخچه
در سال ۱۸۷۹ Arthur Cayley این مساله را در انجمن ریاضی شهر لندن مطرح کرد. در همان سال Alfred Kempe، نتایج بدست آمده را منتشر کرد و برای یک دهه تصور میشد این مساله حل شده است. برای تلاشهای Kempe در این زمینه او به عنوان یکی از اعضای جامعه سلطنتی و بعدها به عنوان ریاست انجمن ریاضی شهر لندن انتخاب شد.
در سال 1820، Heawood ادعا کرد که استدلال Kempe اشتباه بودهاست و اثبات این مساله را برای ۵ رنگ منتشر کرد.

اسلاید 7 :

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

اسلاید 8 :

رنگ آمیزی رأس ها :
در این حالت باید رنگ ها به گونه ای به رأس های گراف نسبت داده شود که هیچ دو رأس مجاوری همرنگ نشوند.
از آن جا که اگر گرافی دارای حلقه (روی یک رأس) باشد نمی تواند به طورمناسب رنگ آمیزی شود برای مسأله رنگ آمیزی رأس ها گراف باید بدون حلقه (روی رأس ها) باشد.
اصطلاح استفاده از رنگ برای برچسب گذاری گراف ها به مسأله رنگ آمیزی نقشه ها بر می گردد. از آن جا که تعداد رنگ ها محدود است و نمی توان در گراف های با تعداد رأس زیاد از رنگ ها استفاده کرد می توان از برچسب های دیگری نظیر اعداد طبیعی (3،2،1،.) برای رنگ آمیزی گراف ها استفاده کرد.

اسلاید 9 :

رنگ آمیزی رأس ها :
یک رنگ آمیزی با استفاده از حداکثر k رنگ را یک مسأله k-coloring می گویند.

حداقل تعداد رنگ هایی را که برای رنگ آمیزی یک گراف مثل G لازم است عدد رنگی (chromatic number) آن گراف می گویند و با X(G) نمایش می دهند.

گرافی را که می تواند با k رنگ به طور مناسب رنگ آمیزی شود یک گراف
k-colorable می گویند و اگر عدد رنگی گراف هم دقیقا برابر k باشد گراف را
k-رنگی (k-chromatic) می گویند.

اسلاید 10 :

رنگ آمیزی رأس ها :
یک زیر مجموعه از رأس های همرنگ یک گراف را کلاس رنگی (color class) می نامند. هر کلاس یک مجموعه مستقل را تشکیل می دهد. بنابراین یک مسأله
k-coloring در واقع تفکیک کردن مجموعه ی رأس های یک گراف به k مجموعه مستقل است. با این توصیف می توان یک گراف k-colorable را یک گراف k-بخشی
(k-partite) هم نامید.

اسلاید 11 :

چند جمله ای رنگی :
گراف روبرو را در نظر بگیرید :

با استفاده از 3 رنگ می توان گراف نشان داده شده در شکل را با 12 شیوه مختلف رنگ آمیزی کرد.

بااستفاده از 2 رنگ، رنگ آمیزی این گراف اصلا
امکان پذیر نیست.

اسلاید 12 :

چند جمله ای رنگی :
فرض کنید بخواهیم با استفاده از 4 رنگ گراف را رنگ آمیزی کنیم. می خواهیم بدانیم این کار به چند روش امکان پذیر است ؟
رأس aدر گراف را می توان با 4 رنگ مختلف رنگ آمیزی کرد.
با انتخاب یک رنگ برای رأس a ، رأس b را می توان با 3 رنگ مختلف رنگ آمیزی کرد.
با انتخاب یک رنگ برای رأس b ، رأس c را می توان با
2رنگ مختلف رنگ آمیزی کرد.
باانتخاب یک رنگ برای رأس c ، رأس d را می توان با
3 رنگ مختلف رنگ آمیزی کرد.

اسلاید 13 :

چند جمله ای رنگی :
پس مجموعا 72 = 3*2*3*4 روش مختلف برای رنگ آمیزی این گراف با 4 رنگ وجود دارد.

اسلاید 14 :

چند جمله ای رنگی :
بنابراین برای گراف مورد نظر جدول تعداد روش های معتبر رنگ آمیزی، به صورت زیر خواهد بود :

اسلاید 15 :

بنابراین چند جمله ای رنگی یک گراف تعداد راه های مختلفی را که یک گراف می تواند با استفاده از تعداد مشخصی رنگ، رنگ آمیزی شود محاسبه می کند.
چندجمله ای رنگی یک گراف تابعی مثل P(G,t) است که نشان دهنده ی تعداد راه هایی است که می توان گراف G را با t رنگ، رنگ آمیزی کرد. همان طور که مشخص است برای یک گراف مثل G چند جمله ای رنگی تابع t است.
به عنوان مثال برای گرافی که در قسمت قبل بررسی شد تابع P به صورت زیر است:
چند جمله ای رنگی :
P(G, t) = t(t − 1)2(t − 2)
بنابراین P(G,4)=72 است.

اسلاید 16 :

چند جمله ای رنگی :
رابطه چند جمله ای رنگی و عدد رنگی :
عدد رنگی یک گراف را که با X(G) نمایش دادیم در واقع کوچکترین عدد طبیعی است که ریشه ی چند جمله ای رنگی گراف نباشد. یعنی :
X(G) = min { k : P(G,k) > 0 }

اسلاید 17 :

چند جمله ای رنگی :
چند جمله ای رنگی برای تعدادی از گراف های مشهور به صورت زیر است :

اسلاید 18 :

چند جمله ای رنگی :
در شکل زیر می توانید رسم چند جمله ای رنگی
برای چهار گراف موجود در شکل را ببینید :

به عنوان مثال از روی شکل مشخص است که برای گراف قرمز رنگ عدد رنگی 1 است چون می توان با یک رنگ، گراف را طوری رنگ آمیزی کرد که هیچ دو رأس مجاوری همرنگ نباشند.

اسلاید 19 :

رنگ آمیزی یال ها :
در این حالت باید رنگ ها به گونه ای به یال های گراف نسبت داده شود که هیچ دو یالی که در یک رأس متلاقی هستند همرنگ نباشند.

یک رنگ آمیزی گراف با k رنگ یک مسأله k-edge-coloring نامیده می شود .

کمترین تعداد رنگی را که برای رنگ آمیزی یال های یک گراف لازم است شاخص رنگی (chromatic index) آن گراف می نامند.

اسلاید 20 :

رنگ آمیزی یال ها :
به عنوان نمونه می توانید در شکل زیر یک گراف که با 3 رنگ، رنگ آمیزی شده ببینید.