فن نظرية التلوين في الرسوم البيانية: خوارزميات التلوين وتطبيقاتها المتنوعة
DOI:
https://doi.org/10.65419/albahit.v5i4.165الكلمات المفتاحية:
تلوين الرسوم البيانية، العدد اللوني، خوارزمية DSATUR، الخوارزميات الجشعة، البرمجة الصحيحة، البحث المحظور، قابلية إعادة الإنتاج، الجدولةالملخص
يتمثل تلوين رؤوس الرسم البياني (Graph Vertex Coloring) في إسناد ألوان إلى الرؤوس بحيث تحصل الرؤوس المتجاورة على ألوان مختلفة، بينما يتمثل الهدف التحسيني للمسألة في تقليل عدد الألوان المستخدمة إلى أدنى حد ممكن. تقدم هذه المخطوطة مراجعة قائمة على أسس رياضية للمسألة، وعائلات خوارزمياتها، وتطبيقاتها في إعداد الجداول الزمنية، وتخصيص الترددات، وتخصيص السجلات، وجدولة الموارد.
وتعرّف الدراسة المعلمات الأساسية للرسوم البيانية، وتبرهن الحدود الرياضية الأولية، وتصحح شروط مبرهنة بروكس (Brooks’ Theorem) وتفسيرها، كما تميّز بين مسألة القرار ومسألة التحسين. وتتناول إجراءات التلوين الجشع ذات الترتيب الثابت، وخوارزمية ويلش–باول (Welsh–Powell)، وخوارزمية DSATUR، وأساليب البرمجة الصحيحة الدقيقة والفرع والتحديد (Branch-and-Bound)، والبحث المحظور (Tabu Search)، والأساليب التطورية.
كما تُعرض تعقيدات الخوارزميات مع مراعاة بنية البيانات وافتراضات التنفيذ. وقد تضمنت المسودة الأصلية مقارنات رقمية لخوارزميات طُبقت على رسوم بيانية وُصفت بأنها تتكون من 500 رأس وبكثافة مقدارها 0.5، إلى جانب ادعاءات أوسع بشأن زمن التنفيذ والأمثلية. إلا أن المسودة لم توفر ملفات الرسوم البيانية، أو البذور العشوائية، أو الشيفرات البرمجية، أو وصف الأجهزة المستخدمة، أو النتائج التفصيلية للتجارب، أو القيم المثلى المعتمدة والحدود الدنيا المثبتة. ولذلك، لا يمكن التحقق من تلك الأرقام بصورة مستقلة، ولم تُعتمد بوصفها نتائج تجريبية في هذه النسخة.
وبدلًا من ذلك، تقدم الورقة بروتوكولًا متكاملًا للتقييم، يعتمد على توثيق مصادر مجموعات الاختبار العامة، وإجراء تشغيلات مستقلة، والتحقق من صحة التلوين، وحساب فجوات الحلول مع مراعاة الحدود المثبتة، والإبلاغ عن النتائج بشفافية.
وتتمثل المساهمة التي تدعمها الأدلة في تقديم مراجعة نظرية متماسكة، وتصميم منهجي قابل لإعادة الإنتاج للمقارنات التجريبية المستقبلية؛ دون الادعاء بأن أي خوارزمية استدلالية تتفوق على جميع الخوارزميات الأخرى في مختلف الحالات
المراجع
1. Appel, K., & Haken, W. (1977a). Every planar map is four colorable. Part I: Discharging. Illinois Journal of Mathematics, 21(3), 429–490. https://doi.org/10.1215/ijm/1256049011
2. Appel, K., Haken, W., & Koch, J. (1977). Every planar map is four colorable. Part II: Reducibility. Illinois Journal of Mathematics, 21(3), 491–567. https://doi.org/10.1215/ijm/1256049012
3. Brélaz, D. (1979). New methods to color the vertices of a graph. Communications of the ACM, 22(4), 251–256. https://doi.org/10.1145/359094.359101
4. Brooks, R. L. (1941). On colouring the nodes of a network. Mathematical Proceedings of the Cambridge Philosophical Society, 37(2), 194–197. https://doi.org/10.1017/S030500410002168X
5. Chaitin, G. J. (1982). Register allocation and spilling via graph coloring. ACM SIGPLAN Notices, 17(6), 98–105. https://doi.org/10.1145/872726.806984
6. Cranston, D. W., & Rabern, L. (2014). Brooks’ theorem and beyond [Preprint]. arXiv. https://arxiv.org/abs/1403.0479
7. DIMACS. (n.d.). Implementation challenges: Second challenge (1992–1993): NP-hard problems: Maximum clique, graph coloring, and satisfiability. https://dimacs.rutgers.edu/programs/implementation-challenges/
8. Galinier, P., & Hao, J.-K. (1999). Hybrid evolutionary algorithms for graph coloring. Journal of Combinatorial Optimization, 3, 379–397. https://doi.org/10.1023/A:1009823419804
9. Galinier, P., & Hertz, A. (2006). A survey of local search methods for graph coloring. Computers & Operations Research, 33(9), 2547–2562. https://doi.org/10.1016/j.cor.2005.07.028
10. Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. W. H. Freeman.
11. Garey, M. R., Johnson, D. S., & Stockmeyer, L. (1976). Some simplified NP-complete graph problems. Theoretical Computer Science, 1(3), 237–267. https://doi.org/10.1016/0304-3975(76)90059-1
12. Hale, W. K. (1980). Frequency assignment: Theory and applications. Proceedings of the IEEE, 68(12), 1497–1514. https://doi.org/10.1109/PROC.1980.11899
13. Hertz, A., & de Werra, D. (1987). Using tabu search techniques for graph coloring. Computing, 39, 345–351. https://doi.org/10.1007/BF02239976
14. Jensen, T. R., & Toft, B. (2011). Graph coloring problems. Wiley.
15. Johnson, D. S., & Trick, M. A. (Eds.). (1996). Cliques, coloring, and satisfiability: Second DIMACS implementation challenge (DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 26). American Mathematical Society. https://doi.org/10.1090/dimacs/026
16. Lewis, R. (2016). A guide to graph colouring: Algorithms and applications. Springer. https://doi.org/10.1007/978-3-319-25730-3
17. Lewis, R. M. R. (2018). A general-purpose hill-climbing method for graph colouring. Journal of the Operational Research Society, 69, 810–816. https://doi.org/10.1057/s41274-017-0239-4
18. Malaguti, E., & Toth, P. (2010). A survey on vertex coloring problems. International Transactions in Operational Research, 17(1), 1–34. https://doi.org/10.1111/j.1475-3995.2009.00696.x
19. Vizing, V. G. (1964). On an estimate of the chromatic class of a p-graph. Diskret. Analiz, 3, 25–30.
20. Welsh, D. J. A., & Powell, M. B. (1967). An upper bound for the chromatic number of a graph and its application to timetabling problems. The Computer Journal, 10(1), 85–86. https://doi.org/10.1093/comjnl/10.1.85
21. Zuckerman, D. (2007). Linear degree extractors and the inapproximability of max clique and chromatic number. Theory of Computing, 3(6), 103–128. https://doi.org/10.4086/toc.2007.v003a006
