رسم بياني لهانوي

في نظرية الرسم البياني والرياضيات الترفيهية ، تعتبر رسوم هانوي البيانية رسومًا بيانية غير موجهة تمثل رؤوسها الحالات الممكنة للغز برج هانوي ، وتمثل حوافها التحركات المسموح بها بين أزواج الحالات.

تتكون الأحجية من مجموعة من الأقراص بأحجام مختلفة، موضوعة بترتيب تصاعدي على مجموعة ثابتة من الأبراج. رسم بياني هانوي لأحجية مع${\displaystyle n}$الأقراص على${\displaystyle k}$يُشار إلى الأبراج بـ${\displaystyle H_{k}^{n}}$[ ^{1 ] [ 2 ]} يتم تحديد كل حالة من حالات اللغز باختيار برج واحد لكل قرص، لذا فإن الرسم البياني يحتوي ^على${\displaystyle k^{n}}$الرؤوس. ^{[ 2 ]}

في حركات اللغز، يتم نقل القرص الأصغر الموجود على أحد الأبراج إما إلى برج غير مشغول أو إلى برج يكون قرصه الأصغر أكبر. إذا كان هناك${\displaystyle u}$في الأبراج غير المشغولة، يكون عدد التحركات المسموح بها هو

${\displaystyle {\binom {k}{2}}-{\binom {u}{2}},}$

والتي تتراوح من حد أقصى قدره${\displaystyle {\tbinom {k}{2}}}$ (متى${\displaystyle u}$هو صفر أو واحد و${\displaystyle {\tbinom {u}{2}}}$(صفر) إلى${\displaystyle k-1}$(عندما تكون جميع الأقراص على برج واحد و${\displaystyle u}$يكون${\displaystyle k-1}$وبالتالي، تتراوح درجات رؤوس الرسم البياني لهانوي من قيمة قصوى قدرها${\displaystyle {\tbinom {k}{2}}}$إلى الحد الأدنى من${\displaystyle k-1}$يبلغ العدد الإجمالي للحواف ^{[ 3 ]}

${\displaystyle {\frac {1}{2}}{\binom {k}{2}}{\bigl (}k^{n}-(k-2)^{n}{\bigr )}.}$

ل${\displaystyle k=0}$(بدون أقراص) توجد حالة واحدة فقط للغز ورأس واحد فقط للرسم البياني. لـ${\displaystyle k>0}$، الرسم البياني لهانوي${\displaystyle H_{k}^{n}}$يمكن تحليلها إلى${\displaystyle k}$نسخ من الرسم البياني الأصغر لهانوي${\displaystyle H_{k}^{n-1}}$نسخة واحدة لكل موضع للقرص الأكبر. وترتبط هذه النسخ ببعضها البعض فقط في الحالات التي يكون فيها القرص الأكبر حراً في الحركة: أي عندما يكون هو القرص الوحيد في برجه، ويكون برج آخر غير مشغول. ^{[ 4 ]}

تحتوي كل رسمة بيانية لهانوي على دورة هاميلتونية . ^{[ 5 ]}

رسم بياني لهانوي${\displaystyle H_{k}^{1}}$هو رسم بياني كامل على${\displaystyle k}$الرؤوس. ولأنها تحتوي على رسوم بيانية كاملة، فإن جميع رسوم هانوي الأكبر حجماً${\displaystyle H_{k}^{n}}$يتطلب على الأقل${\displaystyle k}$الألوان في أي رسم بياني للتلوين . يمكن تلوينها بدقة${\displaystyle k}$يتم تلوينها عن طريق جمع مؤشرات الأبراج التي تحتوي على كل قرص، وباستخدام باقي قسمة المجموع على${\displaystyle k}$مثل اللون. ^{[ 3 ]}

تُعد حالة الرسوم البيانية لهانوي ذات الأبراج الثلاثة حالة خاصة من حالات الرسوم البيانية لهانوي التي تمت دراستها جيدًا منذ عمل سكورر، غروندي وسميث (1944) ^{[ 1 ] [ 6 ] ،}${\displaystyle H_{3}^{n}}$تحتوي هذه الرسوم البيانية على 3n رأسًا ( ^{التسلسل} A000244 في OEIS ) و 3 ( 3 n - ¹ ) / 2 حافة ( التسلسل A029858 في OEIS ) . [ ^{7 ] وهي} رسوم بيانية دائرية ( رسوم بيانية تلامسية لأقراص وحدة غير متداخلة في المستوى)، بترتيب أقراص يشبه مثلث سيربينسكي . إحدى طرق إنشاء هذا الترتيب هي ترتيب أرقام مثلث باسكال على نقاط شبكة سداسية ، بمسافة وحدة واحدة، ووضع قرص وحدة على كل نقطة رقمها فردي. قطر هذه الرسوم البيانية، وطول حل الشكل القياسي للغز برج هانوي (حيث تبدأ جميع الأقراص من برج واحد ويجب أن تنتقل جميعها إلى برج آخر) هو${\displaystyle 2^{n}-1}$[ ^{2 ]​}

مشكلة لم تُحل في الرياضيات

ما هو قطر الرسوم البيانية؟${\displaystyle H_{k}^{n}}$ل${\displaystyle k>3}$؟

المزيد من المسائل غير المحلولة في الرياضيات

ل${\displaystyle k>3}$^{[ 2 ]} عندما لا يكون هيكل مخططات هانوي مفهوماً جيداً، فإن قطر هذه المخططات غير معروف.${\displaystyle k>4}$و${\displaystyle n>0}$أو عندما${\displaystyle k=4}$و${\displaystyle n>2}$هذه الرسوم البيانية غير مستوية. ^{[ 5 ]}

• مثلث سيربينسكي