خوارزمية تحسين الألوان

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

ظهر مفهوم تحسين الألوان لأول مرة في برنامج ستيفن إتش. أونغر GIT الخاص بتماثل الرسوم البيانية، حيث يُطلق عليه اسم طريقة التمديد . ^{[ 2 ]} ووُصف مرة أخرى، مباشرة بعد ذلك، في ورقة بحثية في الكيمياء. ^{[ 3 ]}

تأخذ الخوارزمية رسمًا بيانيًا كمدخل${\displaystyle G}$مع${\displaystyle n}$يتم ذلك على شكل تكرارات، وفي كل تكرار يتم إنتاج تلوين جديد للرؤوس. بشكل رسمي، " التلوين " هو دالة من رؤوس هذا الرسم البياني إلى مجموعة معينة (من "الألوان"). في كل تكرار، نحدد سلسلة من تلوينات الرؤوس.${\displaystyle \lambda _{i}}$على النحو التالي:

• ${\displaystyle \lambda _{0}}$هذا هو التلوين الأولي. إذا كان الرسم البياني غير مُصنَّف، فإن التلوين الأولي يُعيِّن لونًا عاديًا.${\displaystyle \lambda _{0}(v)}$لكل رأس${\displaystyle v}$إذا كان الرسم البياني مُصنَّفًا،${\displaystyle \lambda _{0}}$هو تسمية الرأس${\displaystyle v}$.
• لجميع الرؤوس${\displaystyle v}$، نحن نحدد${\displaystyle \lambda _{i+1}(v)=\left(\lambda _{i}(v),\{\{\lambda _{i}(w)\mid w{\text{ is a neighbor of }}v\}\}\right)}$.

بمعنى آخر، اللون الجديد للرأس${\displaystyle v}$هو الزوج المُشكّل من اللون السابق ومجموعة ألوان جيرانه. تستمر هذه الخوارزمية في تحسين التلوين الحالي. عند نقطة معينة، تستقر، أي${\displaystyle \lambda _{i+1}(u)=\lambda _{i+1}(v)}$إذا وفقط إذا${\displaystyle \lambda _{i}(u)=\lambda _{i}(v)}$يُطلق على هذا التلوين النهائي اسم التلوين الثابت .

يمكن استخدام تحسين الألوان كإجراء فرعي لحل مشكلة حسابية مهمة : تماثل الرسوم البيانية . في هذه المشكلة، لدينا رسمان بيانيان كمدخلات.${\displaystyle G,H}$ومهمتنا هي تحديد ما إذا كانا متماثلين . وهذا يعني بشكل غير رسمي أن الرسمين البيانيين متطابقان حتى إعادة تسمية الرؤوس.

لاختبار ما إذا${\displaystyle G}$و${\displaystyle H}$إذا كان الرسمان البيانيان متماثلين، فيمكننا تجربة ما يلي: إجراء تحسين الألوان على كليهما. إذا كانت الألوان المستقرة الناتجة مختلفة، فهذا يعني أن الرسمين البيانيين غير متماثلين. مع ذلك، قد ينتج نفس اللون المستقر رغم عدم تماثل الرسمين البيانيين؛ انظر أدناه.

من السهل أن نرى أنه إذا تم إعطاء تحسين اللون${\displaystyle n}$باستخدام الرسم البياني للرؤوس كمدخل، يتم إنتاج تلوين مستقر بعد مدة لا تتجاوز${\displaystyle n-1}$تكرارات. وعلى العكس من ذلك، توجد رسوم بيانية يتحقق فيها هذا الحد. ^{[ 4 ]} وهذا يؤدي إلى${\displaystyle O((n+m)\log n)}$التنفيذ حيث${\displaystyle n}$يمثل عدد الرؤوس و${\displaystyle m}$عدد الحواف. ^{[ 5 ]} وقد ثبت أن هذا التعقيد هو الأمثل في ظل افتراضات معقولة. ^{[ 6 ]}

نقول إن رسمين بيانيين${\displaystyle G}$و${\displaystyle H}$ يتم تمييزها عن طريق تحسين الألوان إذا أنتجت الخوارزمية مخرجات مختلفة على${\displaystyle G}$ كما هو الحال في${\displaystyle H}$توجد أمثلة بسيطة لرسوم بيانية لا يمكن تمييزها بتحسين الألوان. على سبيل المثال، لا يميز هذا الأسلوب بين دورة طولها 6 وزوج من المثلثات (المثال V.1 في ^{[ 7 ]} ). مع ذلك، يتميز هذا الأسلوب بقوة كبيرة، إذ يمكنه تحديد رسم بياني عشوائي بشكل شبه مؤكد تقريبًا. ^{[ 8 ]} بل وأكثر من ذلك، فقد ثبت أنه مع${\displaystyle n}$مع ازدياد عدد الرسوم البيانية، تتناقص نسبة الرسوم البيانية التي لا يتم تحديدها بواسطة تحسين الألوان بشكل أُسّي.${\displaystyle n}$[ ^{9 ]​}

بالنسبة للرسمين البيانيين${\displaystyle G}$و${\displaystyle H}$إذا كان عدد الرؤوس متساوياً، فإن الشروط التالية متكافئة:

• ${\displaystyle G}$و${\displaystyle H}$لا يمكن تمييزها عن طريق تحسين الألوان.
• الحد الأدنى لقواعد التليف لـ${\displaystyle G}$و${\displaystyle H}$متماثلة الشكل.
• ${\displaystyle G}$و${\displaystyle H}$متماثلة جزئياً . ^{[ 10 ] [ 11 ]}
• ${\displaystyle G}$و${\displaystyle H}$يكون لها تقسيم عادل مشترك وبسيط .
• ${\displaystyle G}$و${\displaystyle H}$^{[ 12 ]} لها نفس الغطاء العالمي .
• لجميع الأشجار${\displaystyle T}$يوجد عدد متساوٍ من التشاكلات من${\displaystyle T}$ل${\displaystyle G}$كما هو الحال من${\displaystyle T}$ل${\displaystyle H}$[ ^{13 ]​}
• ${\displaystyle G}$و${\displaystyle H}$لا يمكن التمييز بينهما بواسطة الجزء المتغير من منطق الرتبة الأولى مع العد . ^{[ 14 ]}
• أي شبكة عصبية بيانية لتمرير الرسائل ستقوم برسم خريطة${\displaystyle G}$و${\displaystyle H}$للحصول على نفس الناتج، إذا كانت ميزات عقدة الإدخال هي الألوان الأولية${\displaystyle \lambda _{0}}$[ ^{15 ] [ 16 ]​}
• أي خوارزمية مجهولة الهوية متزامنة مع تمرير رسائل البث/صندوق البريد والتي يعتمد فيها المدخل على اللون فقط، ستنتج مخرجًا يعتمد، مرة أخرى، على اللون الأولي فقط. ^{[ 17 ]}