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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

رنگبندی بخشی(Fractional Coloring)

رنگ‎بندی ۵:۲ یک گراف ددکاهدرال (Dodecahedral Graph)

رنگ‎بندی بخشی موضوعی جدید در شاخه تئوری گراف (graph theory) است که به نام تئوری گراف بخشی (fractional graph theory) شناخته می‎شود. این موضوع تعمیمی از رنگ‎بندی گراف معمولی می‎باشد. در رنگ‎بندی گراف سنتی، هر رأس از گراف به رنگ‎های متعددی در آورده می‎شود و رأس‎های مجاور (به این معنا که به وسیله‎ی یالی به هم متصل شده‎اند) باید به رنگ‎های متمایزی در آورده شوند. در یک رنگ‎بندی بخشی، یک مجموعه خاص از رنگ‎ها به هر رأس گراف نسبت داده می‎شود. در این مسأله هم رأس‎های مجاور نباید دارای رنگ‎های مشابه باشند. رنگ‎بندی بخشی را می‎توان به عنوان راحت‎سازی برنامه‎نویسی خطی یا (linear programming relaxation) در نظر گرفت. در واقع با رویکرد برنامه‎نویسی خطی، مسائل مربوط به رنگ‎بندی بخشی نسبت به رنگ‎بندی سنتی بسیار بیشتر قابل پاسخگویی می‎باشد.

تعریف[ویرایش]

یک رنگ بندی ۱:۳ در یک حلقه با ۵ رأس و یک رنگ بندی ۲:۶

یک رنگ‎بندی b-fold یا b-لایه یک گراف G، یک نسبت دهی از اندازه b به رأس‎های گراف است به طوری که رئوس مجاور مجموعه‎ متمایزی داشته باشند. یک رنگ‎بندی a:b تا رنگ‎بندی از میان رنگ‎های مجاز می‎باشد. یک عدد رنگی b-لایه Xb(G)، حداقل تعداد a می‎باشد به طوری که یک رنگ بندی a: b موجود باشد. عدد رنگی بخشی (Xf(G به صورت زیر تعریف می‎شود:

\chi_{f}(G) = \lim_{b \to \infty}\frac{\chi_{b}(G)}{b} = \inf_{b}\frac{\chi_{b}(G)}{b}

توجه کنید که این حد به علت اینکه (Xb(G زیر-افزاینده (subadditive) است موجود می‎باشد، به این معنا که (Xa+b(G) ≤ Xa(G) + Xb(G.

یک عدد رنگی بخشی می‎تواند به صورت یک عبارت احتمالی مطرح شود. (Xf(G کوچکترین k است به صورتی که یک توزیع احتمال بر روی مجموعه مستقل independent sets) G) وجود داشته باشد، به طوری که برای هر رأس v،مجموعه مستقل S از توزیع احتمال گفته شده استخراج شود، با این شرط که:

\Pr(v\in S) \geq \frac{1}{k}

برخی از ویژگی‎های (Xf(G:

\chi_f(G)\ge n(G)/\alpha(G)

و

\omega(G) \le \chi_f(G) \le \chi(G)

در اینحجا (n(G، مرتبه G و (α(G عدد استقلال (independence number) و ω(G) عدد دسته (number Clique) و X(G) عدد رنگی می‎باشد.

فرمول بندی برنامه نویسی خطی[ویرایش]

یک عدد رنگی بخشی Xf(G) از یک گراف G می‎تواند به عنوان یک راه حل برای یک برنامه نویسی خطی در نظر گرفته شود. اگر (G)Ι مجموعه همه مجموعه‌های مستقل G باشد، (G,x)Ι مجموعه همه آن مجموعه‎های مستقل که شامل رأس x است باشد و برای هر مجموعه مستقل I یک متغیر غیر منفی و حقیقی xI تعریف کنیم آنگاه Xf(G)) حداقل مقدار

\sum_{I\in\mathcal{I}(G)} x_I\,

با توجه به برقرار بودن عبارت زیر است.

\sum_{I\in\mathcal{I}(G,x)} x_I \ge 1 برای هر رأس x

دوگانگی (dual) این برنامه خطی، عدد دسته بخشی (fractional clique number یا راحت سازی (relaxation) مستدلات مفهوم صحیح عدد دسته) را محاسبه می‎کند. این یک نسبت دادن وزن به رئوس است به طوری که مجموع وزن نسبت داده شده به هر مجموعه مستقل حداکثر ۱ باشد. قضیه دوگانگی قوی (strong duality) در برنامه‎نویسی خطی، تضمین می‎کند که بهینه‎ترین راه حل‎های هر دو برنامه خطی مقدار یکسان دارند؛ حال آن که ممکن است هر برنامه خطی دارای اندازه تعداد رئوس G نمایی باشند و محاسبه عدد رنگی بخشی گراف دارای سختی NP [۱] باشد. این موضوع و مسأله رنگ‎بندی بخشی یال‎های یک گراف که می‎تواند از مرتبه نمایی باشد، متمایز هستند. این موضوع یک نتیجه‎گیری مستقیم از قضیه تطبیق پلیتپ ادموند (Edmonds’s matching polytope) می‎باشد.[۲][۳]

کاربردها[ویرایش]

یکی از کاربردهای رنگ‎بندی بخشی گراف شامل زمانبندی فعالیت‎‎ها می‎باشد. در این مورد، گراف G یک گراف ناسازگاری است. یک یال در G بین رئوس v و u نشان می‎دهد که v و u نمی‎توانند همزمان فعال باشند. به عبارتی دیگر، مجموعه رئوس که به صورت همزمان فعال هستند، می‎بایستی یک مجموعه مستقل در گراف G باشند. یک رنگ‎بندی بخشی گراف بهینه در G کوتاه‎ترین زمانبندی ممکن را تولید می‎کند به طوری که هر رأس در مجموع برای حداقل ۱ واحد زمانی فعال باشد و در هر نقطه از زمان، مجموع رئوس فعال یک مجموعه مستقل باشد. اگر ما یک راه حل خطی برای برنامه خطی فوق داشته باشیم، ما به راحتی همه مجموعه‎های مستقل I را به صورت دلخواه پیمایش می‎کنیم. رئوسی که در I می‎باشند را برای مدت XI فعال در نظر می‎گیریم در حالی که رئوسی که در I نیستند را غیر فعال در نظر می‎گیریم. یک نمونه کاربرد واضح‎تر این است که مثلاً: هر رأس G یک انتقال رادیویی بی‎سیم را در یک ارتباط شبکه نشان دهد. یال‎های G تداخل در تبادلات رادیویی را نشان می‎دهند. هر انتقال رادیویی باید در مجموع به اندازه یک واحد زمانی فعال باشد. یک رنگ‎بندی بخشی گراف بهینه، یک زمانبندی با حداقل طول و بدون تداخل را به ما می‎دهد، به عبارت دیگر یک زمانبندی با حداکثر پهنای باند را به ما می‎دهد.

مقایسه با رنگ‎بندی سنتی گراف[ویرایش]

در مثال قبلی انتقال رادیویی، اگر لازم باشد که یک گره (رأس) از گراف به طور پیوسته و بدون قطع و وصل شدن، فعال باشد آنگاه رنگ‎بندی رئوس گراف به روش سنتی جواب بهینه را به ما می‎دهد. توضیح آنکه ابتدا باید رئوس با رنگ شماره ۱ به مدت ۱ واحد زمانی باید فعال باشند سپس رئوس با با رنگ شماره ۲ به مدت یک واحد زمانی فعال می‎شوند و به همین ترتیب ادامه می‎یابد. یادآور می‎شود که در هر نقطه از زمان مجموعه گره‎های فعال، یک مجموعه مستقل می‎باشد. به طور کلی، رنگ‎بندی بخشی گراف یک زمانبندی کوتاهتر به ما می‎دهد تا رنگ‎بندی غیر بخشی. یافتن یک زمانبندی کوتاهتر ممکن است اما به قیمت آنکه انتقال دهنده‌های رادیویی قابلیت قطع و وصل شدن بیش از یک بار را داشته باشند.

پانویس[ویرایش]

  1. Carsten Lund and Mihalis Yannakakis: "On the hardness of approximating minimization problems", J. ACM 41:5(1994), p. 960-981.
  2. Bruce Hajek and Galen Sasaki: "Link scheduling in polynomial time", IEEE Transactions on Information Theory 34:5(1988), p. 910-917.
  3. Schrijver, Alexander (2003). Combinatorial Optimization: Polyhedra and Efficiency. Berlin ; Heidelberg ; New York, N.Y.: Springer-Verlag. p. 474.ISBN 3540443894.

منابع[ویرایش]

Scheinerman, Edward R.; Ullman, Daniel H. (1997), Fractional graph theory, New York: Wiley-Interscience, ISBN 0-471-17864-0

Godsil, Chris; Royle, Gordon (2001), Algebraic Graph Theory, New York: Springer-Verlag, ISBN 0-387-95241-1