التوافقية متعددة الأوجه

علم التوافق متعدد السطوح هو فرع من فروع الرياضيات ، ضمن علم التوافق والهندسة المنفصلة ، ​​يدرس مشاكل عد ووصف وجوه المجسمات المحدبة والمجسمات المحدبة ذات الأبعاد الأعلى .

ينقسم البحث في التوافقية متعددة الأوجه إلى مجالين متميزين. يدرس علماء الرياضيات في هذا المجال توافقية متعددات الأوجه؛ فعلى سبيل المثال، يبحثون عن متباينات تصف العلاقات بين أعداد الرؤوس والحواف والوجوه ذات الأبعاد الأعلى في متعددات الأوجه العشوائية أو في فئات فرعية مهمة معينة من متعددات الأوجه، ويدرسون خصائص توافقية أخرى لمتعددات الأوجه مثل اتصالها وقطرها ( عدد الخطوات اللازمة للوصول إلى أي رأس من أي رأس آخر). بالإضافة إلى ذلك، يستخدم العديد من علماء الحاسوب مصطلح "التوافقية متعددة الأوجه" لوصف الأبحاث التي تتناول الأوصاف الدقيقة لوجوه بعض متعددات الأوجه المحددة (وخاصة متعددات الأوجه 0-1، التي تمثل رؤوسها مجموعات جزئية من مكعب فائق ) والناشئة عن مسائل البرمجة العددية الصحيحة .

يمكن تعريف وجه متعدد السطوح المحدب P بأنه تقاطع P مع نصف فضاء مغلق H بحيث لا يحتوي حد H على أي نقطة داخلية من P. بُعد الوجه هو بُعد غلافه. الوجوه ذات البُعد الصفري هي الرؤوس نفسها، والوجوه ذات البُعد الواحد (وتُسمى الحواف ) هي القطع المستقيمة التي تربط أزواجًا من الرؤوس. تجدر الإشارة إلى أن هذا التعريف يشمل أيضًا المجموعة الفارغة ومتعدد السطوح P بأكمله كوجوه . إذا كان بُعد P نفسه d ، فإن وجوه P ذات البُعد d − 1 تُسمى أوجه P ، والوجوه ذات البُعد d − 2 تُسمى حوافًا . ^{[ 1 ]} يمكن ترتيب وجوه P جزئيًا بالتضمين، لتشكيل شبكة وجوه يكون عنصرها العلوي P نفسه وعنصرها السفلي المجموعة الفارغة.    

يُعدّ متجه ƒ للمضلع أداةً أساسيةً في التوافقية متعددة الأوجه ، ^{[ 2 ]} وهو المتجه ( f0 _, f1 , ..., fd _{- 1} ) حيث يُمثّل fi عدد خصائص المضلع ذي البُعد i . على سبيل المثال، للمكعب ثمانية رؤوس، واثنا عشر ضلعًا، وستة أوجه، لذا فإن متجه ƒ الخاص به هو (8, 12, 6). أما _{المضلع الثنائي ،} فيحتوي متجه ƒ الخاص به على نفس الأرقام ولكن بترتيب عكسي؛ وبالتالي، على سبيل المثال، يحتوي ثماني السطوح المنتظم ، وهو المضلع الثنائي للمكعب، على متجه ƒ (6, 12, 8). تتضمن مصفوفات التكوين متجهات ƒ للمضلعات المنتظمة كعناصر قطرية.  

يُشكّل متجه ƒ الموسّع بربط الرقم واحد في كل طرف من طرفي متجه ƒ، مع حساب عدد العناصر في جميع مستويات شبكة الأوجه؛ فعلى الجانب الأيسر من المتجه، f ₋₁  =  1 يُحسب المجموعة الفارغة كوجه، بينما على الجانب الأيمن، f _d  =  1 يُحسب P نفسه. بالنسبة للمكعب، يكون متجه ƒ الموسّع (1، 8، 12، 6، 1)، وبالنسبة للمجسم الثماني الأوجه يكون (1، 6، 12، 8، 1). على الرغم من أن متجهات هذه المجسمات متعددة الأوجه أحادية النمط (تزداد المعاملات، مرتبة من اليسار إلى اليمين، إلى قيمة عظمى ثم تتناقص)، إلا أن هناك مجسمات متعددة الأوجه ذات أبعاد أعلى لا ينطبق عليها هذا. ^{[ 3 ]}

بالنسبة للمضلعات البسيطة (المضلعات التي يكون فيها كل وجه عبارة عن مضلع بسيط )، من الملائم غالبًا تحويل هذه المتجهات، مما ينتج عنه متجه مختلف يُسمى متجه h . إذا فسرنا حدود متجه ƒ (مع حذف الرقم 1 الأخير) على أنها معاملات لكثيرة الحدود ƒ( x )  =  Σ f ₍ x) ^{d ( -i - 1)}     (على سبيل المثال، بالنسبة للمجسم الثماني الأوجه، تعطينا هذه كثيرة الحدود ƒ(x) = x³ + 6x² + 12x ⁺ 8 ) ، فإن  متجه h يسرد ^{معاملات} كثيرة الحدود h ( x ) = ƒ ( x - 1 ) ( مرة أخرى ، بالنسبة للمجسم الثماني الأوجه، h ( x ) = x³ + ^3x² + 3x + ¹ ) . ^{[ 4 ]} كما كتب زيغلر، "بالنسبة لمختلف المشاكل المتعلقة بالمضلعات البسيطة، فإن المتجهات h هي طريقة أكثر ملاءمة وإيجازًا لترميز المعلومات حول أرقام الوجوه من المتجهات ƒ ".                   

أهم علاقة بين معاملات متجه ƒ لمتعدد السطوح هي صيغة أويلر Σ(−1) ⁱ f _i = 0، حيث تتراوح حدود المجموع على معاملات متجه ƒ الممتد. في ثلاثة أبعاد، يؤدي نقل الرقمين 1 في طرفي متجه ƒ الممتد (1, v , e , f , 1) إلى الطرف الأيمن من المعادلة إلى تحويل هذه المتطابقة إلى الصيغة الأكثر شيوعًا v − e + f = 2. وبما أن كل وجه من أوجه متعدد السطوح ثلاثي الأبعاد يحتوي على ثلاثة أضلاع على الأقل، فإنه بالحساب المزدوج ينتج أن 2 e ≥ 3 f ، وباستخدام هذه المتباينة لحذف e و f من صيغة أويلر، نحصل على المتباينتين التاليتين: e ≤ 3 v − 6 و f ≤ 2 v − 4 . بحسب الازدواجية، فإن e ≤ 3 f − 6 و v ≤ 2 f − 4. ويترتب على نظرية شتاينيتز أن أي متجه صحيح ثلاثي الأبعاد يحقق هذه المتساويات والمتباينات هو متجه ƒ لمتعدد السطوح المحدب. ^{[ 5 ]}

في الأبعاد الأعلى، تكتسب علاقات أخرى بين عدد أوجه متعدد السطوح أهميةً بالغة، بما في ذلك معادلات دين-سومرفيل التي، عند التعبير عنها بدلالة متجهات h لمتعددات السطوح التبسيطية، تأخذ الشكل البسيط h _{_k} = h _{_{d - k}} لجميع قيم k . يكافئ مثال هذه المعادلات عندما k = 0 صيغة أويلر، ولكن بالنسبة لـ d > 3، تكون الأمثلة الأخرى لهذه المعادلات مستقلة خطيًا عن بعضها البعض، وتقيد متجهات h (وبالتالي متجهات ƒ أيضًا) بطرق إضافية. ^{[ 4 ]}

هناك متباينة أخرى مهمة تتعلق بعدد وجوه متعدد السطوح، وهي نظرية الحد الأعلى ، التي أثبتها ماكمولين (1970) لأول مرة ، والتي تنص على أن متعدد السطوح ذو البعد d والذي يحتوي على n رأسًا يمكن أن يحتوي على عدد من الوجوه من أي بُعد آخر لا يتجاوز عدد الوجوه من متعدد السطوح المجاور له نفس عدد الرؤوس:

${\displaystyle f_{k-1}\leq \sum _{i=0}^{d/2}{}^{*}\left({\binom {di}{ki}}+{\binom {i}{k-d+i}}\right){\binom {nd-1+i}{i}},}$

حيث تشير العلامة النجمية إلى أنه يجب تقسيم الحد الأخير من المجموع إلى النصف عندما يكون d زوجيًا. ^{[ 6 ]} ويعني هذا، تقاربيًا، أن هناك على الأكثر${\displaystyle \scriptstyle O(n^{\lfloor d/2\rfloor })}$وجوه من جميع الأبعاد.

حتى في أربعة أبعاد، فإن مجموعة المتجهات الممكنة لـ ƒ للمضلعات المحدبة لا تشكل مجموعة فرعية محدبة من الشبكة الصحيحة رباعية الأبعاد، ولا يزال الكثير مجهولاً حول القيم الممكنة لهذه المتجهات. ^{[ 7 ]}

إلى جانب التحقيق في أعداد وجوه متعددات الوجوه، درس الباحثون خصائص تركيبية أخرى لها، مثل أوصاف الرسوم البيانية التي تم الحصول عليها من رؤوس وحواف متعددات الوجوه (هياكلها الهيكلية 1 ).

تنص نظرية بالينسكي على أن الرسم البياني الناتج بهذه الطريقة من أي متعدد سطوح محدب ذي بُعد d يكون متصلاً من حيث الرؤوس من الدرجة d . ^{[ 8 ]} في حالة متعددات السطوح ثلاثية الأبعاد، يمكن استخدام هذه الخاصية والتسطيح لوصف رسوم متعددات السطوح بدقة: تنص نظرية شتاينيتز على أن G هو هيكل متعدد السطوح ثلاثي الأبعاد إذا وفقط إذا كان G رسمًا بيانيًا مستويًا متصلاً من حيث الرؤوس من الدرجة 3. ^{[ 9 ]}

تنص نظرية بليند وماني -ليفتسكا (1987) (التي سبق أن افترضها ميخا بيرلز ) على أنه يمكن إعادة بناء بنية وجوه متعدد السطوح البسيط من رسمه البياني. أي، إذا كان رسم بياني غير موجه معين هو الهيكل العظمي لمتعدد سطوح بسيط، فلا يوجد سوى متعدد سطوح واحد (حتى التكافؤ التوافقي) ينطبق عليه هذا. وهذا يتناقض تمامًا مع متعددات السطوح المتجاورة (غير البسيطة) التي يكون رسمها البياني رسمًا بيانيًا كاملًا ؛ إذ يمكن أن يكون هناك العديد من متعددات السطوح المتجاورة المختلفة لنفس الرسم البياني. وقدّم كالاي (1988) برهانًا آخر لهذه النظرية استنادًا إلى اتجاهات المصب الفريدة ، وبيّن فريدمان (2009) كيفية استخدام هذه النظرية لاستنباط خوارزمية زمنية متعددة الحدود لإعادة بناء شبكات وجوه متعددات السطوح البسيطة من رسومها البيانية. ومع ذلك، فإن اختبار ما إذا كان من الممكن تحقيق رسم بياني أو شبكة معينة كشبكة وجه لمتعدد الوجوه البسيط يعادل (بالقطبية) تحقيق متعددات الوجوه التبسيطية ، والتي ثبت أنها كاملة بالنسبة للنظرية الوجودية للأعداد الحقيقية بواسطة أديبراسيتو وبادرول (2017) .

في سياق طريقة السمبلكس للبرمجة الخطية ، من المهم فهم قطر متعدد السطوح، وهو الحد الأدنى لعدد الحواف اللازمة للوصول إلى أي رأس عبر مسار من أي رأس آخر. يُحدد نظام المتباينات الخطية للبرمجة الخطية أوجه متعدد السطوح التي تُمثل جميع الحلول الممكنة للبرنامج، وتجد طريقة السمبلكس الحل الأمثل باتباع مسار في هذا متعدد السطوح. وبالتالي، يُوفر القطر حدًا أدنى لعدد الخطوات التي تتطلبها هذه الطريقة. وقد اقترحت حدسية هيرش ، التي تم دحضها الآن، حدًا قويًا (خطيًا) لحجم قطر متعدد السطوح ذي الأبعاد الثابتة.${\displaystyle d}$وعدد الجوانب${\displaystyle n}$قد يكون ذلك. ^{[ 10 ]} أضعف (شبه متعدد الحدود في${\displaystyle d}$و${\displaystyle n}$^{[ 11 ]} كما أن الحدود العليا لأقطارها معروفة، بالإضافة إلى براهين حدسية هيرش لفئات خاصة من متعددات الوجوه. ^{[ 12 ]}

إن تحديد ما إذا كان عدد رؤوس متعدد الوجوه المعطى محدودًا بعدد طبيعي k هو مشكلة صعبة حسابيًا وكاملة بالنسبة لفئة التعقيد PP . ^{[ 13 ]}

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

كمثال، لنأخذ متعدد السطوح بيركوف ، وهو مجموعة المصفوفات من الرتبة n × n التي يمكن تكوينها من تركيبات محدبة لمصفوفات التبديل . وبصورة مكافئة، يمكن اعتبار رؤوسه بمثابة وصف لجميع المطابقات التامة في رسم بياني ثنائي الأجزاء كامل ، ويمكن تفسير مسألة التحسين الخطي على هذا المتعدد السطوح على أنها مسألة مطابقة تامة ثنائية الأجزاء بأقل وزن. تنص نظرية بيركوف-فون نيومان على أنه يمكن وصف هذا المتعدد السطوح بنوعين من المتباينات أو المتساويات الخطية. أولًا، لكل خلية في المصفوفة، يوجد قيد بأن تكون قيمة هذه الخلية غير سالبة. ثانيًا، لكل صف أو عمود في المصفوفة، يوجد قيد بأن يكون مجموع الخلايا في ذلك الصف أو العمود مساويًا للواحد. تحدد قيود الصف والعمود فضاءً فرعياً خطياً ذا بُعد n ² − 2 n + 1 يقع فيه متعدد السطوح بيركوف، وتحدد قيود عدم السلبية أوجه متعدد السطوح بيركوف داخل ذلك الفضاء الفرعي.      

مع ذلك، يتميز متعدد السطوح بيركوف بكونه غير عادي، إذ يتوفر وصف كامل لأوجهه. أما بالنسبة للعديد من متعددات السطوح الأخرى من النوع 0-1، فإن عدد أوجهها هائل، ولا يتوفر سوى وصف جزئي لها. ^{[ 14 ]}

• متعدد الأوجه المجرد
• الجبر التبادلي التوافقي
• متعدد الأوجه ماترويد
• ترتيب متعدد الأوجه
• كرة تبسيطية
• متعدد السطوح المتطابق المستقر

• كالاي، جيل (2008)، خمس مسائل مفتوحة تتعلق بالمضلعات المحدبة.