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

في نظرية متعددات السطوح ، يُعدّ مخطط الحواف (المعروف أيضًا بمخطط الرؤوس والحواف أو ببساطة المخطط ) لمتعدد السطوح مخططًا تركيبيًا تتطابق رؤوسه وحوافه مباشرةً مع رؤوس وحواف متعدد السطوح. وباعتباره كائنًا تركيبيًا بحتًا ، يُشفّر مخطط الحواف معلومات التداخل، مُحددًا الرؤوس المتصلة بالحواف، ولكنه لا يحتفظ بالبيانات الهندسية مثل مواقع الرؤوس أو أطوال الحواف. ومن الأسماء الشائعة الأخرى لمخطط الحواف: الهيكل العظمي والهيكل العظمي الأحادي ، مع أن بعض المؤلفين يحصرون هذه المصطلحات للتضمين الهندسي الذي تُشكّله الرؤوس والحواف في الفضاء المحيط بمتعدد السطوح . ولا يوجد تدوين مُتفق عليه عالميًا لمخطط حواف متعدد السطوح.${\displaystyle P}$تتضمن الرموز الشائعة ما يلي:${\displaystyle G_{P}}$،${\displaystyle G(P)}$أو${\displaystyle \operatorname {skel} (P)}$.

لا يمكن تمثيل جميع الرسوم البيانية كرسوم بيانية لحواف متعددات الوجوه؛ وتُسمى تلك التي يمكن تمثيلها بهذه الطريقة بالرسوم البيانية متعددة الوجوه . كما تُسمى الرسوم البيانية لحواف متعددات الوجوه ثلاثية الأبعاد بالرسوم البيانية متعددة السطوح . تُعرف مشكلة تحديد ما إذا كان رسم بياني معين متعدد الوجوه أم لا بمشكلة التمثيل ، وهي مشكلة صعبة الحل (NP-hard) في الأبعاد العامة. في البعد الثالث، تُسمى هذه المشكلة أيضًا بمشكلة شتاينيتز نسبةً إلى حلها على يد إرنست شتاينيتز .

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

الرسم البياني للحواف لمتعدد السطوح المحدب هو رسم بياني بسيط محدود . وهو متصل ، حيث يمكن الحصول على مسار بين أي رأسين باستخدام خوارزمية السمبلكس . بالنسبة لمتعددات السطوح منخفضة الأبعاد، يتحدد هيكل الرسم البياني للحواف بشكل أساسي من خلال بُعد متعدد السطوح.

• المضلع الوحيد ذو البعد الصفري هو النقطة؛ ومخطط حوافها هو${\displaystyle K_{1}}$.
• المضلع الوحيد أحادي البعد هو القطعة المستقيمة؛ ومخطط حوافها هو${\displaystyle K_{2}}$.
• المضلعات ثنائية الأبعاد هي مضلعات . الرسم البياني للحواف لـ${\displaystyle n}$المضلع ذو الأضلاع هو${\displaystyle C_{n}}$، الدورة مع${\displaystyle n}$الرؤوس.
• تتميز الرسوم البيانية للحواف للمضلعات ثلاثية الأبعاد ببنية غنية ولكنها مفهومة جيدًا: وفقًا لنظرية ستينيتز، فإن الرسوم البيانية للحواف للمضلعات ثلاثية الأبعاد هي بالضبط الرسوم البيانية المستوية المتصلة بثلاثة رؤوس ، ولهذا السبب تُعرف أيضًا باسم الرسوم البيانية متعددة السطوح .

ل${\displaystyle d}$-متعددات الوجوه مع${\displaystyle d\geq 4}$لا توجد خصائص معروفة للرسوم البيانية للحواف. يمكن تقديم بعض العبارات العامة:

• يحتوي الرسم البياني للحواف على درجة دنيا على الأقل${\displaystyle d}$إذا كان كل رأس من رؤوس أ${\displaystyle d}$- للمضلع درجة محددة${\displaystyle d}$(أي أن الرسم البياني للحواف هو${\displaystyle d}$إذا كان الشكل متعدد الأوجه منتظمًا ، فإنه يُقال إنه بسيط .
• الرسم البياني للحواف هو${\displaystyle d}$- الرؤوس متصلة . هذا ما يُعرف بنظرية بالينسكي .
• يحتوي الرسم البياني للحواف على تقسيم فرعي للرسم البياني الكامل${\displaystyle K_{d+1}}$^{[ 1 ]} على وجه الخصوص ، لـ${\displaystyle d\geq 4}$، يحتوي الرسم البياني للحواف على${\displaystyle K_{5}}$-صغيرة وليست مستوية.

من الصعب عمومًا تحديد ما إذا كان رسم بياني معين هو رسم بياني لحواف متعدد السطوح، أي ما إذا كان رسمًا بيانيًا متعدد السطوح . بالنسبة لبعض فئات الرسوم البيانية، مثل الرسوم البيانية ذات الدرجة الدنيا${\displaystyle \delta \leq 3}$يمكن أن تساعد الخصائص المذكورة أعلاه في حسم هذه المسألة. على سبيل المثال، مخطط بيترسن منتظم من الدرجة الثالثة . وبالتالي، لو كان متعدد الأوجه، لكان مخطط حواف متعدد الأوجه ثلاثي الأبعاد. إلا أن مخطط بيترسن ليس مستوياً، وبالتالي لا يمكن أن يكون مخطط حواف متعدد الأوجه من الدرجة الثالثة.

للرسوم البيانية ذات الدرجة الدنيا${\displaystyle \delta \geq 4}$تُعدّ الإجابة عن هذه الأسئلة أصعب بكثير عمومًا. فعلى سبيل المثال، حتى يوليو 2025، لم يكن معروفًا ما إذا كان حاصل ضرب الرسم البياني الديكارتي لرسمين بيانيين من نوع بيترسن متعدد الأوجه. ^{[ 2 ]} ومن المعروف أنه إذا كان متعدد الأوجه، فلا بد أن يكون متعدد الأوجه من أربعة أو خمسة أبعاد. ^{[ 3 ]}

بعض العمليات على متعددات الوجوه تُترجم إلى رسوم بيانية لحوافها بطريقة طبيعية.

• الرسم البياني للحواف في الضرب الديكارتي${\displaystyle P\times Q}$يمثل حاصل الضرب الديكارتي للرسوم البيانية للحواف لمضلعين متعددي الوجوه${\displaystyle P}$و${\displaystyle Q}$على سبيل المثال، ناتج رسم بياني دوري و${\displaystyle K_{1}}$هو الرسم البياني للحواف في منشور . توجد رسوم بيانية غير متعددة الأوجه يكون ناتجها متعدد الأوجه. ^{[ 3 ]}
• الرسم البياني للحواف الخاصة بالوصلة${\displaystyle P\star Q}$إن عملية الربط بين متعددي الوجوه هي عملية ربط الرسوم البيانية للحواف لـ${\displaystyle P}$و${\displaystyle Q}$يتم إنشاء وصلة الرسم البياني من الاتحاد المنفصل لرسوم بيانية الحواف عن طريق جمع جميع الحواف بينها. ويتم الحصول على رسم بياني الحواف نفسه للمجموع المباشر.${\displaystyle P\oplus Q}$(ثنائي الضرب الديكارتي) بافتراض أن كلاهما${\displaystyle P}$و${\displaystyle Q}$لها أبعاد لا تقل عن اثنين.
• بالنسبة للمضلعات ثلاثية الأبعاد، فإن الرسم البياني للحواف للمضلع الثنائي هو الرسم البياني الثنائي للرسم البياني للحواف الخاص به.

بمعرفة مخطط حواف متعدد السطوح ذي بُعد ثلاثة أو أقل، يُمكن إعادة بناء التوافقيات الكاملة لهذا المتعدد ، أي القائمة الكاملة للوجوه والتقاطعات بينها. على سبيل المثال، تتطابق الوجوه ثنائية الأبعاد لمتعدد سطوح ثلاثي الأبعاد تمامًا مع الدورات المستحثة غير المنفصلة في مخطط الحواف. ^{[ 5 ]} كذلك، بالنسبة لمتعددات السطوح ذات الأبعاد حتى ثلاثة، يُمكن تحديد بُعد متعدد السطوح من مخطط حوافه.${\displaystyle d\geq 4}$لا ينطبق أي من هذين الأمرين. توجد متعددات وجوه متميزة توافقياً ذات رسوم بيانية متماثلة للحواف، بل وحتى متعددات وجوه ذات أبعاد مختلفة ذات رسوم بيانية متماثلة للحواف.

• تجتاز خوارزمية سيمبلكس الرسم البياني للحواف لمتعدد السطوح لإيجاد الحل الأمثل لبرنامج خطي .
• تنص فرضية هيرش على أن الرسم البياني للحواف لـ${\displaystyle d}$- قطر متعدد الأوجه لا يتجاوز${\displaystyle d}$عثر سانتوس على مثال مضاد في عام 2012. ^{[ 12 ]} ومنذ ذلك الحين، أُعيدت صياغة الفرضية بطرق مختلفة. وحتى يونيو 2025، لم يكن هناك حد متعدد الحدود على القطر في${\displaystyle d}$معروف.
• تاريخياً، نشأت مصطلحات "الرأس" و"الحافة" للرسوم البيانية في دراسة متعددات السطوح ولم يتم اعتمادها في نظرية الرسوم البيانية إلا لاحقاً .