Get best of the week

تلوين قوس قزح هم أفضل أصدقاء الرياضيات

في الآونة الأخيرة ، ساعدت ألوان قوس قزح في تنفيذ دليل جديد. وهي ليست المرة الأولى التي تكون فيها مفيدة.



يمكن أن يخبر الترميز اللوني للمربع اللاتيني ورسمه البياني الكثير عنهما

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

فرضية Ringel هي مشكلة من مجال التوافيق المتعلقة ببناء الرسوم البيانية - نقاط (قمم) متصلة بخطوط (حواف). يتنبأ بعلاقة خاصة بين الرسوم البيانية الكبيرة من نوع معين مع رؤوس 2n + 1 والرسوم البيانية الأصغر نسبيًا مع رؤوس n + 1.

لنبدأ ، على سبيل المثال ، بـ 11 قمة. ربط كل قمة مع كل الآخرين للحصول على ما يسمى رسم بياني كامل. بعد ذلك ، خذ ستة من القمم المتاحة ، وقم بتوصيلها ، كما نشاء ، فقط حتى لا نحصل على حلقات مغلقة. وهكذا نحصل على ما يسمى ب "خشب".


توضح أمثلة الرسوم البيانية والأشجار الكاملة

فرضية Ringel أن نسخ أي شجرة يمكن أن تغطي بشكل مثالي ، أو تجانب ، جميع حواف الرسم البياني الكامل المقابل - تمامًا كما يمكنك تجانب أرضية المطبخ بنفس البلاط.



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



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

ومع ذلك ، فإن هذه التقنية من تلوين قوس قزح لم تأتي لإنقاذ للمرة الأولى.

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



ثم تساءل أويلر: هل من الممكن اختيار ثلاث خلايا ، واحدة من كل عمود وكل صف ، بحيث لا تتكرر الأرقام الموجودة فيها؟ افترض أنه يمكنك تحديد خلية من العمود الأول من الصف الأول الذي يحتوي على 1 ، وخلية من الصف الثاني من العمود الثاني تحتوي على 3 ، ومن الصف الثالث من العمود الثالث الذي يحتوي على 2. لذلك ، اخترنا ثلاث خلايا ، كل منها تنتمي إلى صفوف وأعمدة مختلفة ، وتحتوي على رقمها - 1 ، 3 ، 2. تسمى هذه المجموعة من الخلايا المستعرضة.



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

ونتيجة لذلك ، اكتشف علماء الرياضيات أن إحدى الطرق لاستكشاف هذه المشكلة هي تحويل مربع إلى رسم بياني. للقيام بذلك ، ارسم ثلاثة رؤوس على اليسار ، تشير إلى ثلاثة أعمدة. ثم نرسم ثلاث رؤوس على اليمين ، تمثل الخطوط. ارسم الحواف التي تربط كل قمة على اليمين بكل قمة على اليسار. تمثل كل حافة ، كونها مزيجًا من صف وعمود معين ، إحدى الخلايا التسع. على سبيل المثال ، تتطابق الحافة بين أعلى الرأس الأيمن وأعلى اليسار الأيسر مع خلية الصف الأول من العمود الأول (الخلية اليسرى العليا من المربع اللاتيني).



الآن نخرج أقلام الرصاص الملونة ونرمز ألوان الأضلاع وفقًا لأرقام المربعات التي تشير إليها. لنفترض أننا قمنا بتلوين الخطوط التي تشير إلى 1 باللون الأزرق والأحمر مع 2 والأصفر مع 3. إذا كان 1 في الخلية العلوية اليسرى ، فستكون الحافة بين القمم العلوية زرقاء.



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



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

لفهم جوهر المشكلة ، ارسم أولاً ستة رؤوس ، ثم قم بتوصيلها لتشكيل شجرة. قم بتعيين رقم لكل قمة الرأس بأي شكل من الأشكال. ثم ضع علامة على كل حافة مع الفرق بين أرقام القمم التي تربطها. هذا ، على سبيل المثال ، إذا كانت الحافة تربط بين الذروتين 6 و 2 ، فإننا نضع علامة على هذه الحافة بالرقم 4.

هدفك هو جعل تسميات الحافة متسلسلة ولا تتكرر أرقامها. في هذه الحالة ، 1 ، 2 ، 3 ، 4 ، 5. إذا كنت تستطيع القيام بذلك ، فسيكون هناك ترميز رشيق لشجرتك.



في الستينيات ، اقترح جيرهارد رينجيل - الشخص الذي طرح الفرضية - وأنطون كوتسيج ، معًا أنه يمكن تمييز أي شجرة ، بغض النظر عن عدد الحواف أو الشكل ، بأمان.

تفترض فرضية الترميز الرشيقة فرضية Ringel - أي إذا كانت الفرضية الأولى صحيحة ، فإن فرضية Ringel صحيحة أيضًا. لفهم هذا ، دعونا نعود إلى شجرة معلمة برشاقة من ستة قمم ورسم بياني كامل من 11 قمة. نقوم بتوزيع 11 رأسًا حول المحيط وترقيمها من 1 إلى 11. الآن سنضع نسخة من الشجرة على الرسم البياني الكامل بحيث تتزامن تسميات القمم: تتداخل قمة الرأس 5 للشجرة مع الرأس 5 من الرسم البياني الكامل ، وهكذا. هذا الموضع هو نسخة قوس قزح من شجرة مميزة برشاقة.



لذلك إذا كنت تعرف أن الأشجار التي تحتوي على عدد من القمم n + 1 يمكن دائمًا تمييزها برشاقة ، فأنت تعلم أنه يمكن دائمًا وضعها داخل الرسم البياني الكامل المقابل مع رؤوس 2n + 1 للحصول على نسخة قوس قزح من الشجرة. ومثل هذا الموضع سيكون بالضبط المكان الذي تبدأ فيه عملية تبليط Ringel.

قال بيني سوداكوف من المعهد الفيدرالي السويسري للتكنولوجيا ، أحد المؤلفين الثلاثة لإثبات فرضية رينجل: "إذا وجدت ترميزًا رشيقًا ، يمكنني أن أخبرك بكيفية العثور على نسخة قوس قزح" .

بالطبع ، تمكن علماء الرياضيات في نهاية المطاف من إثبات حقيقة فرضية Ringel دون الحاجة إلى إثبات فرضية الترميز الرشيق ، تاركين هذا السؤال دون إجابة.

قال سوداكوف: "الترميز اللطيف هو مسألة جذابة وجميلة في حد ذاته ، ولا يزال مفتوحًا".

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

More articles:


All Articles