رنگبندی بخشی ( Fractional Coloring )
رنگ بندی بخشی موضوعی جدید در شاخه تئوری گراف ( graph theory ) است که به نام تئوری گراف بخشی ( fractional graph theory ) شناخته می شود. این موضوع تعمیمی از رنگ بندی گراف معمولی می باشد. در رنگ بندی گراف سنتی، هر رأس از گراف به رنگ های متعددی درآورده می شود و رأس های مجاور ( به این معنا که به وسیلهٔ یالی به هم متصل شده اند ) باید به رنگ های متمایزی درآورده شوند. در یک رنگ بندی بخشی، یک مجموعه خاص از رنگ ها به هر رأس گراف نسبت داده می شود. در این مسئله هم رأس های مجاور نباید دارای رنگ های مشابه باشند. رنگ بندی بخشی را می توان به عنوان راحت سازی برنامه نویسی خطی یا ( linear programming relaxation ) در نظر گرفت. در واقع با رویکرد برنامه نویسی خطی، مسائل مربوط به رنگ بندی بخشی نسبت به رنگ بندی سنتی بسیار بیشتر قابل پاسخگویی می باشد.
یک رنگ بندی b - fold یا b - لایه یک گراف G، یک نسبت دهی از اندازه b به رأس های گراف است به طوری که رئوس مجاور مجموعه متمایزی داشته باشند. یک رنگ بندی a:b تا رنگ بندی از میان رنگ های مجاز می باشد. یک عدد رنگی b - لایه Xb ( G ) ، حداقل تعداد a می باشد به طوری که یک رنگ بندی a: b موجود باشد. عدد رنگی بخشی ( Xf ( G به صورت زیر تعریف می شود:
توجه کنید که این حد به علت اینکه ( Xb ( G زیر - افزاینده ( subadditive ) است موجود می باشد، به این معنا که ( Xa+b ( G ) ≤ Xa ( G ) + Xb ( G.
یک عدد رنگی بخشی می تواند به صورت یک عبارت احتمالی مطرح شود. ( Xf ( G کوچک ترین k است به صورتی که یک توزیع احتمال بر روی مجموعه مستقل independent sets ) G ) وجود داشته باشد، به طوری که برای هر رأس v، مجموعه مستقل S از توزیع احتمال گفته شده استخراج شود، با این شرط که:
Pr ( v ∈ S ) ≥ 1 k
برخی از ویژگی های ( Xf ( G:
χ f ( G ) ≥ n ( G ) / α ( G )
و
ω ( G ) ≤ χ f ( G ) ≤ χ ( G )
در اینجا ( n ( G، مرتبه G و ( α ( G عدد استقلال ( independence number ) و ω ( G ) عدد دسته ( number Clique ) و X ( G ) عدد رنگی می باشد.
یک عدد رنگی بخشی Xf ( G ) از یک گراف G می تواند به عنوان یک راه حل برای یک برنامه نویسی خطی در نظر گرفته شود. اگر ( G ) Ι مجموعه همه مجموعه های مستقل G باشد، ( G, x ) Ι مجموعه همه آن مجموعه های مستقل که شامل رأس x است باشد و برای هر مجموعه مستقل I یک متغیر غیر منفی و حقیقی xI تعریف کنیم آنگاه Xf ( G ) ) حداقل مقدار
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفرنگ بندی بخشی موضوعی جدید در شاخه تئوری گراف ( graph theory ) است که به نام تئوری گراف بخشی ( fractional graph theory ) شناخته می شود. این موضوع تعمیمی از رنگ بندی گراف معمولی می باشد. در رنگ بندی گراف سنتی، هر رأس از گراف به رنگ های متعددی درآورده می شود و رأس های مجاور ( به این معنا که به وسیلهٔ یالی به هم متصل شده اند ) باید به رنگ های متمایزی درآورده شوند. در یک رنگ بندی بخشی، یک مجموعه خاص از رنگ ها به هر رأس گراف نسبت داده می شود. در این مسئله هم رأس های مجاور نباید دارای رنگ های مشابه باشند. رنگ بندی بخشی را می توان به عنوان راحت سازی برنامه نویسی خطی یا ( linear programming relaxation ) در نظر گرفت. در واقع با رویکرد برنامه نویسی خطی، مسائل مربوط به رنگ بندی بخشی نسبت به رنگ بندی سنتی بسیار بیشتر قابل پاسخگویی می باشد.
یک رنگ بندی b - fold یا b - لایه یک گراف G، یک نسبت دهی از اندازه b به رأس های گراف است به طوری که رئوس مجاور مجموعه متمایزی داشته باشند. یک رنگ بندی a:b تا رنگ بندی از میان رنگ های مجاز می باشد. یک عدد رنگی b - لایه Xb ( G ) ، حداقل تعداد a می باشد به طوری که یک رنگ بندی a: b موجود باشد. عدد رنگی بخشی ( Xf ( G به صورت زیر تعریف می شود:
توجه کنید که این حد به علت اینکه ( Xb ( G زیر - افزاینده ( subadditive ) است موجود می باشد، به این معنا که ( Xa+b ( G ) ≤ Xa ( G ) + Xb ( G.
یک عدد رنگی بخشی می تواند به صورت یک عبارت احتمالی مطرح شود. ( Xf ( G کوچک ترین k است به صورتی که یک توزیع احتمال بر روی مجموعه مستقل independent sets ) G ) وجود داشته باشد، به طوری که برای هر رأس v، مجموعه مستقل S از توزیع احتمال گفته شده استخراج شود، با این شرط که:
Pr ( v ∈ S ) ≥ 1 k
برخی از ویژگی های ( Xf ( G:
χ f ( G ) ≥ n ( G ) / α ( G )
و
ω ( G ) ≤ χ f ( G ) ≤ χ ( G )
در اینجا ( n ( G، مرتبه G و ( α ( G عدد استقلال ( independence number ) و ω ( G ) عدد دسته ( number Clique ) و X ( G ) عدد رنگی می باشد.
یک عدد رنگی بخشی Xf ( G ) از یک گراف G می تواند به عنوان یک راه حل برای یک برنامه نویسی خطی در نظر گرفته شود. اگر ( G ) Ι مجموعه همه مجموعه های مستقل G باشد، ( G, x ) Ι مجموعه همه آن مجموعه های مستقل که شامل رأس x است باشد و برای هر مجموعه مستقل I یک متغیر غیر منفی و حقیقی xI تعریف کنیم آنگاه Xf ( G ) ) حداقل مقدار
wiki: رنگبندی بخشی گراف