دراسة لإيجاد العدد اللوني الضلعي المستمر وخوارزمية تلوين البيانات P

الملخص

كما هو معروف فإن مسألة تلوين البيان بأقلَّ عدد من الألوان مسألة معقّدة من الصف NP، وتتلخص في كيفيّة تلوين عقد بيان بأقلَّ عدد من الألوان بحيث لا يُخصّص لأيَّ عقدتين متجاورتين اللون نفسه أو كيف يتمُّ تلوين أضلاع بيان بأقلَّ عدد من الألوان بحيث لا يكون لأيَّ ضلعين متجاورين اللون نفسه، ولأنَّ تلوين الأضلاع لا يعطي دوماً التلوين المناسب المُمثل لحلَّ مشكلة ما ظهرت مسألة الحصول على التلوين الضلعي المستمر، وقد تمَّ أخذ هذه المسألة من مسألة مفتوحة لم تُدرس مسبقاً [1]. وانطلاقاً من كونها مسألة مفتوحة واستكمالاً للبحث

في هذا المجال، قدّمنا في هذه الورقة البحثيّة دراسة جديدة تتضمن دراسة تلوين البيانات P  في البداية قمنا بإنتاج البيانات P  باستعمال الجداء الديكارتي للمسارين  ثمَّ قمنا بدراسة تلوين هذه البيانات ابتداءً من التلوين الضلعي المستمر، دراستنا تكون وفق ثلاثَ حالات حسب مرتبة كلّا من  كلّ حالة تتضمّن وضع خوارزمية التلوين الضلعي المستمر الأمثل، وتحديد الصيغة العامة للعدد اللوني الضلعي المستمر بشكل دقيق، وعرض بعض الأمثلة التوضيحية بالإضافة إلى برهان قابلية تحقيق البيانات P  للتلوين الضلعي المستمر، ثمَّ توصلنا إلى نتائج يمكن من خلالها تصنيف هذه البيانات من حيث قابليتها للتلوين الضلعي المستمر بشكل مباشر، فضلاً عن وضع الصيغة العامة للعدد اللوني الضلعي المستمر للبيان P  ككل حسب مرتبته nm، انتقلنا بعد ذلك لدراسة تلوين الأضلاع حيث قمنَّا باستنتاج العدد اللوني اللازم لتلوين الأضلاع، بالإضافة إلى دراسة تلوين العقد حيث اقترحنا خوارزمية التلوين وتمكنَّا من وضع العدد اللوني اللازم لتلوين العقد واختتمنا البحث ببعض الأمثلة التوضيحية، وبهذه الحالة أصبح لدينا دراسة متكاملة تتضمن تطبيق جميع أنواع التلوين على البيانات P .