تلوين المسار

في نظرية الرسوم البيانية ، يُعدّ تلوين المسارات نوعًا من أنواع تلوين الرسوم البيانية ، حيث تُخصّص ألوان (أو أطوال موجية ) لمجموعة من المسارات في الرسم البياني، بحيث يحصل أي مسارين يشتركان في حافة واحدة على لونين مختلفين. والهدف عادةً هو تقليل عدد الألوان المستخدمة. وقد استُلهم تلوين المسارات من مشكلة تخصيص عرض النطاق الترددي الضوئي لطلبات الاتصال في الشبكات الضوئية بالكامل التي تستخدم تقنية تعدد الإرسال بتقسيم الطول الموجي (WDM). ^{[ 1 ]}

قد يشير تلوين المسار إما إلى مشكلة WA أو مشكلة RWA .

في مسألة تخصيص الطول الموجي (أو مسألة WA )، تتكون المدخلات من رسم بياني${\displaystyle G}$ومجموعة (متعددة) من المسارات${\displaystyle P}$تم تعريفها مسبقًا على${\displaystyle G}$المهمة هي تعيين ألوان للمسارات في${\displaystyle P}$بحيث يكون أي مسارين يشتركان في حافة في${\displaystyle G}$^{[ 2 ]}​

هذه الصيغة تعادل تلوين رؤوس الرسم البياني للصراع لـ${\displaystyle P}$، والتي تحتوي على رأس واحد لكل مسار في${\displaystyle P}$ووجود حافة بين رأسين عندما تشترك المسارات المتناظرة في حافة واحدة.${\displaystyle G}$[ ^{1 ]​}

في مسألة توجيه وتخصيص الطول الموجي (وتُعرف أيضًا بمسألة توجيه الطول الموجي أو مسألة RWA )، يتكون المدخل من رسم بياني${\displaystyle G}$ومجموعة من الطلبات${\displaystyle R}$حيث يمثل كل طلب زوجًا من العقد المراد توصيلها. بالنسبة لكل طلب، يجب على الخوارزمية اختيار مسار يربط بين نقطتي النهاية وتعيين لون لهذا المسار، بحيث تحصل المسارات التي تشترك في حافة واحدة على ألوان مختلفة. ^{[ 2 ]}

وبالتالي، تنقسم مشكلة RWA إلى مشكلتين فرعيتين: مشكلة التوجيه المتمثلة في اختيار مسار لكل طلب، ومشكلة WA المتمثلة في تلوين المسارات الناتجة. ^{[ 1 ]}

في الرسوم البيانية العامة حيث توجد مسارات متعددة بين أزواج العقد، تتفاعل هذه المشكلات الفرعية، مما يجعل RWA أكثر تعقيدًا من WA وحده.

في الشبكات الشجرية ، يكون المسار الذي يربط أي عقدتين فريدًا. لذا، تصبح مسألة التوجيه الفرعية بسيطة، ويختزل توجيه الطول الموجي في الأشجار إلى مسألة WA. ^{[ 1 ]} لهذا السبب، غالبًا ما تركز الأبحاث المتعلقة بتلوين المسارات على طوبولوجيات الأشجار.

يُعرَّف حمل الحافة بأنه عدد المسارات التي تمر عبرها، وحمل مجموعة من المسارات .${\displaystyle L}$يمثل هذا الحد الأقصى للحمل على جميع الحواف. ويحدد هذا الحمل الحد الأدنى لعدد الألوان المطلوبة. ^{[ 1 ]}

يمكن دراسة تلوين المسار في كل من الإعدادات غير الموجهة والإعدادات ثنائية الاتجاه (الموجهة): ^{[ 2 ]}

• في تلوين المسار غير الموجه ، الرسم البياني${\displaystyle G}$المسار غير موجه، والمسارات غير موجهة. يتعارض مساران إذا اشتركا في أي حافة.
• في تلوين المسارات الموجهة ، يكون الرسم البياني ثنائي الاتجاه (حيث يتم استبدال كل حافة غير موجهة بحافتين موجهتين في اتجاهين متعاكسين)، وتكون المسارات موجهة. ويتعارض مساران موجهان فقط إذا اشتركا في حافة موجهة في نفس الاتجاه.

تُحاكي النماذج الموجهة الشبكات التي يكون لكل وصلة ألياف مادية سعة منفصلة لكل اتجاه إرسال.

يُعدّ تلوين المسارات مسألةً صعبةً من نوع NP-hard لكلٍّ من الشبكات الحلقية غير الموجهة والشبكات الحلقية ثنائية الاتجاه . بالنسبة للأشجار: ^{[ 1 ] [ 2 ]}

• تلوين المسار غير الموجه في النجوم يعادل تلوين حواف الرسوم البيانية المتعددة ، وبالتالي فهو صعب من نوع NP.
• يُعد تلوين المسار الموجه مسألة صعبة من نوع NP حتى بالنسبة للأشجار الثنائية ثنائية الاتجاه.
• يمكن حل مشكلة تلوين المسارات على النحو الأمثل في وقت متعدد الحدود للأشجار ذات الدرجة المحدودة أو عندما يكون عدد المسارات التي تلامس أي عقدة${\displaystyle O((\log n)^{1-\varepsilon })}$بالنسبة للبعض${\displaystyle \varepsilon >0}$.

بالنسبة للأشجار غير الموجهة، تحقق خوارزمية جشعة تستخدم تلوين حواف الرسوم البيانية المتعددة نسبة تقريب تبلغ 3/2، وهي نسبة دقيقة. ^{[ 1 ]} كما توجد خوارزمية أخرى بنسبة تقريب مطلقة تبلغ 4/3 ونسبة تقريب تقاربية تبلغ 1.1. ^{[ 2 ]}

بالنسبة للأشجار ثنائية الاتجاه، تحقق الخوارزميات الجشعة الحتمية ما يلي:${\displaystyle 5L/3}$الحد الأعلى للألوان المستخدمة في مسارات التحميل${\displaystyle L}$تعمل الخوارزميات العشوائية على تحسين ذلك إلى${\displaystyle 7L/5+o(L)}$ألوان الأشجار الثنائية ثنائية الاتجاه. ^{[ 1 ]}

يرتبط تلوين المسارات ارتباطًا وثيقًا بجدولة المكالمات ، التي تعمم المشكلة بإدخال متطلبات عرض النطاق الترددي ومدة المكالمات. عندما تساوي جميع متطلبات عرض النطاق الترددي وسعات الحافة ومدة المكالمات 1، فإن جدولة المكالمات تختزل إلى مشكلة RWA، حيث تتوافق الألوان مع الفترات الزمنية. ^{[ 2 ]}

• مجموعة من مسائل التحسين من نوع NP من تأليف فيجو كان (المسألة: تلوين المسار الأدنى)