پاورپوینت درسی رنگ آمیزی گراف ها (pptx) 25 اسلاید

دسته بندی : پاورپوینت

نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )

تعداد اسلاید: 25 اسلاید

قسمتی از متن PowerPoint (.pptx) :

رنگ آمیزی گراف ها سر فصل مطالب : اصول رنگ آمیزی گراف ها تاریخچه کاربردها اصول رنگ آمیزی گراف : در نظریه گراف، رنگ‌آمیزی گراف یکی از حالت‌های خاص برچسب گذاری گراف است. رویکرد کلی آن نظیر کردن رنگهایی به المان های یک گراف است به طوری که این رنگ آمیزی محدودیت خاصی را برآورده کند.   اصول رنگ آمیزی گراف : انواع حالت های رنگ آمیزی گراف : رنگ آمیزی رأس ها : در این حالت رنگ‌آمیزی‌ باید به گونه ای باشد که درآن هیچ دو راس مجاوری هم رنگ نباشند. رنگ آمیزی یال ها : در این حالت رنگ‌آمیزی‌ باید به گونه ای باشد که درآن هیچ دو یال مجاوری هم رنگ نباشند. رنگ آمیزی سطح : در این حالت رنگ آمیزی باید به گونه ای باشد که در آن هیچ دو ناحیه ی گراف که مرز مشترک دارند همرنگ نباشند. تاریخچه اولین نتیجه‌های بدست آمده در مورد رنگ آمیزی گراف از تلاش‌های انجام شده بر روی گراف‌های مسطح برای حل مساله رنگ آمیزی نقشه بدست آمد. در آن زمان Francis Guthrie ادعا کرد که رنگ آمیزی نقشه ایالت‌های مختلف بریتانیا روی نقشه، به طوری که هیچ دو ایالت مجاوری همرنگ نشوند، می‌تواند با ۴ رنگ انجام شود. برادر Guthrie این مساله را برای معلم ریاضی خود Augustus de Morgan، در College of Londonفرستاد و او این مساله را در سال ۱۸۲۵ میلادی در نامه‌ای که به William Hamilton نوشت مطرح کرد. تاریخچه در سال ۱۸۷۹ Arthur Cayley این مساله را در انجمن ریاضی شهر لندن مطرح کرد. در همان سال Alfred Kempe، نتایج بدست آمده را منتشر کرد و برای یک دهه تصور می‌شد این مساله حل ‌شده ‌است. برای تلاش‌های Kempe در این زمینه او به عنوان یکی از اعضای جامعه سلطنتی و بعدها به عنوان ریاست انجمن ریاضی شهر لندن انتخاب شد. در سال 1820، Heawood ادعا کرد که استدلال Kempe اشتباه بوده‌است و اثبات این مساله را برای ۵ رنگ منتشر کرد. تاریخچه در قرن بیستم تلاش‌های زیادی برای اثبات روش‌های رنگامیزی نقشه با ۴ رنگ صورت گرفت که در نهایت در سال ۱۹۷۶ این مسأله به وسیله Kenneth Appel و Wolfgang Haken اثبات شد ولی به دلیل استفاده از کامپیوتر برای اثبات مساله، به آن اعتنایی نشد. رنگ آمیزی رأس ها : در این حالت باید رنگ ها به گونه ای به رأس های گراف نسبت داده شود که هیچ دو رأس مجاوری همرنگ نشوند. از آن جا که اگر گرافی دارای حلقه (روی یک رأس) باشد نمی تواند به طورمناسب رنگ آمیزی شود برای مسأله رنگ آمیزی رأس ها گراف باید بدون حلقه (روی رأس ها) باشد. اصطلاح استفاده از رنگ برای برچسب گذاری گراف ها به مسأله رنگ آمیزی نقشه ها بر می گردد. از آن جا که تعداد رنگ ها محدود است و نمی توان در گراف های با تعداد رأس زیاد از رنگ ها استفاده کرد می توان از برچسب های دیگری نظیر اعداد طبیعی (3،2،1،...) برای رنگ آمیزی گراف ها استفاده کرد. رنگ آمیزی رأس ها : یک رنگ آمیزی با استفاده از حداکثر k رنگ را یک مسأله k-coloring می گویند. حداقل تعداد رنگ هایی را که برای رنگ آمیزی یک گراف مثل G لازم است عدد رنگی (chromatic number) آن گراف می گویند و با X(G) نمایش می دهند. گرافی را که می تواند با k رنگ به طور مناسب رنگ آمیزی شود یک گراف k-colorable می گویند و اگر عدد رنگی گراف هم دقیقا برابر k باشد گراف را k-رنگی (k-chromatic) می گویند.