رنگبندی بخشی گراف

رنگبندی بخشی
بندانگشتی
رنگ‌بندی بخشی موضوعی جدید در شاخه تئوری گراف ( ) است که به نام تئوری گراف بخشی ( ) شناخته می‌شود. این موضوع تعمیمی از رنگ‌بندی گراف معمولی می‌باشد. در رنگ‌بندی گراف سنتی، هر راس از گراف به رنگ‌های متعددی در آورده می‌شود و راس‌های مجاور (به این معنا که به وسیله‌ی یالی به هم متصل شده‌اند) باید به رنگ‌های متمایزی در آورده شوند. در یک رنگ‌بندی بخشی، یک مجموعه خاص از رنگ‌ها به هر راس گراف نسبت داده می‌شود. در این مسئله هم راس‌های مجاور نباید دارای رنگ‌های مشابه باشند. رنگ‌بندی بخشی را می‌توان به عنوان راحت‌سازی برنامه‌نویسی خطی یا ( ) در نظر گرفت. در واقع با رویکرد برنامه‌نویسی خطی، مسائل مربوط به رنگ‌بندی بخشی نسبت به رنگ‌بندی سنتی بسیار بیشتر قابل پاسخگویی می‌باشد.
تعریف
یک رنگ بندی ۱:۳ در یک حلقه با ۵ راس و یک رنگ بندی ۲:۶
یک رنگ‌بندی b-fold یا b-لایه یک گراف G، یک نسبت دهی از اندازه b به راس‌های گراف است به طوری که رئوس مجاور مجموعه متمایزی داشته باشند. یک رنگ‌بندی a:b تا رنگ‌بندی از میان رنگ‌های مجاز می‌باشد. یک عدد رنگی b-لایه ، حداقل تعداد a می‌باشد به طوری که یک رنگ بندی a: b موجود باشد.
عدد رنگی بخشی (X f (G به صورت زیر تعریف می‌شود:
توجه کنید که این حد به علت اینکه (X b (G زیر-افزاینده ( ) است موجود می‌باشد، به این معنا که (X a+b (G) ≤ X a (G) + X b (G.
یک عدد رنگی بخشی می‌تواند به صورت یک عبارت احتمالی مطرح شود. (X f (G کوچکترین k است به صورتی که یک توزیع احتمال بر روی مجموعه مستقل independent sets) G) وجود داشته باشد، به طوری که برای هر راس v،مجموعه مستقل S از توزیع احتمال گفته شده استخراج شود، با این شرط که:
برخی از ویژگی‌های (X f (G:
و
در اینحجا (n(G، مرتبه G و ((G عدد استقلال ( ) و عدد دسته ( ) و عدد رنگی می‌باشد.
فرمول بندی برنامه نویسی خطی
یک عدد رنگی بخشی X f (G) از یک گراف G می‌تواند به عنوان یک راه حل برای یک برنامه نویسی خطی در نظر گرفته شود. اگر مجموعه همه مجموعه‌های مستقل G باشد، مجموعه همه آن مجموعه‌های مستقل که شامل راس x است باشد و برای هر مجموعه مستقل I یک متغیر غیر منفی و حقیقی x I تعریف کنیم آنگاه X f (G)) حداقل مقدار
با توجه به برقرار بودن عبارت زیر است.
برای هر راس x
دوگانگی ( ) این برنامه خطی، عدد دسته بخشی (fractional clique number یا راحت سازی (relaxation) مستدلات مفهوم صحیح عدد دسته) را محاسبه می‌کند. این یک نسبت دادن وزن به رئوس است به طوری که مجموع وزن نسبت داده شده به هر مجموعه مستقل حداکثر ۱ باشد. قضیه دوگانگی قوی ( ) در برنامه‌نویسی خطی، تضمین می‌کند که بهینه‌ترین راه حل‌های هر دو برنامه خطی مقدار یکسان دارند؛ حال آن که ممکن است هر برنامه خطی دارای اندازه تعداد رئوس G نمایی باشند و محاسبه عدد رنگی بخشی گراف دارای سختی NP باشد. این موضوع و مسئله رنگ‌بندی بخشی یال‌های یک گراف که می‌تواند از مرتبه نمایی باشد، متمایز هستند. این موضوع یک نتیجه‌گیری مستقیم از قضیه تطبیق پلیتپ ادموند (Edmonds’s matching polytope) می‌باشد.
کاربردها
یکی از کاربردهای رنگ‌بندی بخشی گراف شامل زمانبندی فعالیت‌ها می‌باشد. در این مورد، گراف G یک گراف ناسازگاری است. یک یال در G بین رئوس v و u نشان می‌دهد که v و u نمی‌توانند همزمان فعال باشند. به عبارتی دیگر، مجموعه رئوس که به صورت همزمان فعال هستند، می‌بایستی یک مجموعه مستقل در گراف G باشند.
یک رنگ‌بندی بخشی گراف بهینه در G کوتاه‌ترین زمانبندی ممکن را تولید می‌کند به طوری که هر راس در مجموع برای حداقل ۱ واحد زمانی فعال باشد و در هر نقطه از زمان، مجموع رئوس فعال یک مجموعه مستقل باشد. اگر ما یک راه حل خطی برای برنامه خطی فوق داشته باشیم، ما به راحتی همه مجموعه‌های مستقل I را به صورت دلخواه پیمایش می‌کنیم. رئوسی که در I می‌باشند را برای مدت XI فعال در نظر می‌گیریم در حالی که رئوسی که در I نیستند را غیر فعال در نظر می‌گیریم.
یک نمونه کاربرد واضح‌تر این است که مثلا: هر راس G یک انتقال رادیویی بی‌سیم را در یک ارتباط شبکه نشان دهد. یال‌های G تداخل در تبادلات رادیویی را نشان می‌دهند. هر انتقال رادیویی باید در مجموع به اندازه یک واحد زمانی فعال باشد. یک رنگ‌بندی بخشی گراف بهینه، یک زمانبندی با حداقل طول و بدون تداخل را به ما می‌دهد، به عبارت دیگر یک زمانبندی با حداکثر پهنای باند را به ما می‌دهد.
مقایسه با رنگ‌بندی سنتی گراف
در مثال قبلی انتقال رادیویی، اگر لازم باشد که یک گره (راس) از گراف به طور پیوسته و بدون قطع و وصل شدن، فعال باشد آنگاه رنگ‌بندی رئوس گراف به روش سنتی جواب بهینه را به ما می‌دهد. توضیح آنکه ابتدا باید رئوس با رنگ شماره ۱ به مدت ۱ واحد زمانی باید فعال باشند سپس رئوس با با رنگ شماره ۲ به مدت یک واحد زمانی فعال می‌شوند و به همین ترتیب ادامه می‌یابد. یادآور می‌شود که در هر نقطه از زمان مجموعه گره‌های فعال، یک مجموعه مستقل می‌باشد.
به طور کلی، رنگ‌بندی بخشی گراف یک زمانبندی کوتاهتر به ما می‌دهد تا رنگ‌بندی غیر بخشی. یافتن یک زمانبندی کوتاهتر ممکن است اما به قیمت آنکه انتقال دهنده‌های رادیویی قابلیت قطع و وصل شدن بیش از یک بار را داشته باشند.