Get best of the week

يوضح دليل قوس قزح وجود مكونات قياسية في الرسوم البيانية

أثبت علماء الرياضيات أن نسخ الرسوم البيانية الأصغر يمكن أن تغطي دائمًا الرسوم البيانية الأكبر حجمًا.



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

قبل علماء الرياضيات بحماس تأكيد هذه الفرضية.

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

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

وفي المطبخ ، وفي الرسوم البيانية ، من المهم أن تضع بالضبط البلاط الأول. يسلط العمل الجديد الضوء على هذه القضية الحاسمة - وبطريقة تجعلها مفاجئة وبديهية على حد سواء.

الغابات مع الأشجار


في التوافقيات ، يدرس علماء الرياضيات كيف تتحد القمم (النقاط) والحواف (الخطوط) لتكوين كائنات أكثر تعقيدًا تسمى الرسوم البيانية. يمكنك طرح الكثير من الأسئلة حول الرسوم البيانية. واحدة من الأساسيات: في أي الحالات تكون الرسوم البيانية الأصغر والأبسط مدمجة بشكل مثالي في الرسوم الأكبر والأكثر تعقيدًا؟

قال جاكوب فوكس من جامعة ستانفورد: "لديك مجموعة من قطع الألغاز ولا تعرف ما إذا كان يمكنك تجميعها من هذه القطع" .

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



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



يتعلق سؤال رينجل بعلاقة الرسوم البيانية والأشجار الكاملة. قال: أولاً ، تخيل رسمًا بيانيًا كاملاً لرؤوس 2n + 1 (رقم فردي). ثم تخيل أي شجرة تتكون من رؤوس n + 1 - ويمكن أن تكون هذه الأشجار مختلفة تمامًا.

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

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



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

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

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

قال مونتغومري: "حقيقة أن عدد حواف الرسم البياني الكامل مقسومًا على عدد حواف الشجرة أمر مهم جدًا".

سرعان ما وجد علماء الرياضيات دليلاً آخر على معقولية الفرضية ، والتي أدت إلى سلسلة من الاكتشافات التي أدت في النهاية إلى الدليل.

ضع وأدر


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



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

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



تأمل الآن النجم المطابق لها: النقطة المركزية ذات الحواف الخمسة المنبثقة منه.



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

سنقوم بتدوير النجم أبعد. في الوقت الذي نعود فيه إلى حيث بدأنا ، سنقوم بتمهيد الرسم البياني الكامل بالكامل دون تراكب النجوم - تمامًا كما تنبأ Ringel.



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

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

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

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

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

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

تخيل مرة أخرى رسمًا بيانيًا كاملاً مع 11 قمة مرتبة في شكل دائرة. ضع علامة على حوافها برموز ألوان وفقًا لقاعدة بسيطة تأخذ في الاعتبار المسافة بين الذروتين.

يتم تحديد هذه المسافة من خلال عدد الخطوات التي يجب اتخاذها للانتقال من قمة إلى أخرى في دائرة (بدون قطع المسار داخل الدائرة). بالطبع ، في دائرة ، يمكنك دائمًا الذهاب في اتجاهين ، لذلك سنحدد المسافة على أنها أقصر مسار بين قمتين. إذا كانت هذه هي القمم المجاورة ، فستكون المسافة بينهما 1 ، وليس 10. إذا تم فصلها برأس واحد ، فستكون المسافة 2.



الآن نقوم بتلوين حواف الرسم البياني وفقًا للمسافة. نرسم جميع الحواف التي تربط القمم الموجودة على مسافة 1 بلون واحد - على سبيل المثال ، أزرق. نرسم جميع الحواف التي تربط القمم الموجودة على مسافة وحدتين في الأخرى - على سبيل المثال ، أصفر.

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



بعد وقت قصير من طرح Ringel و Kotzig لفرضياتهما ، أدرك Kotzig أن تلوين الرسم البياني الكامل له يمكن أن يكون دليلاً لوضع شجرة عليه.

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



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

قال بوكروفسكي: "إذا صنعت نسخة من قوس قزح ، فإن كل شيء سيعمل".

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

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

تغليف مثالي


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

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

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

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

قال بوكروفسكي: "تبدأ الصعوبة عندما تحاول ملء رسم بياني كامل بمثل هذه الأشياء المحرجة التي تبدو مثل النجوم".

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

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



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

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

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

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

قال مونتغومري: "في نهاية بناء الأشجار ، عندما يصبح الوضع معقدًا ، لم يعد لدي لون إلزامي واحد ، ولكن لم يكن لدي خيار صغير".

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

قالت نوجا ألون من جامعة برينستون: "يمكنك الآن إجبار ما قمت بتأجيله منذ البداية ، كما لو كنت تمتص ما تبقى من الشجرة والحصول على ألوان قوس قزح كاملة".

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

وإذا كانت نسخة قوس قزح موجودة دائمًا ، فيمكنك دائمًا ربط الرسم البياني بالطريقة التي تنبأ بها Ringel. وبالتالي ، فإن فرضيته صحيحة.

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

قال فوكس: "إن ذلك يظهر أن الأساليب التي كان الناس يفكرون بها لفترة طويلة لديها إمكانات كبيرة حقًا". "إذا قمت بتطبيقها بشكل صحيح ، يمكنك حل المشكلات التي بدت في السابق منيعة."

More articles:


All Articles