غطاء مزدوج للدراجات

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

هي مسألة طُرحت في سبعينيات القرن الماضي من قِبل دبليو تي توت ، ^{[ 1 ]} وإيتاي وروديه، ^{[ 2 ]} وجورج سيكيريس، ^{[ 3 ]} وبول سيمور، ^{[ 4 ]} وتُعرف باسم حدسية الغطاء المزدوج للدورة ، وتتعلق بما إذا كان لكل رسم بياني بدون جسور غطاء مزدوج للدورة. ويمكن صياغة هذه الحدسية بشكل مكافئ بدلالة تضمينات الرسوم البيانية ، وفي هذا السياق تُعرف أيضًا باسم حدسية التضمين الدائري .

في يوليو 2026، أصدرت OpenAI نسخة أولية تدعي التوصل إلى حل إيجابي للتخمين، ^{[ 5 ] [ 6 ]} والذي يزعمون أن الدليل عليه تم إنشاؤه بواسطة GPT-5.6 ، وهو نموذج اللغة الكبير الخاص بهم .

الدورة هي رسم بياني فرعي متصل ، جميع رؤوسه من الدرجة 2. وبالتحديد، لا يُعتبر ضلع واحد، يتم اجتيازه ذهابًا وإيابًا، دورة. الجسر في الرسم البياني هو ضلع يؤدي حذفه إلى زيادة عدد المكونات المتصلة .

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

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

في 10 يوليو 2026، أعلنت OpenAI على تويتر أن نموذج اللغة الضخم GPT-5.6 Sol قد توصل إلى برهان للفرضية "في أقل من ساعة". ^{[ 7 ]} ونشرت الشركة البرهان المقترح المكون من ثلاث صفحات للفرضية ^{[ 5 ]} بالإضافة إلى التعليمات المكونة من صفحتين المستخدمة لإنشاء هذا البرهان. ^{[ 8 ]} ووجهت التعليمات GPT-5.6 إلى استخدام "ما يصل إلى 64 وكيلًا متزامنًا"، والحفاظ على استقلالية هذه الوكلاء من خلال جعلهم يعملون على مناهج مختلفة وعدم إخبارهم بالمنهج المفضل حاليًا، و"استخدام وكلاء منافسين طوال العملية" للتحقق من البراهين المرشحة، و"قضاء 8 ساعات على الأقل في ذلك". ^{[ 8 ]} كما نشر فريق OpenAI أيضًا صياغة رسمية للبرهان في Lean . ^{[ 9 ]}

يعتمد البرهان على اختزالٍ لفرانسوا جاغر المذكور أدناه، ^{[ 10 ]} ، وهو أنه يكفي إثبات التخمين للرسوم البيانية المتعددة عديمة الحلقات المكعبة (أي التي يكون لكل رأس فيها درجة 3). علاوة على ذلك، يعتمد البرهان على حقيقة أن كل رسم بياني عديم الجسور يقبل قيمة غير صفرية في أي مكان.${\displaystyle {\mathbb {F}}_{2}^{3}}$-flow، الذي تم تأسيسه بشكل مستقل بواسطة Jaeger (1976) و Kilpatrick (1975).

أشار عالم الرياضيات توماس بلوم إلى فكرة استخدام الصفر في أي مكان${\displaystyle {\mathbb {F}}_{2}^{3}}$يعود استخدام التدفقات على الرسوم البيانية المكعبة لدراسة الأغطية المزدوجة للدورات إلى ورقة بحثية نُشرت عام 1983 على الأقل من قبل بيرموند وجاكسون وجايجر. ^{[ 11 ]}

الرسم البياني غير المتصل (snark) هو حالة خاصة من الرسم البياني غير المتصل، ويتميز بخصائص إضافية، منها أن كل رأس فيه له ثلاثة حواف متصلة به بالضبط (أي أن الرسم البياني مكعب )، وأنه لا يمكن تقسيم حواف الرسم البياني إلى ثلاثة تطابقات تامة (أي أن الرسم البياني لا يحتوي على تلوين ثلاثي الحواف ، وبحسب نظرية فيزينغ، فإن مؤشره اللوني يساوي 4). وقد تبين أن الرسوم البيانية غير المتصلة (snark) تشكل الحالة الصعبة الوحيدة لفرضية التغطية المزدوجة للدورة: فإذا كانت هذه الفرضية صحيحة بالنسبة للرسوم البيانية غير المتصلة (snark)، فإنها صحيحة لأي رسم بياني. ^{[ 10 ]}

لاحظ جايجر (1985) أنه في أي مثال مضاد مصغر محتمل لفرضية الغطاء المزدوج للدورة، يجب أن تحتوي جميع الرؤوس على ثلاثة حواف متصلة بها أو أكثر. فالرأس الذي يتصل به حافة واحدة فقط يشكل جسرًا، بينما إذا اتصلت حافتان برأس ما، فيمكن تقليصهما لتشكيل رسم بياني أصغر بحيث يمتد أي غطاء مزدوج لهذا الرسم البياني الأصغر إلى أحد الرسمين البيانيين الأصليين. من ناحية أخرى، إذا كان للرأس v أربعة حواف متصلة به أو أكثر، فيمكن فصل حافتين منها بإزالتهما من الرسم البياني واستبدالهما بحافة واحدة تربط بين طرفيهما الآخرين، مع الحفاظ على عدم وجود جسور في الرسم البياني الناتج. مرة أخرى، يمكن تمديد الغطاء المزدوج للرسم البياني الناتج بطريقة مباشرة إلى غطاء مزدوج للرسم البياني الأصلي: كل دورة في الرسم البياني المفصول تقابل إما دورة في الرسم البياني الأصلي، أو زوجًا من الدورات يلتقيان عند v . وبالتالي، يجب أن يكون كل مثال مضاد مصغر مكعبًا. لكن إذا كان من الممكن تلوين حواف الرسم البياني المكعب بثلاثة ألوان (مثلاً بالأحمر والأزرق والأخضر)، فإن الرسم البياني الفرعي للحواف الحمراء والزرقاء، والرسم البياني الفرعي للحواف الزرقاء والخضراء، والرسم البياني الفرعي للحواف الحمراء والخضراء، كل منها يشكل مجموعة من الدورات المنفصلة التي تغطي جميع حواف الرسم البياني مرتين. لذلك، يجب أن يكون كل مثال مضاد أدنى رسمًا بيانيًا مكعبًا غير قابل للتلوين بثلاثة ألوان للحواف، أي رسمًا بيانيًا مكعبًا بدون جسور، أي رسمًا بيانيًا مكعبًا غير قابل للتلوين بثلاثة ألوان للحواف. ^{[ 10 ]}

يتمثل أحد الحلول الممكنة لمسألة التغطية المزدوجة للدورة في إثبات استحالة وجود مثال مضاد أدنى، وذلك بإثبات أن أي رسم بياني يحتوي على تكوين قابل للاختزال ، أي رسم بياني فرعي يمكن استبداله برسم بياني فرعي أصغر بطريقة تحافظ على وجود أو عدم وجود تغطية مزدوجة للدورة. على سبيل المثال، إذا احتوى رسم بياني مكعب على مثلث، فإن تحويل Δ-Y سيستبدل المثلث برأس واحد؛ ويمكن تمديد أي تغطية مزدوجة للدورة للرسم البياني الأصغر إلى تغطية مزدوجة للدورة للرسم البياني المكعب الأصلي. لذلك، يجب أن يكون المثال المضاد الأدنى لفرضية التغطية المزدوجة للدورة رسمًا بيانيًا خاليًا من المثلثات ، مما يستبعد بعض الرسوم البيانية مثل رسم تيتز البياني الذي يحتوي على مثلثات. من خلال عمليات البحث الحاسوبية، من المعروف أن كل دورة بطول 11 أو أقل في رسم بياني مكعب تُشكل تكوينًا قابلًا للاختزال، وبالتالي فإن أي مثال مضاد أدنى لفرضية التغطية المزدوجة للدورة يجب أن يكون محيطه 12 على الأقل. ^{[ 12 ]}

لسوء الحظ، لا يمكن إثبات حدسية الغطاء المزدوج للدورة باستخدام مجموعة محدودة من التكوينات القابلة للاختزال. فكل تكوين قابل للاختزال يحتوي على دورة، لذا لكل مجموعة محدودة S من التكوينات القابلة للاختزال، يوجد عدد γ بحيث تحتوي جميع التكوينات في المجموعة على دورة طولها γ على الأكثر. ومع ذلك، توجد مجموعات شبكية ذات محيط كبير بشكل تعسفي، أي ذات حدود عالية بشكل تعسفي على طول أقصر دورة فيها. ^{[ 13 ]} لا يمكن لمجموعة شبكية G ذات محيط أكبر من γ أن تحتوي على أي من التكوينات في المجموعة S ، لذا فإن الاختزالات في S ليست قوية بما يكفي لاستبعاد احتمال أن تكون G مثالًا مضادًا مصغرًا.

إذا كان للرسم البياني غطاء مزدوج دوري، فيمكن استخدام دورات هذا الغطاء لتشكيل الخلايا الثنائية لتضمين الرسم البياني على مُركّب خلوي ثنائي الأبعاد . في حالة الرسم البياني المكعب، يُشكّل هذا المُركّب دائمًا سطحًا متعدد الشعب . يُقال إن الرسم البياني مُضمّن دائريًا على السطح متعدد الشعب، حيث يكون كل وجه من أوجه التضمين دورة بسيطة في الرسم البياني. مع ذلك، قد لا يتوافق الغطاء المزدوج الدوري لرسم بياني بدرجة أكبر من ثلاثة مع تضمين على سطح متعدد الشعب: فقد يكون للمُركّب الخلوي المُشكّل من دورات الغطاء طوبولوجيا غير متعددة الشعب عند رؤوسه. تنصّ فرضية التضمين الدائري أو فرضية التضمين القوي ^{[ 10 ]} على أن كل رسم بياني مُتصل برأسين له تضمين دائري على سطح متعدد الشعب. إذا كان الأمر كذلك، فإن الرسم البياني له أيضًا غطاء مزدوج دوري، مُشكّل من أوجه التضمين.

بالنسبة للرسوم البيانية المكعبة، فإن اتصال الرؤوس الثنائية وانعدام الجسور متكافئان. لذلك، من الواضح أن فرضية التضمين الدائري لا تقل قوة عن فرضية التغطية المزدوجة للدورة. ^{[ 10 ]}

إذا وُجد تضمين دائري، فقد لا يكون على سطح ذي جنس أدنى: فقد وصف نغوين هوي شونغ رسمًا بيانيًا حلقيًا متصلًا برأسين لا يقع أي من تضميناته الدائرية على سطح حلقي. ^{[ 10 ]}

هناك صيغة أقوى لفرضية التضمين الدائري، وهي الفرضية التي تنص على أن كل رسم بياني متصل برأسين له تضمين دائري على مشعب قابل للتوجيه . وبالنسبة لفرضية الغطاء المزدوج للدورات، فإن هذا يكافئ الفرضية القائلة بوجود غطاء مزدوج للدورات، وتوجيه لكل دورة في الغطاء، بحيث يكون لكل حافة e، تكون الدورتان اللتان تغطيان e موجهتين في اتجاهين متعاكسين عبر e . ^{[ 10 ]}

بدلاً من ذلك، تم النظر أيضاً في تعزيزات للفرضية تتضمن تلوين الدورات في الغطاء. وأقوى هذه التعزيزات هي فرضية مفادها أن كل رسم بياني بدون جسور له تضمين دائري على مشعب قابل للتوجيه حيث يمكن تلوين الوجوه بخمسة ألوان. إذا صحّ ذلك، فإنه سيؤدي إلى فرضية WT Tutte التي تنص على أن كل رسم بياني بدون جسور له تدفق خماسي غير صفري في أي مكان . ^{[ 10 ]}

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

• تخمين بيترسن للتلوين

• فليشنر، هربرت (1976)، “Eine Gemeinsame Basis für die Theorie der Eulerschen Graphen und den Satz von Petersen”، Monatshefte für Mathematik ، 81 (4): 267–278 ، دوى : 10.1007 / BF01387754 (غير نشط في 30 يناير 2026)، S2CID 118767538 {{citation}}: CS1 maint: DOI غير نشط اعتبارًا من يناير 2026 ( رابط ) .
• إيتاي، أ.؛ روديه، م. (1978)، "تغطية الرسم البياني بالدوائر"، الأوتوماتا واللغات والبرمجة. المؤتمر الدولي للأتمتة واللغات والبرمجة 1978 ، سلسلة محاضرات في علوم الحاسوب (أوسييلو، ج.، بوم، س. (محرران))، المجلد  62، سبرينغر، الصفحات 289-299 ، doi : 10.1007/3-540-08860-1_21 ، ISBN  978-3-540-08860-8.
• هوك، أ. (2000)، "التكوينات القابلة للاختزال لتخمين الغطاء المزدوج للدورة"، الرياضيات التطبيقية المنفصلة ، ​​99 ( 1-3 ): 71-90 ، doi : 10.1016/S0166-218X(99)00126-2.
• ياغر، ف. (1985)، "دراسة استقصائية لتخمين الغطاء المزدوج للدورة"، حوليات الرياضيات المتقطعة 27 - الدورات في الرسوم البيانية ، دراسات الرياضيات في شمال هولندا، المجلد  27، الصفحات 1-12 ، doi : 10.1016/S0304-0208(08)72993-1 ، ISBN  978-0-444-87803-8.
• كوخول، مارتن (1996)، "Snarks بدون دورات صغيرة"، مجلة نظرية التوافيق، السلسلة ب ، 67 (1) (  الطبعة الأولى): 34-47 ، doi : 10.1006/jctb.1996.0032.
• كوخول، مارتن (2009أ)، "الرسوم البيانية المنتظمة ثلاثية الألوان غير القابلة للتلوين بثلاثة حواف مع تضمينات متعددة السطوح في الأسطح القابلة للتوجيه"، رسم الرسوم البيانية 2008، المحررون: آي جي توليس، إم باترينياني ، سلسلة محاضرات في علوم الحاسوب، المجلد 5417  ، الصفحات 319-323 .
• كوخول، مارتن (2009ب)، "التضمينات متعددة السطوح للـ snarks في الأسطح القابلة للتوجيه"، وقائع الجمعية الرياضية الأمريكية ، 137 (5) (  الطبعة الخامسة): 1613-1619 ، doi : 10.1090/S0002-9939-08-09698-6.
• سيمور، ب. د. (1979)، "مجموع الدوائر"، في بوندي، ج. أ.؛ مورتي، يو. إس. آر. (محرران)، نظرية الرسم البياني والمواضيع ذات الصلة ، نيويورك: أكاديميك برس، ص 342-355 ، رقم ISBN  978-0121143503.
• سيكيريس، ج. (1973)، "التحليل متعدد السطوح للرسوم البيانية المكعبة"، نشرة الجمعية الرياضية الأسترالية ، 8 (3): 367-387 ، doi : 10.1017/S0004972700042660.
• توتي، دبليو تي (1987)، مراسلات شخصية مع إتش. فليشنر (22 يوليو 1987).
• تشانغ، كون-كوان (1997)، تدفقات الأعداد الصحيحة وأغطية الدورات للرسوم البيانية ، مطبعة سي آر سي، رقم ISBN 978-0-8247-9790-4.
• تشانغ، كون-كوان (2012)، غلاف مزدوج للدوائر للرسوم البيانية ، مطبعة جامعة كامبريدج، doi : 10.1017/CBO9780511863158 ، ISBN 978-0-5212-8235-2.

• تخمين الغطاء المزدوج الدوري ، وتخمين التضمين الدائري ، وتخمين غرونباوم ، من حديقة المسائل المفتوحة.
• تخمين الغطاء المزدوج للدورة مؤرشف في 2008-12-05 في آلة Wayback ، بقلم دان أرتشيديكون .
• وايسشتاين، إريك دبليو ، "تخمين الغطاء المزدوج الدوري" ، عالم الرياضيات