رنگ امیزی یالی

رنگ آمیزی یالی. در نظریهٔ گراف، یک رنگ آمیزی یالی از یک گراف، نسبت دادن "رنگ ها" به یال های گراف است به نحوی که هیچ دو یال مجاوری رنگ یکسان نداشته باشند. برای مثال، تصویر سمت چپ نمایانگر یک رنگ آمیزی یالی از یک گراف با رنگ های قرمز، آبی، و سبز است. رنگ آمیزی یالی یکی از انواع مختلف رنگ آمیزی گراف است. مسئلهٔ رنگ آمیزی یالی بررسی می کند که آیا ممکن است یال های یک گراف داده شده را با حداکثر k رنگ متفاوت که k داده شده است، یا با کمترین تعداد رنگ ممکن، رنگ کرد. کمترین تعداد لازم رنگ برای یال های یک گراف داده شده، شاخص رنگی آن گراف نامیده می شود. برای مثال، گراف تصویر با سه رنگ، رنگ می شود ولی نمی توان آن را با دو رنگ رنگ کرد، پس شاخص رنگی آن سه است.
بنابر قضیهٔ ویزینگ، تعداد رنگ های لازم برای رنگ آمیزی یالی یک گراف ساده برابر با بیشترین درجهٔ آن Δ یا Δ+۱ است. برای برخی از گراف ها مانند گراف های دوبخشی یا گراف های مسطح با درجهٔ بالا تعداد رنگ های لازم همیشه Δ است؛ ولی برای گراف های چندگانه تعداد رنگ های ممکن است به بزرگی ۳Δ/۲ باشد. الگوریتم هایی با زمان های چندجمله ای وجود دارند که رنگ آمیزی بهینهٔ گراف های دوبخشی یا گراف های غیر دوبخشی ساده که حداکثر Δ+۱ رنگ لازم دارند را محاسبه می کند؛ در صورتی که مسئلهٔ کلی یافتن رنگ آمیزی بهینه ان پی کامل است و سریع ترین الگوریتم شناخته شده برای آن، زمان نمایی نیاز دارد. انواع دیگری از مسئلهٔ رنگ آمیزی یالی مطالعه شده اند که در آن ها نسبت دادن رنگ ها به یال ها باید شرایط دیگری غیر از نامجاور بودن را نیز برآورده کند. مسئلهٔ رنگ آمیزی گراف کاربردهایی در مسائل زمان بندی و نیز انتساب فرکانس برای شبکه های فیبرنوری دارد.
گراف دوری با طول دور زوج به دو رنگ و با طول فرد به سه رنگ برای رنگ آمیزی یالی نیاز دارد. در این گراف ها، رنگ آمیزی یالی به صورت یک درمیان صورت می گیرد. [ ۱]
در گراف کامل Kn با n زوج به n − ۱ رنگ نیاز داریم. رنگ آمیزی گراف کامل، حالت خاص ( Baranyai’s theorem]] Soifer 2008]] ) به شمار می رود که راه حل هندسی زیر را ارائه می دهد: n نقطه در مرکز یک n − ۱ - ضلعی قرار دهید. به هر یال رأس مرکزی، رنگ متفاوتی را انتساب دهید. برای یال های دیگر رئوس نیز همین کار را با رعایت شروط رنگ آمیزی انجام دهید. درصورتی که n فرد باشد، برای رنگ آمیزی یالی به n رنگ نیاز داریم: هر رنگ برای ( n − ۱ ) /۲ یال قابل استفاده است که این تعداد یال، ۱/n تعداد کل یال هاست. [ ۲]