إثبات فرضية قديمة بعمر 53 عامًا لتلوين الشبكات

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

استوحت مسائل تلوين الشبكات من التساؤل القاضي بتلوين الخرائط لتمييز البلدان المتجاورة؛ فقد كانت هذه المسائل موضع دراسة بين علماء الرياضيات لما يقرب من 200 عام. الهدف من ذلك هو معرفة كيفية تلوين نقاط التقاء الشبكات (أو الرسومات كما يسميها علماء الرياضيات) دون تشابه في اللون لأي نقطتين. 

تعدُّ مسائل تلوين الخرائط بسيطة لكنها صعبة الحل؛ فالسؤال الذي يكمن في كَون الألوان الأربعة الأساسية كافية لتلوين أية خريطة، قد استغرق قرنًا ونيّفًا للإجابة (إن كنت تتساءل، فالجواب "نعم"). تبدو المشكلة التي عولجت حديثًا الجديدة (والتي لم تحل لأكثر من 50 عامًا) ذات صلة بهذه القاعدة؛ إذ إنها متعلقة بقاعدة التنسور – أي رسوم بيانية ناتجة عن دمج منحنيين مختلفين بطريقة معينة (هَب أنهما H وG) – فمنتج التنسور للمنحنيين سابقَيّ الذكر، ينتج منحنى جديدًا أكبر، كل نقطة فيه تمثل زوجًا من النقاط في المنحنيين الأصليين (إحداهما في H والأخرى في G). وتعد نقطتان في منتج تنسور متصلتين إذا كانت كلتا النقطتين المقابلتين لهما في G وH مرتبطتين.

في عام 1966؛ افترض "ستيفن هديتنيمي- Stephen Hedetniemi"- بروفيسور في جامعة "كليمسون- Clemson" في ساوث كارولينا- في أطروحة الدكتوراه الخاصة به، أن أقل عدد من الألوان التي يتطلبها منتج تنسور هو العدد نفسه من الألوان يتطلبها أحد الرسمين المقابلين، باعتماد أصغر العددين.

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

التجمعات الملونة

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

يمكن تمثيل العلاقة بين المهن المختلفة في رسم بياني، إذ تشير النقاط (العقد) فيه إلى المهن، وخطوط تصل بين أي وظيفتين منقطعتَي الصلة. وبالمثل، فمن الممكن إنشاء رسم بياني نقاطه الهوايات، وتوصيل أي هوايتين غير متوافقتين.

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

أمر مهم تلحظه في المثال السابق، أن الألوان التي استخدمتها في رسم منحنى الوظائف، متاحة للاستخدام في منحنى دمج المهنة والهواية، كلٌ بما يوافقه. الأمر ذاته ممكن فيما يخص منحنى الهوايات. 

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

ولأكثر من 50 عامًا، لم يجد علماء الرياضيات منتج تنسور واحدًا يحتاج إلى عدد من الألوان أقل من رسميه المقابلين. التخمين صحيح، إن كان أحد المنحنيين الأصليين يتطلب أربعة ألوان أو أقل من ذلك. كذلك الأمر في إعداد الألوان "الكسرية"، إذ تمثِّل كل نقطة مزيجًا من الألوان- مثلًا 2/3 أصفر و 1/3 أخضر (من حيث حفلات نهاية الأسبوع، كدعوة ثلاثة صحفيين يمارسون رياضة التنس، واستضافة اثنين منهم في العطلة "الصفراء" والثالث في العطلة "الخضراء").

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

تلوين الصفحات

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

يبدأ شيتوف بالنظر في ما يحدث إذا جُمِعَ الرسم البياني G مع أحد الخطوط البيانية "الأسية" لتكوين منتج تنسور. يحتوي التابع الأسي عقدة لكل تلوين محتمل ببضعة ألوان ثابتة (إذ يتاح هنا كل تلوين محتمل، دون حصرٍ بتلوين تكون فيه العقد المختلفة اللون متصلة). فمثلًا، إذا كان المنحنى G يحتوي على سبع عقد، بينما تحوي لوحة الألوان خمسةً فقط، فينتج على المنحنى "الأسي" (5⁷) عقدة، وهذا ما عرفه علماء الرياضيات لفترة طويلة؛ إذ إن هناك رسمًا واحدًا تكفيه هذا الألوان الخمسة: منتج التنسور الناجم عن الرسمين البيانيين G ومنحناه الأسي. تمتلك كل الرسوم البيانية الأسية هذه الخاصية؛ إذ يمكن تلوين الرسم البياني لمنتج التنسور (الناتج من دمج رسمين: الأساسي والأسي الناتج منه) بعدد الألوان الموجودة نفسه في اللوحة الأصلية والمستخدمة لتلوين الرسم البياني الأسي.

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

لِمَ أُهمِلَت حجة كهذه لأكثر من 50 عامًا؟  لغز أرَّق علماء الرياضيات، وعبَّر عنه "بافول هِل-Pavol Hell" من جامعة Simon Fraser في كندا، بقوله: "قد تخفي الأوراقُ جواهِرَ، لقد استطاع شيتوف فهم الأمور على نحو أكثر عمقًا من أي شخص آخر".

تعدُّ رسوم شيتوف البيانية عملاقة، فبالرغم من أنه لم يحسب حجمها بدقة؛ فإنه قدَّر احتواء المنحنى G على (4¹⁰⁰) عقدة، والمنحنى الأسي (4¹⁰⁰⁰⁰) عقدة، رقم يفوق العدد المقدر للجزيئات في الكون المرئي. يحسب شيتوف إنجازه صغيرًا إلى حد لا تحويه مقارنة مع غيره من البراهين المعاكسة، ويصف عمله هذا "ضخمًا في عين الناظر".

وبما أنه من غير المعقول أن تدعو (4¹⁰⁰⁰⁰) ضيف لزيارتك، فإن العمل الذي قدمه شيتوف لا يستبعد وجود أمثلة معاكسة أصغر بكثير مما قُدِّم. الآن وقد عرف علماء الرياضيات أن افتراض هيديتنيمي خاطئ، يأتي السؤال الطبيعي الآتي: ما عدد الألوان التي يتطلبها منتج التنسور أقل من رسومه البيانية المقابلة؟ وكم من العقد وخطوط الوصل يحتويها مثال معاكس كهذا؟

وفي الوقت نفسه، تحتوي الورقة الجديدة درسًا مهمًّا لعلماء الرياضيات، يقول "نوجا ألون-Noga Alon" من جامعة Princeton، مبديًا رأيه: "يعود السبب في كون الافتراض صعب الإثبات أحيانًا، إلى كونه خاطئًا".

المصدر:

هنا