رنگ آمیزی نمودار :تعریف و اصطلاحات
تعریف و اصطلاحات [ ویرایش ]
این نمودار به 12 روش مختلف می تواند 3 رنگ باشد.
رنگ آمیزی عمودی [ ویرایش ]
در صورت استفاده از هیچگونه صلاحیت ، رنگ آمیزی یک نمودار تقریباً همیشه یک نقاشی مناسب با ورق است ، یعنی برچسب زدن از رئوس نمودار با رنگ هایی به گونه ای که هیچ دو راس با یک لبه مشترک با هم یکسان نیستند. از آنجایی که یک راس با یک حلقه (یعنی اتصال مستقیم به خود باز می گردد) هرگز نمی تواند به درستی رنگ شود ، درک می شود که نمودارهای موجود در این زمینه بدون حلقه هستند.
اصطلاحات استفاده از رنگ ها برای برچسب های vertex به رنگ آمیزی نقشه برمی گردد. از برچسب هایی مانند قرمز و آبی فقط در مواردی استفاده می شود که تعداد رنگ ها کمی باشد ، و به طور معمول درک می شود که برچسب ها از عدد صحیح 1 ، 2 ، 3 ، ... drawn کشیده می شوند.
رنگ آمیزی با استفاده از حداکثر K رنگ است (مناسب) به نام K -coloring . به کمترین تعداد رنگ مورد نیاز برای رنگ آمیزی یک نمودار G ، تعداد کرواتیکی آن گفته می شود و اغلب به χ ( G ) اشاره می شود. گاهی اوقات γ ( G ) استفاده می شود ، زیرا χ ( G ) نیز برای مشخص کردن ویژگی اویلر یک نمودار استفاده می شود. یک نمودار است که می توان اختصاص (مناسب) K -coloring است ک -colorable ، و آن است ک -chromatic اگر عدد رنگی آن است که دقیقا ک . زیر مجموعه ای از رئوس ها که به همان رنگ اختصاص داده می شوند ، یک کلاس رنگ نامیده می شود ، هر کلاس چنین مجموعه مستقل را تشکیل می دهد . بنابراین ، k- colour همان قسمت جدائی از راس است که به مجموعه های مستقل k تبدیل شده است ، و اصطلاحات k-partite و k-colorable معنی مشابهی دارند.
چند جمله ای Chromatic [ ویرایش ]
کلیه نمودارهای غیر همسان در 3 راس و چند جملههای کروماتیک آنها. نمودار خالی E 3 (قرمز) 1 رنگ را تصدیق می کند. دیگران اعتراف نمی کنند چنین نقاشی هایی داشته باشند. نمودار سبز 12 رنگ با 3 رنگ را پذیرفته است.
مقاله اصلی: چند جمله ای Chromatic
چند جمله ای رنگی شمارش تعدادی از راه های یک گراف می توان با استفاده بیش از یک عدد داده شده از رنگ، رنگ آمیزی. به عنوان مثال ، با استفاده از سه رنگ ، نمودار موجود در تصویر مجاور می تواند به 12 روش رنگی شود. تنها با دو رنگ ، به هیچ وجه نمی توان رنگ آمیزی کرد. با چهار رنگ ، می توان آن را به صورت 24 + 4 = 12 = 72 رنگ آمیزی کرد: با استفاده از هر چهار رنگ ، 4 عدد وجود دارد! = 24 رنگ معتبر ( هر انتساب چهار رنگ به هر نمودار 4-vertex یک رنگ آمیزی مناسب است)؛ و برای هر انتخاب از سه چهار رنگ ، 12 رنگ 3 رنگ معتبر وجود دارد. بنابراین ، برای نمودار موجود در مثال ، جدول تعدادی از رنگهای معتبر مانند این شروع می شود:
| رنگهای موجود | 1 | 2 | 3 | 4 | ... |
| تعداد نقاشی ها | 0 | 0 | 12 | 72 | ... |
چند جمله ای کروماتیک یک تابع P ( G ، t ) است که تعداد رنگ های T رنگی G را شمارش می کند . همانطور که از نام آن مشخص است ، برای یک G خاص ، عملکرد در واقع چند جمله ای در t است . برای نمودار مثال ، P ( G ، t ) = t ( t - 1) 2 ( t - 2) و در واقع P ( G ، 4) = 72.
چند جمله ای کروماتیک حداقل به همان اندازه اطلاعات رنگی G را شامل می شود که تعداد کروماتیک آن نیز هست. در واقع ، χ کوچکترین عدد صحیح مثبت است که ریشه چند جمله ای کرومیکی ندارد
| مثلث K 3 |  |
| نمودار کامل K n |  |
| درخت با N راس |  |
| چرخه C n |  |
| نمودار پیترسن |  |
رنگ آمیزی لبه [ ویرایش ]
مقاله اصلی: رنگ آمیزی لبه
لبه رنگ آمیزی از یک گراف رنگ آمیزی مناسب از است لبه ، به این معنی انتساب از رنگ به لبه به طوری که هیچ راس حادثه به دو لبه از همان رنگ است. لبه رنگ آمیزی با K رنگ است که به نام K لبه-رنگ آمیزی و معادل برای این مشکل از پارتیشن بندی مجموعه ای لبه به است ک تطابق . کمترین تعداد رنگ مورد نیاز برای رنگ آمیزی یک لبه G ، شاخص کروماتیک یا عدد کروماتیکی لبه ، χ ′ ( G ) است. رنگ آمیزی Tait یک رنگ 3 لبه از یک نمودار مکعب است . قضیه چهار رنگ معادل این ادعا که هر مکعب مسطح است bridgeless نمودار اذعان رنگ آمیزی تیت.
کل رنگ آمیزی [ ویرایش ]
مقاله اصلی: کل رنگ آمیزی
رنگ آمیزی کامل نوعی رنگ آمیزی بر روی رئوس و لبه های یک نمودار است. در صورت استفاده از هرگونه صلاحیت ، همیشه فرض می شود که یک رنگ کامل به این معنا باشد که به هیچ یک از راسهای مجاور ، لبه های مجاور و لبه ها و سرهای انتهایی آن به همان رنگ اختصاص نمی یابد. تعداد کل کروماتیک χ ″ (G) یک نمودار G کمترین رنگ مورد نیاز در هر رنگ آمیزی کل G است.
رنگ آمیزی بدون برچسب [ ویرایش ]
رنگ آمیزی بدون برچسب یک گراف، یک است مدار از یک رنگ آمیزی تحت عمل از گروه automorphism از نمودار. اگر رنگ آمیزی از یک نمودار را تفسیر کنیم
منبع