تحليل هاميلتوني

📅 آخر تحديث: ٣ أغسطس ٢٠٢٦
✍️ نُشر في: ٣ أغسطس ٢٠٢٦
📷 يحتوي على 15 صور
الموسوعة الحرة
تحليل واليكي الهاميلتوني للرسم البياني الكاملك9{\displaystyle K_{9}}

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

الشروط الضرورية

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

فئات خاصة من الرسوم البيانية

الرسوم البيانية الكاملة

كل رسم بياني كامل يحتوي على عدد فردين{\displaystyle n}للرسم البياني ذي الرؤوس تحليل هاميلتوني. هذه النتيجة، وهي حالة خاصة من مسألة أوبرولفاخ لتحليل الرسوم البيانية الكاملة إلى عوامل ثنائية متماثلة، نُسبت إلى واليكي بواسطة إدوارد لوكاس عام 1892. وتطرح الصيغة الأصلية لمسألة أوبرولفاخ سؤال كيفية إنشاء مخطط جلوس لـن{\displaystyle n}الناس فوق(ن-1)/2{\displaystyle (n-1)/2}تُعقد وجبات العشاء على مجموعة معينة من الطاولات الدائرية ذات الأحجام المختلفة، بحيث يجلس كل مشارك بجوار الآخر مرة واحدة فقط. أما نظرية واليكي فتُطبق على الحالة التي توجد فيها طاولة واحدة فقط.

أماكن البناء الأصلية لـ Waleckiن-1{\displaystyle n-1}يُقسّم هذا الرسم البياني إلى مضلع منتظم ، ويُغطي الرسم البياني الكامل في هذه المجموعة الفرعية من الرؤوس بـ(ن-1)/2{\displaystyle (n-1)/2}مسارات هاميلتونية متعرجة عبر المضلع، حيث يدور كل مسار عن المسار الآخر بمضاعفاتπ/(ن-1){\displaystyle \pi /(n-1)}ويمكن بعد ذلك إكمال جميع المسارات إلى دورات هاميلتونية عن طريق توصيل نهاياتها من خلال الرأس المتبقي. [ 2 ]

توسيع رأس من2ك{\displaystyle 2k}- رسم بياني منتظم إلى زمرة من2ك{\displaystyle 2k}لا يمكن أن تُغير الرؤوس، رأس واحد لكل طرف من أطراف الحافة عند الرأس المُستبدل، ما إذا كان للرسم البياني تفكيك هاميلتوني. إن عكس عملية التوسيع هذه، أي اختزال زمرة إلى رأس واحد، سيُحوّل أي تفكيك هاميلتوني في الرسم البياني الأكبر إلى تفكيك هاميلتوني في الرسم البياني الأصلي. وعلى العكس، يمكن تطبيق بناء واليكي على الزمرة لتوسيع أي تفكيك هاميلتوني للرسم البياني الأصغر إلى تفكيك هاميلتوني للرسم البياني المُوسّع. [ 3 ]

يُعدّ الرسم البياني الموجّه أحد أنواع الرسوم البيانية المشابهة للرسم البياني الكامل . وهو رسم بياني تتصل فيه كل زوج من الرؤوس المختلفة بحافة موجّهة واحدة من أحدهما إلى الآخر؛ فعلى سبيل المثال، قد يصف هذا الرسم البياني نتيجة بطولة رياضية بنظام الدوري ، حيث يلعب كل متنافس في البطولة ضد كل متنافس آخر، وتكون الحواف موجّهة من الخاسر في كل مباراة إلى الفائز. ورداً على تخمين بول كيلي من عام 1968، [ 4 ] أثبتت دانييلا كوهن وديريك أوستوس في عام 2012 أن لكل بطولة منتظمة كبيرة بما فيه الكفاية تحليلاً هاميلتونياً. [ 5 ]

الرسوم البيانية المستوية

الرسم البياني المتوسط ​​لرسم هيرشل البياني هو رسم بياني مستوٍ منتظم من الدرجة الرابعة بدون تحليل هاميلتوني. المناطق المظللة تُشير إلى رؤوس رسم هيرشل البياني الأساسي.

بالنسبة للرسوم البيانية المستوية المنتظمة من الدرجة 4 ، يمكن اشتقاق شروط إضافية ضرورية من نظرية غرينبيرغ . ويُعطى مثال على رسم بياني مستوٍ منتظم من الدرجة 4 لا يستوفي هذه الشروط، ولا يمتلك تحليلًا هاميلتونيًا، بالرسم البياني المتوسط ​​لرسم هيرشل البياني . [ 6 ]

الموشورات

مشكلة لم تُحل في الرياضيات
هل لكل منشور فوق رسم بياني منتظم ثلاثي الاتصال 3 تحليل هاميلتوني؟
المزيد من المسائل غير المحلولة في الرياضيات

المنشور فوق رسم بياني هو حاصل ضربه الديكارتي مع الرسم البياني الكامل ذي الرأسين. على سبيل المثال، المنشور فوق رسم بياني دوري هو رسم بياني لمنشور هندسي . وقد دُرست الرسوم البيانية المنتظمة من الدرجة 4، الناتجة عن منشورات فوق رسوم بيانية منتظمة من الدرجة 3، بشكل خاص فيما يتعلق بالتحليل الهاميلتوني. عندما يكون الرسم البياني الأساسي المنتظم من الدرجة 3 متصلًا بثلاثة رؤوس ، فإن المنشور الناتج المنتظم من الدرجة 4 يحتوي دائمًا على دورة هاميلتونية، وفي جميع الأمثلة التي تم اختبارها، على تحليل هاميلتوني. بناءً على هذه الملاحظة، افترض ألسپاش وروزنفيلد في عام 1986 أن جميع المنشورات فوق الرسوم البيانية المنتظمة من الدرجة 3 والمتصلة بثلاثة رؤوس لها تحليل هاميلتوني. [ 7 ] [ 8 ]

من المعروف أن العديد من فئات الرسوم البيانية المنتظمة ثلاثية الرؤوس والمتصلة بثلاثة رؤوس تمتلك موشورات ذات تحليلات هاميلتونية. ويحدث هذا تحديدًا عندما يكون الرسم البياني المنتظم ثلاثي الرؤوس مستويًا وثنائي الأجزاء، أو عندما يكون رسمًا بيانيًا هالينيًا ، أو عندما يكون نفسه موشورًا أو سلم موبيوس ، أو عندما يكون رسمًا بيانيًا بيترسنيًا معمّمًا من رتبة قابلة للقسمة على أربعة. [ 8 ] [ 9 ]

الرسوم البيانية المتناظرة

يوجد عدد لا نهائي من الرسوم البيانية المتعدية الرؤوس (الرسوم البيانية التي يكون فيها كل رأس متناظرًا مع كل رأس آخر) التي لا تمتلك تحليلًا هاميلتونيًا. وينطبق هذا بشكل خاص على رسوم كايلي البيانية التي تصف رؤوسها عناصر مجموعة ، وتصف عناصرها الضرب بمولدات تلك المجموعة . كما يوجد عدد لا نهائي من رسوم كايلي المنتظمة من الدرجة 6 التي لا تمتلك تحليلًا هاميلتونيًا، وتوجد أيضًا رسوم كايلي بيانية ذات درجة زوجية كبيرة كيفما كانت بدون تحليل هاميلتوني. إحدى طرق إنشاء هذه الرسوم البيانية هي استخدام التوسعات المتكررة بواسطة الزمر، والتي تحافظ على التناظر ولا تُغير من وجود التحليل الهاميلتوني. [ 3 ]

الرسوم البيانية المتشعبة الموحدة

تُعدّ مسائل التفكيك للرسوم البيانية الفائقة عموماً أصعب بكثير من مسائل التفكيك للرسوم البيانية العادية. وعلى عكس الرسوم البيانية العادية، تسمح الرسوم البيانية الفائقة بوجود مفاهيم متعددة غير متكافئة للدورات (انظر دورات الرسوم البيانية الفائقة ).

أبسط هذه المفاهيم هي دورة بيرج . في عام 2014، أظهر كوهن وأوستوس [ 10 ] أن الدورة الكاملةك{\displaystyle k}- رسم بياني فائق منتظمكن(ك){\displaystyle K_{n}^{(k)}}يقبل التحلل إلى دورات هاميلتون بيرج كلمان{\displaystyle n}يقسم(نك){\displaystyle {\tbinom {n}{k}}}.

مشكلة لم تُحل في الرياضيات
بالنسبة للأعداد الصحيحةن{\displaystyle n}وك{\displaystyle k}أينن{\displaystyle n}يقسم(نك){\displaystyle {\tbinom {n}{k}}}، هل يكتملك{\displaystyle k}- رسم بياني فائق منتظمكن(ك){\displaystyle K_{n}^{(k)}}هل تقبل بتحليل هاميلتوني محكم؟
المزيد من المسائل غير المحلولة في الرياضيات

ومع ذلك، بالنسبة للمفهوم الأكثر شيوعًا للدورة في الرسم البياني الفائق - الدورة المحكمة - لا تزال هناك مشكلة مفتوحة فيما إذا كانت الدورة الكاملةك{\displaystyle k}- رسم بياني فائق منتظمكن(ك){\displaystyle K_{n}^{(k)}}تقبل هذه المسألة تحليلًا هاميلتونيًا. [ 11 ] وبصياغتها كمسألة ترتيب المقاعد من مسألة أوبرولفاخ المذكورة أعلاه، فإن إيجاد هذه التحليلات يتوافق مع الحالة التي تكون فيها كل مجموعة منك{\displaystyle k}يجلس الأشخاص بشكل متتالٍ مرة واحدة بالضبط. في هذه الحالة، يجب أن يكون عدد وجبات العشاء(ن-1ك-1)/ك{\displaystyle {\tbinom {n-1}{k-1}}/k}.

تتناول نظرية باراني مشكلة مماثلة، من خلال إيجاد تحليل للكاملك{\displaystyle k}- تحويل الرسم البياني الفائق المنتظم إلى تطابقات مثالية.

عدد عمليات التحلل

كل رسم بياني غير موجه منتظم من الدرجة 4 له عدد زوجي من تحليلات هاميلتونية. وبعبارة أدق، لكل حافتينهـ{\displaystyle e}وو{\displaystyle f}بالنسبة للرسم البياني المنتظم من الدرجة 4، عدد عمليات التفكيك الهاميلتوني التيهـ{\displaystyle e}وو{\displaystyle f}ينتمي إلى نفس الدورة إذا كان زوجيًا. إذا كان2ك{\displaystyle 2k}- الرسم البياني المنتظم له تحليل هاميلتوني، وله على الأقل عدد من التحليلات يساوي ثلاثة أضعاف مضروب عدد التحليلات.

(3ك-2)⋅(3ك-5)⋯7⋅4⋅1.{\displaystyle (3k-2)\cdot (3k-5)\cdots 7\cdot 4\cdot 1.}

على سبيل المثال، تحتوي الرسوم البيانية المنتظمة من الدرجة 4 التي لها تحليل هاميلتوني على أربعة منها على الأقل؛ وتحتوي الرسوم البيانية المنتظمة من الدرجة 6 التي لها تحليل هاميلتوني على 28 منها على الأقل، وهكذا. ويترتب على ذلك أن الرسوم البيانية الوحيدة التي تكون تحليلاتها الهاميلتونية فريدة هي الرسوم البيانية الدورية . [ 12 ]

التعقيد الحسابي

يُعد اختبار ما إذا كان لأي رسم بياني تحليل هاميلتوني مسألةً كاملةً من فئة NP ، سواءً في حالة الرسوم البيانية الموجهة أو غير الموجهة. [ 13 ] وعلى وجه الخصوص، تُعدّ هذه المسألة كاملةً من فئة NP بالنسبة للرسوم البيانية المنتظمة ذات درجة زوجية محددة؛ على سبيل المثال، بالنسبة للرسوم البيانية المنتظمة من الدرجة 4.

تكون الرسوم البيانية الخطية للرسوم البيانية المكعبة منتظمة من الدرجة 4، ولها تحليل هاميلتوني إذا وفقط إذا كان الرسم البياني المكعب الأساسي يحتوي على دورة هاميلتونية. [ 14 ] [ 15 ] ونتيجة لذلك، يظل تحليل هاميلتون مسألة NP-كاملة لفئات الرسوم البيانية التي تتضمن رسومًا بيانية خطية لحالات صعبة من مسألة الدورة الهاميلتونية . على سبيل المثال، يكون تحليل هاميلتون مسألة NP-كاملة للرسوم البيانية المستوية المنتظمة من الدرجة 4، لأنها تتضمن الرسوم البيانية الخطية للرسوم البيانية المستوية المكعبة. من ناحية أخرى، يشير هذا التكافؤ أيضًا إلى أن تحليل هاميلتوني سهل للرسوم البيانية الخطية المنتظمة من الدرجة 4 عندما تحتوي رسومها البيانية المكعبة الأساسية على مسائل دورة هاميلتونية سهلة.

من شبه المؤكد أن الرسوم البيانية المنتظمة العشوائية ذات الدرجة الزوجية لها تحليل هاميلتوني، والأهم من ذلك، أن هناك خوارزمية عشوائية متعددة الحدود ، والتي عند إدخال رسم بياني منتظم عشوائي ذي درجة زوجية، تجد بشكل شبه مؤكد تحليل هاميلتوني فيه. [ 16 ]

انظر أيضاً

  • التشعب الخطي ، نوع مختلف من التقسيم المقيد إلى رسوم بيانية فرعية ذات درجة قصوى اثنين

مراجع

  1. ↑ بيرموند، جيه.-سي. (1978)، "التحليلات الهاميلتونية للرسوم البيانية، والرسوم البيانية الموجهة، والرسوم البيانية الفائقة" ، في بولاباس، ب. (محرر)، التطورات في نظرية الرسوم البيانية ، حوليات الرياضيات المتقطعة، المجلد  3، الصفحات 21-28 ، doi : 10.1016/S0167-5060(08)70494-1 ، ISBN  9780720408430، MR 0505807 
  2. ↑ ألسپاش، برايان (2008)، "بناء واليكي الرائع"، نشرة معهد التوافقية وتطبيقاتها ، 52 : 7-20 ، MR 2394738 
  3. 1 2 براينت، دارين؛ دين، ماثيو (2015)، "الرسوم البيانية المتعدية على الرؤوس التي لا تحتوي على تحليل هاميلتوني"، مجلة نظرية التوافيق ، السلسلة ب، 114 : 237-246 ، arXiv : 1408.5211 ، doi : 10.1016/j.jctb.2015.05.007 ، MR 3354297 
  4. ↑Moon, John W. (1968), Topics on Tournaments, New York, Montreal, London: Holt, Rinehart and Winston, Exercise 9, page 9, MR 0256919
  5. ↑Kühn, Daniela; Osthus, Deryk (2013), "Hamilton decompositions of regular expanders: a proof of Kelly's conjecture for large tournaments", Advances in Mathematics, 237: 62–146, arXiv:1202.6219, doi:10.1016/j.aim.2013.01.005, MR 3028574
  6. ↑Bondy, J. A.; Häggkvist, R. (1981), "Edge-disjoint Hamilton cycles in 4-regular planar graphs", Aequationes Mathematicae, 22 (1): 42–45, doi:10.1007/BF02190157, MR 0623315
  7. ↑Alspach, Brian; Rosenfeld, Moshe (1986), "On Hamilton decompositions of prisms over simple 3-polytopes", Graphs and Combinatorics, 2 (1): 1–8, doi:10.1007/BF01788070, MR 1117125
  8. 12Rosenfeld, Moshe; Xiang, Ziqing (2014), "Hamiltonian decomposition of prisms over cubic graphs", Discrete Mathematics & Theoretical Computer Science, 16 (2): 111–124, doi:10.46298/dmtcs.2079, MR 3349112
  9. ↑Čada, Roman; Kaiser, Tomá; Rosenfeld, Moshe; Ryjáček, Zdeněk (2004), "Hamiltonian decompositions of prisms over cubic graphs", Discrete Mathematics, 286 (1–2): 45–56, doi:10.1016/j.disc.2003.11.044, MR 2084278
  10. ↑Kühn, D.; Osthus, D. (2014). "Decompositions of complete uniform hypergraphs into Hamilton Berge cycles". Journal of Combinatorial Theory, Series A. 126: 128–135. arXiv:1403.7932. doi:10.1016/j.jcta.2014.04.010.
  11. ↑Bailey, R.; Stevens, B. (2010). "Hamiltonian decompositions of complete k-uniform hypergraphs". Discrete Mathematics. 310 (22): 3088–3095. doi:10.1016/j.disc.2009.03.047.
  12. ↑ توماسون، أ. ج. (1978)، "دورات هاميلتون والرسوم البيانية ذات التلوين الفريد للحواف"، التقدم في نظرية الرسم البياني (مؤتمر كامبريدج التوافقي، كلية ترينيتي، كامبريدج، 1977) ، حوليات الرياضيات المتقطعة، المجلد 3، الصفحات 259-268 ، MR 0499124   
  13. ↑ بيروش، ب. (1984)، "اكتمال NP لبعض مسائل التقسيم والتغطية في الرسوم البيانية"، الرياضيات التطبيقية المنفصلة ، ​​8 (2): 195-208 ، doi : 10.1016/0166-218X(84)90101-X ، MR 0743024 
  14. ^ Kotzig، Anton (1957)، “Aus der Theorie der endlichen regulären Graphen dritten und vierten Grades”، Časopis Pro Pěstování Matematiky ، 82 : 76–92 ، دوى : 10.21136 / CPM.1957.117236 ، MR 0090815 
  15. ^ مارتن ، بيير (1976)، “Cycles hamiltoniens dans les graphes 4-réguliers 4-connexes”، Aequationes Mathematicae ، 14 (1/2): 37–40 ، دوى : 10.1007 / BF01836203 ، MR 0414442 
  16. ↑ كيم، جيونغ هان ؛ وورمالد، نيكولاس سي. (2001)، "المطابقات العشوائية التي تحفز دورات هاميلتون وتفكيكات هاميلتونية للرسوم البيانية المنتظمة العشوائية"، مجلة نظرية التوافيق ، السلسلة ب، 81 (1): 20-44 ، doi : 10.1006/jctb.2000.1991 ، MR 1809424