نظرية أور

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

ليكن G رسمًا بيانيًا (محدودًا وبسيطًا) يحتوي على n ≥ 3 رؤوس. نرمز بـ deg v إلى درجة الرأس v في G ، أي عدد الحواف المتصلة بـ v في G. وتنص نظرية أور على أنه إذا

إذن G هي دالة هاميلتونية .

يكافئ ذلك إثبات أن كل رسم بياني غير هاميلتوني G لا يحقق الشرط (*) . بناءً على ذلك، ليكن G رسمًا بيانيًا على n ≥ 3 رؤوس غير هاميلتوني، وليكن H مُشكَّلًا من G بإضافة حواف واحدة تلو الأخرى لا تُنشئ دورة هاميلتونية، حتى يتعذر إضافة المزيد من الحواف. ليكن x و y أي رأسين غير متجاورين في H. عندئذٍ، تُنشئ إضافة الحافة xy إلى H دورة هاميلتونية جديدة واحدة على الأقل، ويجب أن تُشكِّل الحواف الأخرى غير xy في هذه الدورة مسارًا هاميلتونيًا v₁ _v₂ ... vₙ في H حيث x = _v₁ و y = vₙ . لكل _{فهرس i في} النطاق 2 _≤ i ≤ _n ، نُحدِّد الحافتين _{المُحتملتين} في H _من v₁ _إلى vₙ ومن vₙ - ₁ إلى vₙ . لا يمكن أن يوجد في H إلا ضلع واحد من هذين الضلعين، وإلا لكانت الدورة v₁ v₂ _{... vᵢ₋₁ vₙ vₙ₋₁ ... vᵢ v₁ دورة} هاميلتونية . _{وبالتالي ، فإن} العدد _{الإجمالي} للأضلاع المتصلة إما بـ v₁ _أو vₙ يساوي على _الأكثر عدد خيارات _{i ، وهو} n - 1. لذلك _، لا تحقق H الخاصية ( * ) ، التي تشترط أن يكون هذا العدد الإجمالي للأضلاع ( _درجة v₁ + درجة vₙ _{) أكبر} من أو يساوي n . وبما أن درجات الرؤوس في G تساوي على الأكثر درجاتها في H ، فإن G لا تحقق الخاصية (*) أيضًا . 

يصف بالمر (1997) الخوارزمية البسيطة التالية لإنشاء دورة هاميلتونية في رسم بياني يفي بشرط أور.

1. قم بترتيب الرؤوس بشكل عشوائي في دورة، مع تجاهل التجاور في الرسم البياني.
2. بينما تحتوي الدورة على رأسين متتاليين v _i و v _{i  +  1} غير متجاورين في الرسم البياني، قم بتنفيذ الخطوتين التاليتين:
   • ابحث عن فهرس j بحيث تكون الرؤوس الأربعة v _i و v _{i  +  1} و v _j و v _{j  +  1} جميعها متميزة، وبحيث يحتوي الرسم البياني على حواف من v _i إلى v _j ومن v _{j  +  1} إلى v _{i  +  1}
   • اعكس جزء الدورة بين v _{i  +  1} و v _j (شاملة).

تزيد كل خطوة عدد الأزواج المتتالية المتجاورة في الدورة على الرسم البياني، بمقدار زوج واحد أو زوجين (بحسب ما إذا كان الرأسان v _{_j} و v_{_{j  +  1}} متجاورين بالفعل)، لذا لا يمكن أن تتكرر الحلقة الخارجية أكثر من n مرة قبل انتهاء الخوارزمية، حيث n هو عدد رؤوس الرسم البياني المُعطى. وبحجة مشابهة لتلك الواردة في برهان النظرية، يجب أن يكون الفهرس المطلوب j موجودًا، وإلا فإن مجموع درجات الرأسين غير المتجاورين v_{_i} و v _{_{i  +  1}} ^سيكون صغيرًا جدًا. يمكن إنجاز إيجاد i و j ، وعكس جزء من الدورة، في زمن O( n ). وبالتالي، فإن الزمن الكلي للخوارزمية هو O( n² )، وهو ما يطابق عدد الحواف في الرسم البياني المُدخل.

تُعدّ نظرية أور تعميمًا لنظرية ديراك، التي تنص على أنه عندما يكون لكل رأس درجة لا تقل عن n /2 ، يكون الرسم البياني هاميلتونيًا. فإذا حقق الرسم البياني شرط ديراك، فمن الواضح أن مجموع درجات كل زوج من الرؤوس يساوي n على الأقل .

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

وجد وودال (1972) صيغةً لنظرية أور تنطبق على الرسوم البيانية الموجهة . لنفترض أن الرسم البياني الموجه G يتمتع بالخاصية التالية: لكل رأسين u و v ، إما أن يكون هناك ضلع من u إلى v، أو أن مجموع درجة خروج u ودرجة دخول v يساوي أو يزيد عن عدد رؤوس G. عندئذٍ، وفقًا لنظرية وودال، يحتوي G على دورة هاميلتونية موجهة. يمكن استنتاج نظرية أور من وودال باستبدال كل ضلع في رسم بياني غير موجه بزوج من الأضلاع الموجهة. وتنص نظرية أخرى وثيقة الصلة، وضعها مينيل (1973)، على أن الرسم البياني الموجه المتصل بقوة والمكون من n رأسًا ، والذي يتمتع بالخاصية التالية: لكل رأسين غير متجاورين u و v ، يكون العدد الإجمالي للأضلاع المتصلة بـ u أو v على الأقل 2n - 1، يجب أن يكون هاميلتونيًا.  

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

• بوندي، جيه إيه (1971)، "الرسوم البيانية الدورية الكاملة 1"، مجلة نظرية التوافيق، السلسلة ب ، 11 (1): 80-84 ، doi : 10.1016/0095-8956(71)90016-5.
• Meyniel، M. (1973)، “Une condition suffisante d’existence d’un Circuit hamiltonien dans un graphe orienté”، مجلة النظرية التوافقية، السلسلة ب (باللغة الفرنسية)، 14 (2): 137–147 ، دوى : 10.1016 / 0095-8956 (73)90057-9.
• أور، أ. (1960)، "ملاحظة حول دوائر هاميلتون"، المجلة الرياضية الأمريكية الشهرية ، 67 (1): 55، doi : 10.2307/2308928 ، JSTOR 2308928 .
• بالمر، إي إم (1997)، "الخوارزمية الخفية لنظرية أور حول دورات هاميلتون"، الحوسبة والرياضيات مع التطبيقات ، 34 (11): 113-119 ، doi : 10.1016/S0898-1221(97)00225-3 ، MR 1486890 .
• وودال، د. ر. (1972)، "شروط كافية للدوائر في الرسوم البيانية"، وقائع الجمعية الرياضية في لندن ، السلسلة الثالثة، 24 : 739-755 ، doi : 10.1112/plms/s3-24.4.739 ، MR 0318000 .