التلوين الجزئي

التلوين الجزئي هو موضوع في فرع من نظرية الرسوم البيانية يُعرف بنظرية الرسوم البيانية الجزئية . وهو تعميم للتلوين التقليدي للرسوم البيانية . في التلوين التقليدي، يُخصص لون لكل رأس في الرسم البياني، ويجب أن تُخصص ألوان مختلفة للرؤوس المتجاورة - أي تلك المتصلة بحواف. أما في التلوين الجزئي، فتُخصص مجموعة من الألوان لكل رأس في الرسم البياني. ويبقى شرط تجاور الرؤوس قائمًا، فإذا كان رأسان متصلين بحافة، فلا يجب أن يكون لهما لون مشترك.

يمكن اعتبار تلوين الرسوم البيانية الجزئي بمثابة تبسيط لبرمجة الرسوم البيانية التقليدية باستخدام البرمجة الخطية. في الواقع، تُعدّ مسائل التلوين الجزئي أكثر ملاءمةً لمنهج البرمجة الخطية من مسائل التلوين التقليدية.

التلوين من الرتبة b للرسم البياني G هو تخصيص مجموعات بحجم b لرؤوس الرسم البياني بحيث تحصل الرؤوس المتجاورة على مجموعات منفصلة . التلوين من الرتبة a : b هو تلوين من الرتبة b باستخدام a لونًا متاحًا. ويمكن تعريفه بشكل مكافئ على أنه تشاكل مع الرسم البياني Kneser KG _{a , b} . يُعرف هذا التلوين بالعدد اللوني من الرتبة b.${\displaystyle \chi _{b}(G)}$هو أصغر عدد لوني a بحيث يوجد تلوين a : b . لاحظ أن العدد اللوني المنتظم${\displaystyle \chi (G)}$هو بالضبط${\displaystyle \chi _{1}(G)}$.

العدد اللوني الجزئي${\displaystyle \chi _{f}(G)}$يُعرَّف بأنه:

${\displaystyle \chi _{f}(G)=\lim _{b\to \infty }{\frac {\chi _{b}(G)}{b}}=\inf _{b}{\frac {\chi _{b}(G)}{b}}}$

لاحظ أن النهاية موجودة لأن${\displaystyle \chi _{b}(G)}$وهي شبه جمعية ، بمعنى:${\displaystyle \chi _{a+b}(G)\leq \chi _{a}(G)+\chi _{b}(G).}$

يمكن تعريف العدد اللوني الجزئي بشكل مكافئ من حيث الاحتمالات.${\displaystyle \chi _{f}(G)}$هو أصغر قيمة لـ k التي يوجد من أجلها توزيع احتمالي على المجموعات المستقلة لـ G بحيث يكون لكل رأس v ، بالنظر إلى مجموعة مستقلة S مسحوبة من التوزيع:

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

لدينا:

${\displaystyle \chi _{f}(G)\geq {\frac {n(G)}{\alpha (G)}},}$

مع المساواة بالنسبة للرسوم البيانية المتعدية على الرؤوس ، حيث n ( G ) هي رتبة G ، و α ( G ) هو عدد الاستقلال . ^{[ 1 ]}

علاوة على ذلك:

${\displaystyle \omega (G)\leq \chi _{f}(G)\leq \chi (G),}$

حيث ω ( G ) هو عدد الزمر ، و${\displaystyle \chi (G)}$هو العدد اللوني .

علاوة على ذلك، فإن العدد اللوني الكسري يقارب العدد اللوني ضمن عامل لوغاريتمي، ^{[ 2 ]} في الواقع:

${\displaystyle {\frac {\chi (G)}{1+\ln \alpha (G)}}\leq \chi _{f}(G)\leq {\frac {\chi _{b}(G)}{b}}\leq \chi (G).}$

تُقدّم رسوم كنيسر البيانية أمثلةً حيث:${\displaystyle \chi (G)/\chi _{f}(G)}$كبيرة بشكل تعسفي، لأن:${\displaystyle \chi (KG_{m,n})=m-2n+2,}$بينما${\displaystyle \chi _{f}(KG_{m,n})={\tfrac {m}{n}}.}$

العدد اللوني الجزئي${\displaystyle \chi _{f}(G)}$يمكن الحصول على مصفوفة الرسم البياني G كحل لبرنامج خطي . ليكن${\displaystyle {\mathcal {I}}(G)}$لتكن G مجموعة جميع المجموعات المستقلة في G ، ولتكن${\displaystyle {\mathcal {I}}(G,x)}$لتكن I مجموعة جميع المجموعات المستقلة التي تتضمن الرأس x . لكل مجموعة مستقلة I ، عرّف متغيرًا حقيقيًا غير سالب x ∈ _I.${\displaystyle \chi _{f}(G)}$هي القيمة الدنيا لـ:

${\displaystyle \sum _{I\in {\mathcal {I}}(G)}x_{I},}$

رهناً بما يلي:

${\displaystyle \sum _{I\in {\mathcal {I}}(G,x)}x_{I}\geq 1}$

لكل رأس${\displaystyle x}$.

يحسب البرنامج الثنائي لهذا البرنامج الخطي "عدد الزمر الكسري"، وهو تبسيط لمفهوم عدد الزمر الصحيح في الأعداد النسبية . أي، ترجيح رؤوس الرسم البياني G بحيث يكون الوزن الإجمالي المخصص لأي مجموعة مستقلة 1 على الأكثر . تضمن نظرية الازدواجية القوية للبرمجة الخطية أن الحلول المثلى لكلا البرنامجين الخطيين لها نفس القيمة. مع ذلك، تجدر الإشارة إلى أن حجم كل برنامج خطي قد يكون أُسّيًا بالنسبة لعدد رؤوس G ، وأن حساب العدد اللوني الكسري للرسم البياني هو مسألة صعبة الحل (NP-hard) . ^{[ 3 ]} وهذا يتناقض مع مشكلة تلوين حواف الرسم البياني جزئيًا، والتي يمكن حلها في وقت متعدد الحدود. هذه نتيجة مباشرة لنظرية إدموندز لمتعدد السطوح المطابق . ^{[ 4 ] [ 5 ]}

تشمل تطبيقات تلوين الرسوم البيانية الجزئية جدولة الأنشطة . في هذه الحالة، يكون الرسم البياني G رسمًا بيانيًا للتعارض : يشير وجود حافة في G بين العقدتين u و v إلى أنه لا يمكن أن تكون u و v نشطتين في الوقت نفسه. بعبارة أخرى، يجب أن تكون مجموعة العقد النشطة في الوقت نفسه مجموعة مستقلة في الرسم البياني G.

يُوفّر تلوين الرسم البياني الجزئي الأمثل في G أقصر جدول زمني ممكن، بحيث يكون كل عقدة نشطة لمدة وحدة زمنية واحدة على الأقل إجمالاً، وتكون مجموعة العقد النشطة في أي لحظة مجموعة مستقلة. إذا كان لدينا حل x للبرنامج الخطي أعلاه، فإننا ببساطة نجتاز جميع المجموعات المستقلة I بترتيب عشوائي. لكل I ، نجعل العقد في I نشطة لمدة${\displaystyle x_{I}}$وحدات زمنية؛ وفي الوقت نفسه، تكون كل عقدة ليست في المجموعة I غير نشطة.

بصورة أكثر تحديدًا، قد يُمثل كل عقدة في الرسم البياني G عملية إرسال لاسلكي في شبكة اتصالات لاسلكية؛ وتمثل حواف الرسم البياني G التداخل بين عمليات الإرسال اللاسلكي. يجب أن تكون كل عملية إرسال لاسلكي نشطة لمدة وحدة زمنية واحدة إجمالاً؛ يوفر التلوين الأمثل للرسم البياني الجزئي جدولًا زمنيًا بأقصر طول (أو، بشكل مكافئ، جدولًا زمنيًا بأقصى عرض نطاق) خالٍ من التعارضات.

• شاينرمان، إدوارد ر.؛ أولمان، دانيال هـ. (1997)، نظرية الرسم البياني الكسري ، نيويورك: وايلي-إنترساينس، ISBN 978-0-471-17864-4.
• جودسيل، كريس ؛ رويل، جوردون (2001)، نظرية الرسم البياني الجبرية ، نيويورك: سبرينغر-فيرلاغ، ISBN 978-0-387-95241-3.

• المطابقة الجزئية