الرسم البياني المكعب الفائق

في نظرية الرسم البياني ، الرسم البياني المكعب الفائق${\displaystyle Q_{n}}$هو الرسم البياني للحواف لـ${\displaystyle n}$المكعب الفائق ذو الأبعاد n ، أي أنه الرسم البياني المُشكَّل من رؤوس وحواف المكعب الفائق. على سبيل المثال، الرسم البياني للمكعب${\displaystyle Q_{3}}$هو الرسم البياني الذي يتكون من 8 رؤوس و 12 حافة لمكعب ثلاثي الأبعاد. ${\displaystyle Q_{n}}$لديه${\displaystyle 2^{n}}$الرؤوس ،${\displaystyle 2^{n-1}n}$وهو رسم بياني منتظم ذو حواف${\displaystyle n}$حواف تلامس كل رأس.

الرسم البياني المكعب الفائق${\displaystyle Q_{n}}$يمكن أيضًا إنشاء ذلك عن طريق إنشاء رأس لكل مجموعة فرعية من${\displaystyle n}$مجموعة من n عنصر، مع وجود رأسين متجاورين عندما تختلف مجموعاتهما الفرعية في عنصر واحد، أو عن طريق إنشاء رأس لكل${\displaystyle n}$عدد ثنائي مكون من خانات ، حيث تكون رأسيهما متجاورتين عندما يختلف تمثيلهما الثنائي في خانة واحدة. وهو${\displaystyle n}$حاصل الضرب الديكارتي ذو الرتبة n للرسم البياني الكامل ذي الرأسين ، ويمكن تقسيمه إلى نسختين من${\displaystyle Q_{n-1}}$متصلين ببعضهم البعض بتطابق تام .

لا ينبغي الخلط بين الرسوم البيانية المكعبة الفائقة والرسوم البيانية المكعبة ، وهي رسوم بيانية لها ثلاثة حواف فقط تلامس كل رأس. الرسم البياني المكعب الفائق الوحيد${\displaystyle Q_{n}}$هذا رسم بياني مكعب، وهو الرسم البياني المكعب${\displaystyle Q_{3}}$.

الرسم البياني المكعب الفائق${\displaystyle Q_{n}}$يمكن إنشاء مجموعة من عائلة المجموعات الجزئية لمجموعة تحتوي على${\displaystyle n}$يمكن إنشاء العناصر عن طريق إنشاء رأس لكل مجموعة جزئية ممكنة وربط رأسين بحافة عندما تختلف المجموعات الجزئية المتناظرة في عنصر واحد. وبالمثل، يمكن إنشاؤها باستخدام${\displaystyle 2^{n}}$الرؤوس الموسومة بـ${\displaystyle n}$الأعداد الثنائية ذات n بت ، وربط رأسين بحافة عندما تكون مسافة هامينغ بين تسمياتهما تساوي واحدًا. هذان التركيبان مرتبطان ارتباطًا وثيقًا: يمكن تفسير العدد الثنائي على أنه مجموعة (مجموعة المواضع التي يحتوي فيها على رقم غير صفري)، وتختلف مجموعتان من هذا النوع في عنصر واحد فقط عندما تكون مسافة هامينغ بين العددين الثنائيين المتناظرين تساوي واحدًا.

بدلاً عن ذلك،${\displaystyle Q_{n}}$يمكن بناؤها من اتحاد منفصل لمكعبين فائقين${\displaystyle Q_{n-1}}$، وذلك بإضافة حافة من كل رأس في نسخة واحدة من${\displaystyle Q_{n-1}}$إلى الرأس المقابل في النسخة الأخرى، كما هو موضح في الشكل. تشكل الحواف المتصلة تطابقًا تامًا .

يُقدّم البناء المذكور أعلاه خوارزمية تكرارية لإنشاء مصفوفة التجاور لمكعب فائق،${\displaystyle A_{n}}$يتم النسخ عبر منتج Kronecker${\displaystyle \otimes _{K}}$بحيث تكون النسختان من${\displaystyle Q_{n-1}}$يحتوي على مصفوفة تجاور${\displaystyle \mathrm {1} _{2}\otimes _{K}A_{n-1}}$،أين${\displaystyle 1_{d}}$هو${\displaystyle d\times d}$مصفوفة الوحدة . في الوقت نفسه، تحتوي الحواف المتصلة على مصفوفة تجاور.${\displaystyle A_{1}\otimes _{K}1_{2^{n-1}}}$. مجموع هذين الحدين يعطي دالة تكرارية لمصفوفة التجاور لمكعب فائق:$${\displaystyle A_{n}={\begin{cases}1_{2}\otimes _{K}A_{n-1}+A_{1}\otimes _{K}1_{2^{n-1}}&{\text{إذا كان }}n>1\\{\begin{bmatrix}0&1\\1&0\end{bmatrix}}&{\text{إذا كان }}n=1\end{cases}}}$$ بناء آخر لـ${\displaystyle Q_{n}}$هو حاصل الضرب الديكارتي لـ${\displaystyle n}$ الرسوم البيانية الكاملة ذات الرأسين${\displaystyle K_{2}}$. بشكل عام، يُطلق على حاصل الضرب الديكارتي لنسخ من رسم بياني كامل اسم رسم بياني هامينغ ؛ وتُعد الرسوم البيانية المكعبة الفائقة أمثلة على رسوم بيانية هامينغ.

الرسم البياني${\displaystyle Q_{0}}$يتكون من رأس واحد، بينما${\displaystyle Q_{1}}$هو الرسم البياني الكامل على رأسين.

${\displaystyle Q_{2}}$هي دورة طولها 4.

الرسم البياني${\displaystyle Q_{3}}$هو الهيكل العظمي للمكعب وهو رسم بياني مستوٍ بثمانية رؤوس واثني عشر ضلعًا .

الرسم البياني${\displaystyle Q_{4}}$هو رسم ليفي لتكوين موبيوس . وهو أيضًا رسم الفارس لتكوين حلقي${\displaystyle 4\times 4}$رقعة الشطرنج . ^{[ 1 ]}

تُعرف مشكلة إيجاد أطول مسار أو دورة تمثل رسمًا بيانيًا فرعيًا مستحثًا لرسم بياني مكعب فائق معين باسم مشكلة الثعبان في الصندوق .

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

• رسم بياني دي بروين
• دورات متصلة مكعبة
• مكعب فيبوناتشي
• رسم بياني مكعب مطوي
• رسم بياني فرانكل-رودل
• رسم بياني مكعب مقسم إلى نصفين
• طوبولوجيا شبكة المكعب الفائق
• مكعب جزئي

• هاراري، ف .؛ هايز، ج.ب.؛ وو، هـ.-ج. (1988)، "دراسة استقصائية لنظرية الرسوم البيانية المكعبة الفائقة"، الحوسبة والرياضيات مع التطبيقات ، 15 (4): 277-289 ، doi : 10.1016/0898-1221(88)90213-1 ، hdl : 2027.42/27522.