متعدد السطوح المتكامل

📅 آخر تحديث: ٢ أغسطس ٢٠٢٦
✍️ نُشر في: ٢ أغسطس ٢٠٢٦
📷 يحتوي على 17 صور
الموسوعة الحرة
مكعبمكعب ثماني الأوجهالمجسم الثمانيثماني السطوح المقطوع
(±1, ±1, ±1)(0, ±1, ±1)(0, 0, ±1)(0, ±1, ±2)
أربعة متعددات وجوه متكاملة في ثلاثة أبعاد

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

أمثلة

أنن{\displaystyle n}يمكن تمثيل المجسم البسيط المنتظم ذي الأبعاد n كمضلع متعدد الأوجه صحيح فيRن+1{\displaystyle \mathbb {R} ^{n+1}}الغلاف المحدب للنقاط الصحيحة التي تكون إحداثية واحدة منها تساوي واحدًا وبقية الإحداثيات تساوي صفرًا. وهناك نوع آخر مهم من الأشكال الهندسية التكاملية، وهو المخطط المتعامد ، والذي يمكن تشكيله على أنه الغلاف المحدب للنقاط الصحيحة التي تبدأ إحداثياتها بعدد من الآحاد المتتالية متبوعة بأصفار في جميع الإحداثيات المتبقية.ن{\displaystyle n}مكعب وحدة ذو أبعاد n فيRن{\displaystyle \mathbb {R} ^{n}}يحتوي المجسم التبادلي على رؤوس جميع النقاط الصحيحة التي إحداثياتها صفر أو واحد. أما المجسم التبادلي، فيحتوي على رؤوس تُحدد إحداثياتها بتطبيق جميع التبديلات الممكنة على المتجه.(1،2،...،ن){\displaystyle (1,2,...,n)}. إن المجسم التجميعي في تحقيق لوداي المحدب هو أيضًا متعدد الوجوه الصحيح وتشويه للمجسم التبادلي.

في مجال التحسين

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

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

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

بالنسبة لمتعدد السطوح الموصوف بمتباينات خطية، عندما يكون متعدد السطوح غير صحيح، يمكن إثبات عدم صحته بإيجاد رأس إحداثياته ​​ليست أعدادًا صحيحة. يمكن وصف هذا الرأس توافقيًا بتحديد مجموعة فرعية من المتباينات التي، عند تحويلها إلى نظام معادلات خطية ، يكون لها حل وحيد، والتحقق من أن نقطة الحل هذه تحقق جميع المتباينات الأخرى. لذلك، ينتمي اختبار الصحة إلى فئة التعقيد coNP للمسائل التي يمكن إثبات إجابتها السلبية بسهولة. وبشكل أكثر تحديدًا، فهو coNP-كامل . [ 6 ]

يتم ترميز العديد من الخصائص المهمة للمضلع المتكامل، بما في ذلك حجمه وعدد رؤوسه، بواسطة متعدد الحدود إيرهارت الخاص به . [ 7 ]

تُعدّ متعددات الوجوه التكاملية عنصرًا بارزًا في نظرية المتنوعات الطورية ، حيث تُقابل المتنوعات الطورية الإسقاطية المستقطبة. على سبيل المثال، المتنوع الطوري المُقابل للمُبسط هو فضاء إسقاطي . أما المتنوع الطوري المُقابل لمكعب الوحدة فهو تضمين سيغري لـن{\displaystyle n}ناتج ضرب الخط الإسقاطي.

في الهندسة الجبرية ، تُعدّ متعددات وجوه نيوتن مثالًا هامًا على متعددات الوجوه الشبكية، وهي عبارة عن أغلفة محدبة لمتجهات تمثل أسس كل متغير بدلالة متعددة حدود . على سبيل المثال، متعددة الحدودxy+2x2+y5+4{\displaystyle xy+2x^{2}+y^{5}+4}يتكون من أربعة فصول دراسية،xy{\displaystyle xy}مع متجه الأس (1،1)،2x2{\displaystyle 2x^{2}}مع متجه الأس (2,0)،y5{\displaystyle y^{5}}بمتجه الأس (0،5)، و4{\displaystyle 4}بمتجه أسّي (0,0). متعدد السطوح النيوتني الخاص به هو الغلاف المحدب للنقاط الأربع (1,1)، (2,0)، (0,5)، و(0,0). هذا الغلاف عبارة عن مثلث صحيح تقع النقطة (1,1) داخله، والنقاط الثلاث الأخرى هي رؤوسه.

انظر أيضاً

مراجع

  1. ↑ كورنويجول، جيرار (2001)، التحسين التوافقي: التعبئة والتغطية ، سلسلة مؤتمرات CBMS-NSF الإقليمية في الرياضيات التطبيقية، المجلد  74، فيلادلفيا، بنسلفانيا: جمعية الرياضيات الصناعية والتطبيقية (SIAM)، ص  4، doi : 10.1137/1.9780898717105 ، ISBN 0-89871-481-8MR 1828452​ 
  2. ↑ موروتو، كازو (2003)، التحليل المحدب المنفصل ، سلسلة دراسات SIAM في الرياضيات المنفصلة وتطبيقاتها، فيلادلفيا، بنسلفانيا: جمعية الرياضيات الصناعية والتطبيقية (SIAM)، ص 90، doi : 10.1137/1.9780898718508 ، hdl : 2433/149564 ، ISBN  0-89871-540-7، MR 1997998 
  3. ↑ ستانلي، ريتشارد ب. (1986)، "مضلعات مجموعتين جزئيتين"، الهندسة المنفصلة والحسابية ، 1 (1): 9-23 ، doi : 10.1007/BF02187680 ، MR 0824105 
  4. ^ لوفاسز، لازلو (1986). نظرية المطابقة . شمال هولندا. ص 269 – 274. ISBN  978-0-444-87916-5. OCLC 316569965 . 
  5. ^ لوفاسز، لازلو (1986). نظرية المطابقة . شمال هولندا. ص 274 – 281. ISBN  978-0-444-87916-5. OCLC 316569965 . 
  6. ↑ دينغ، غولي؛ فينغ، لي؛ زانغ، وينان (2008)، "تعقيد التعرف على الأنظمة الخطية ذات خصائص التكامل المحددة"، البرمجة الرياضية، السلسلة أ ، 114 (2): 321-334 ، doi : 10.1007/s10107-007-0103-y ، hdl : 10722/58972 ، MR 2393045 
  7. ↑ بارفينوك، أ. آي. (1994)، "حساب متعددة حدود إيرهارت لمتعدد سطوح شبكي محدب"، الهندسة المنفصلة والحسابية ، 12 (1): 35-48 ، doi : 10.1007/BF02574364 ، MR 1280575