خريطة التلوين وقواعد Gröbner

هذه الصورة ملك لموقع mathscareers.org.uk الذي وافق مشكورا على إدراجها في هذه المقالة

الكاتب الأصلي: أسكوديرو هيرنانديس Escudeiro Hernandes
ترجمة: إيمان لكميتي

إستنادا إلى “نظرية الألوان الأربعة” فإن أربعة ألوان فقط كافية لتلوين خريطة دون أن يكون لمنطقتين متجاورتين نفس اللون. باستعمال كثيرات الحدود وأساسات غروبنر Gröbner نستطيع أن نبيّن فيما إذا كانت 3 ألوان كافية لتلوين خريطة مشابهة أو لا.

1. تلوين الخرائط

نظرية الألوان الأربعة¹ تنص على أن أية خريطة، سواء كانت مستوية أو كروية، يمكن أن تلون بأربعة ألوان دون أن يكون لمنطقتين متجاورتين نفس اللون. من السهل إيجاد أمثلة لخرائط لا يمكن أن تلوّن بثلاثة ألوان فقط، وأخرى نستطيع تلوينها بثلاثة ألوان. تقوم طريقة تحديد ما إذا كانت ثلاثة ألوان كافية لتلوين خريطة على تحليل جملة معادلات كثيرات حدود مرتبطة بالخريطة. كل لون مرتبط بالجذر التكعيبي (العقدي) للوحدة، وكل منطقة يرمز إليها بالمتغير $x_i$ بحيث لا يمكنها إلا أن تأخذ واحدة من ثلاث قيم، أي واحدًا من الألوان. عندئذ يكون لدينا $x_i^3 - 1 = 0$ لكل منطقة.

من أجل المنطقتين $x_j$ و $x_k$ ، لدينا:

$0 = x_j^3 - x_k^3 = (x_j - x_k)(x_j^2 + x_j x_k + x_k^2).$

إذا كانت $x_j$ و $x_k$ منطقتين متجاورتين فلا يمكن لهما أن تكونًا من نفس اللون، ومن ثمّ $x_j \neq x_k$ . وهذا معناه $x_j^2 + x_j x_k + x_k^2 = 0$ . بهذه الطريقة، يمكن لخريطة من $n$ منطقة أن تُلون بثلاثة ألوان إذا وفقط إذا كانت جملة معادلات كثيرات الحدود أدناه تقبل على الأقل حلا:

$\left\{ \begin{array}{l} x_i^3 - 1 = 0, \\ x_j^2 + x_j x_k + x_k^2 = 0 \end{array}\right. \quad (1)$

حيث $i = 1, \ldots, n$ و $x_j$ و $x_k$ تمثل المناطق المتجاورة.

مثال 1

نعتبر الخريطة:

هل يمكن أن تلون بثلاثة ألوان؟

للإجابة على هذا السؤال يجب التحقق من أنه يمكن حل جملة المعادلات (1) مع $i = 1, \ldots, 9$ وأن يكون:

$(j,k) \in \{(1,2); (2,3); (2,6); (2,9); (3,4); (3,5); (3,6); (4,5); (5,6); (6,7); (6,9); (7,8); (7,9); (8,9)\}.$

2. جمل المعادلات المؤلفة من كثيرات الحدود

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

نرمز بـ $P(n)$ لمجموعة كثيرات الحدود ذات المعاملات العقدية (المركبة) والمتغيرات $x_1, \ldots, x_n$ .

عندما تكون مجموعة كثيرات الحدود $f_1, \ldots, f_r$ معطاة في $P(n)$ ، نعرف المثالي الذي تولّده بـــ:

$I = \langle f_1, \ldots, f_r \rangle = \{ h_1 f_1 + \ldots + h_r f_r : h_1, \ldots, h_r \in P(n) \}.$

نظرية للرياضي دافيد هيلبرت David Hilbert: تنص العلاقة (2) المسماة نظرية أصفار هيلبرت على أن الجملة $f_1 = \ldots = f_r = 0$ تقبل حلا عُقديا إذا وفقط إذا كان $1 \notin \langle f_1, \ldots, f_r \rangle$ . فكيف لنا التحقق من الشرط الأخير؟

من السهل التحقق من أن لجملتيْ المعادلات $f_1 = \ldots = f_r = 0$ و $g_1 = \ldots = g_s = 0$ ، حيث $f_i, g_j \in P(n)$ ، وتحققان الشرط

$\langle f_1, \ldots, f_r \rangle = \langle g_1, \ldots, g_s \rangle \quad (2)$

نفس الحل.

ولذلك، فإن إستراتيجية حل الجملة $f_1 = \ldots = f_r = 0$ تتوقف على إيجاد كثيرات حدود $g_1, \ldots, g_s$ تحقق الشرط (2)، وبواسطتها يمكن التحقق مما إذا كان عنصر $f \in P(n)$ ينتمي أو لا إلى المثالي $\langle f_1, \ldots, f_r \rangle$ والذي يكون فيه حسابه الحل المشترك أسهل من حسابه في الجملة الأصلية.

لقد تم إثبات الوجود النظري للمجموعة $G = \{g_1, \ldots, g_s\}$ خلال النصف الأول من القرن العشرين من طرف الرياضي ولفغانغ غروبنر Wolfgang Gröbner. وبعد سنوات، أنشأ تلميذه برونو بشيرغر Bruno Buchberger خوارزمية تسمح بتحديد هذه المجموعة. تسمى هذه المجموعات أساسات غروبنر، وتعتبر خوارزمية بشيرغر الحسابية من أهم أدوات الحساب الجبري.

إذا كان المثالي من الشكل $I = \langle f_1 \rangle$ فإن $f \in I$ إذا وفقط إذا كان $f = h_1 f_1$ . هذا يعني أن $f$ قابل للقسمة على $f_1$ . كما أن $f \in \langle f_1, \ldots, f_r \rangle$ إذا وفقط إذا كان، مما يوحي بشبيئ مشابه بخصوص قسمة $f$ على $f_1, \ldots, f_r$ .

في الواقع، يمكننا قسمة كثير حدود ذي عدة متغيرات على مجموعة منتهية من كثيرات الحدود، شرط أن تكون الحدود مرتبة بطريقة معينة.

3. أساسات غروبنر Gröbner

وحيد حد $m$ من $P(n)$ هو عنصر من الشكل $x_1^{a_1} \ldots x_n^{a_n}$ ، حيث $a_1, \ldots, a_n$ أعداد صحيحة موجبة أو معدومة. نرمز بـ $1$ لوحيد الحد $x_1^0 \ldots x_n^0$ . من بين الترتيبات $\leq$ المدرجة على أحاديات الحد لـ $P(n)$ التي تجعل تطبيق خوارزمية القسمة أمرًا ممكنا هي تلك التي تحقق العلاقتين $1 \leq m$ و $m_1.m \leq m_2.m$ عندما $m_1.m \leq m_2.m$ .

كمثال على ذلك هناك الترتيب المعجمي $\leq_{lex}$ حيث $x_1^{a_1} \ldots x_n^{a_n} \leq_{lex} x_1^{b_1} \ldots x_n^{b_n}$ بحيث $1 \leq i \leq n$ حيث $a_i < b_i$ و $a_j = b_j$ من أجل كل $j < i$ .

لنعتبر ترتيبا ما على وحيدات الحد. يسمى أكبر وحيد حد في كثير الحدود $f$ الحد المهيمن لـــ $f$ ، ويرمز له بـــ $\mathrm{lt}(f)$ (leading term).

أساس غروبنر لمثالي $I = \langle f_1, \ldots, f_r \rangle$ بالنسبة لترتيب معين لوحيدات الحد، هو تعريفا، مجموعة $G = \{g_1, \ldots, g_s\}$ من عناصر $I$ حيث كل حد مهيمن من كل عنصر من $I$ يقبل القسمة على الحد المهيمن من عنصر من $G$ . يمكننا إثبات أن كل أساس لغروبنر $G$ من $I$ مجموعة تحقق الشرط 2.

ونتيجة لذلك فإن $1 \in I$ إذا وفقط إذا وجد أساس لغروبنر في $I$ يحتوي ثابتا غير معدوم، لأن $1 \leq m$ من أجل كل حد $m$ من $P(n)$ .

على سبيل المثال، $G = \{f_1\}$ هو أساس غروبنر لـ $\langle f_1 \rangle$ ، من أجل كل ترتيب على وحيدات الحد. في حين أن $G = \{x+y+z-6, x-y+1, x+y-z\}$ ليست أساس غروبنر لـ $I = \langle x+y+z-6, x-y+1, x+y-z \rangle$ بالنسبة للترتيب المعجمي لأن

$\mathrm{lt}(x+y+z-6-(x-y+1)) = \mathrm{lt}(2y+z-7) = 2y$

لا يقبل القسمة على

$x = \mathrm{lt}(x+y+z-6) = \mathrm{lt}(x-y+1) = \mathrm{lt}(x+y-z).$

لكي نتحصل على أساس غروبنر لمثالي، من أجل ترتيب معين على وحيدات الحد، يمكننا استعمال خوارزمية بشيرغر². نجد خوارزميات تسمح بحساب أساسات غروبنر في أغلبية برامج الحساب الجبري.

نلاحظ في المثال السابق أن أساس غروبنر للمثالي $I = \langle x+y+z-6, x-y+1, x+y-z \rangle$ ، بالنسبة للترتيب المعجمي هو $G = \{x+y+z-6, 2y+z-7, 2z-6\}$ .

4. حل المسألة وبعض التطبيقات

إن جملة المعادلات في المثال 1 لها على الأكثر عدد منته من الحلول (تسعة متغيرات، كل واحــد منهـا يمكنه أخذ واحدة من بين ثلاث قيم). تكمن المسألة في معرفة ما إذا كان للجملة حل، وفي هــذه الحالــة ينبغي تعيينه.

بتطبيق خوارزمية بشيرغر على جملة المثال 1، نتحصل، من أجل الترتيــب المعجمـــي، علـــى أســـاس غروبنر $G$ التالي

$G = \left\{ \begin{array}{l} x_1^3 - 1;\; x_2^2 + x_2 x_1 + x_1^2;\; x_3^2 + x_3 x_2 - x_2 x_1 - x_1^2; \\ x_4 + x_3 + x_2;\; x_5 - x_2;\; x_6 + x_3 + x_2;\; x_7 - x_2;\; x_8 + x_3 + x_2;\; x_9 - x_3 \end{array} \right\}.$

ومن ثمّ فإن $1 \notin I$ . وعندئذ نلاحظ أن الجملة تقبل حلولا. تعبّر المعادلات التالية

$\left\{ \begin{array}{l} x_1^3 - 1 = 0, \\ x_2^2 + x_2 x_1 + x_1^2 = 0, \\ x_5 - x_2 = 0, \\ x_7 - x_2 = 0, \\ x_9 - x_3 = 0 \end{array}\right.$

عما يلي: يمكننا استعمال أي لون لـ $x_1$ ، مع $x_2 \neq x_1$ و $x_2 = x_5 = x_7$ و $x_3 = x_9$ . بما أن الألوان تُمثّل بواسطة جذور تكعيبية عقدية للوحدة فإن الحل الوحيد من أجل $x_4 + x_3 + x_2 = 0$ و $x_6 + x_3 + x_2 = 0$ و $x_8 + x_3 + x_2 = 0$ يكون بإعطاء قيم (ألوان) مختلفة لـ $x_2$ و $x_3$ و $x_4$ . ومنه $x_4 = x_6 = x_8$ .

أخيرا، نجد العلاقة $0 = x_3^2 + x_3 x_2 - x_2 x_1 - x_1^2 = (x_3 + x_2 + x_1)(x_3 - x_1)$ التي تؤدي إلى إمكانيتين: $x_3 + x_2 + x_1 = 0$ أو $x_3 - x_1 = 0$ أي $x_1$ و $x_2$ و $x_3$ ألوانا مختلفة أو $x_1 = x_3$ . وهكذا، نجد بمبادلة الألوان كل الحلول الممكنة:

يمكن استخدام أساسات غروبنر أيضا لتعيين مثاليات، وذلك عن طريق تحويل المعادلات الوسيطية إلى معادلات ديكارتية (من أجل السطوح والمنحنيات مثلا). كما نستطيع استعمالها لحساب كثير الحدود الأصغري ذي معادلات ديكارتية (من أجل السطوح والمنحنيات مثلا)، وكذا للتأكد من نظريات الهندسة الإقليدية، ومن صحة الإنشاءات الأوريغامية Origami. وتستخدم كذلك في حل شبكات السودوكو Sudoku (انظر المراجع (4) و(5) و (6)).

المراجع

(1) http://www.ipv.pt/millenium/Millenium24/12.pdf

(2) http://www.mat.uniroma1.it/people/manetti/dispense/nullstellen.pdf

(3) https://www.risc.jku.at/people/buchberg/papers/1970-00-00-A.english.pdf

(4) Adams, W. and Loustaunau, P., An Introduction to Gröbner Basis, AMS, Providence RI (1994).

(5) Cox, D; Little, J. and O’Shea, D., Ideals, Varieties and Algorithms, 2nd edition, Springer-Verlag, New York, (1996).

(6) Hernandes, M. E., Um Primeiro Contato com Bases de Gröbner, 28°. Colóquio Brasileiro de Matemática, IMPA, Rio de Janeiro, (2011).

خريطة التلوين وقواعد Gröbner

Related

اترك ردّاًإلغاء الرد

شارك هذا الموضوع:

Related

اترك ردّاًإلغاء الرد