نظرية شتاينيتز

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

عزز عمل لاحق لإبيفانوف برهان شتاينيتز على أن كل رسم بياني متعدد السطوح يمكن اختزاله إلى${\displaystyle K_{4}}$باستخدام تحويلات ΔY و YΔ، أثبت إبيفانوف أنه إذا تم تحديد رأسين في رسم بياني مستوٍ، فإنه يمكن اختزال الرسم البياني إلى حافة واحدة بين هذين الرأسين من خلال الجمع بين تحويلات ΔY و YΔ مع اختزالات متسلسلة-متوازية . ^{[ 10 ]} كان برهان إبيفانوف معقدًا وغير بنائي، لكن ترومبر بسّطه باستخدام طرق تعتمد على قواطع الرسوم البيانية . لاحظ ترومبر أن كل رسم بياني شبكي قابل للاختزال بواسطة تحويلات ΔY و YΔ بهذه الطريقة، وأن قابلية الاختزال هذه محفوظة بواسطة قواطع الرسوم البيانية، وأن كل رسم بياني مستوٍ هو قاطع لرسم بياني شبكي. ^{[ 11 ]} يمكن استخدام هذه الفكرة لاستبدال مبرهنة شتاينيتز التي تنص على وجود متتالية اختزال. بعد هذا الاستبدال، يمكن إكمال بقية البرهان باستخدام الاستقراء بنفس طريقة برهان شتاينيتز الأصلي. ^{[ 8 ]} بالنسبة لهذه البراهين، التي تُجرى باستخدام أي من طرق إيجاد متواليات تحويلات ΔY و YΔ، توجد رسوم بيانية متعددة السطوح تتطلب عددًا غير خطي من الخطوات. وبشكل أدق، يمكن اختزال أي رسم بياني مستوٍ باستخدام عدد من الخطوات لا يتجاوز ما يتناسب مع${\displaystyle n^{3/2}}$ويتطلب عدد لا نهائي من الرسوم البيانية عددًا من الخطوات يتناسب على الأقل مع${\displaystyle n^{3/2}}$، أين${\displaystyle n}$يمثل عدد الرؤوس في الرسم البياني. ^{[ 12 ] [ 13 ]}

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

إجهاد التوازن على رسم بياني لمكعب

مخروط ناقص يرفع الرسم المُجهد (بنفس المواضع ثنائية الأبعاد) إلى ثلاثي الأبعاد

إذا رُسم مخطط بياني في مستوى ذي حواف مستقيمة، يُعرَّف إجهاد التوازن بأنه تخصيص أعداد حقيقية غير صفرية (أوزان) للحواف، بحيث يكون كل رأس في الموضع المحدد بالمتوسط ​​المرجح لجيرانه. وفقًا لتطابق ماكسويل-كريمونا ، يمكن تحويل إجهاد التوازن إلى سطح ثلاثي الأبعاد متصل خطي متقطع، بحيث تُسقط الحواف التي تُشكل الحدود بين الأجزاء المستوية من السطح على الرسم المعطى. يُحدد وزن وطول كل حافة الفرق في ميول السطح على جانبي الحافة، وشرط أن يكون كل رأس في حالة توازن مع جيرانه يُكافئ شرط أن تؤدي فروق الميول هذه إلى تقاطع السطح مع نفسه بشكل صحيح في جوار الرأس. تُترجم الأوزان الموجبة إلى زوايا ثنائية محدبة بين وجهين من السطح الخطي المتقطع، بينما تُترجم الأوزان السالبة إلى زوايا ثنائية مقعرة. على النقيض من ذلك، ينشأ كل سطح خطي متصل متقطع من إجهاد توازن بهذه الطريقة. إذا رُسم مخطط مستوٍ محدود، وأُعطي إجهاد توازن بحيث تكون جميع الحواف الداخلية للرسم ذات أوزان موجبة، وجميع الحواف الخارجية ذات أوزان سالبة، فإنه بتحويل هذا الإجهاد إلى سطح ثلاثي الأبعاد بهذه الطريقة، ثم استبدال السطح المستوي الذي يمثل الجزء الخارجي من المخطط بمكمله في نفس المستوى، نحصل على متعدد السطوح محدب، يتميز بخاصية إضافية وهي أن إسقاطه العمودي على المستوى لا يحتوي على أي تقاطعات. ^{[ 15 ] [ 16 ]}

استُخدمت معادلة ماكسويل-كريمونا للحصول على تمثيلات متعددة السطوح للرسوم البيانية متعددة السطوح، وذلك بدمجها مع طريقة رسم الرسوم البيانية المستوية لـ WT Tutte ، والمعروفة باسم تضمين Tutte . تبدأ طريقة Tutte بتثبيت أحد أوجه الرسم البياني متعدد السطوح في وضع محدب في المستوى. سيصبح هذا الوجه هو الوجه الخارجي لرسم الرسم البياني. وتستمر الطريقة بوضع نظام من المعادلات الخطية في إحداثيات الرؤوس، حيث يُوضع كل رأس متبقٍ عند متوسط ​​إحداثيات جيرانه. وكما أوضح Tutte، فإن نظام المعادلات هذا سيكون له حل فريد، حيث يُرسم كل وجه من أوجه الرسم البياني كمضلع محدب. ^{[ 17 ]} وبشكل بديهي، يصف هذا الحل النمط الذي يمكن الحصول عليه باستبدال الحواف الداخلية للرسم البياني بنوابض مثالية وتركها تستقر في حالة الطاقة الدنيا. ^{[ 18 ]} والنتيجة هي إجهاد شبه متوازن: إذا تم إسناد وزن واحد لكل حافة داخلية، فإن كل رأس داخلي في الرسم يكون في حالة توازن. مع ذلك، ليس من الممكن دائمًا إسناد أعداد سالبة للحواف الخارجية بحيث تكون هي الأخرى في حالة توازن. يكون هذا الإسناد ممكنًا دائمًا عندما يكون الوجه الخارجي مثلثًا، وبالتالي يمكن استخدام هذه الطريقة لإنشاء أي رسم بياني متعدد السطوح ذي وجه مثلث. إذا لم يحتوي الرسم البياني متعدد السطوح على وجه مثلث، فإن الرسم البياني الثنائي الخاص به يحتوي على مثلث وهو أيضًا متعدد السطوح، لذا يمكن إنشاء الرسم البياني الثنائي بهذه الطريقة ثم إنشاء الرسم البياني الأصلي كمجسم قطبي متعدد السطوح للتنفيذ الثنائي. ^{[ 4 ] [ 19 ]} هناك طريقة بديلة لإنشاء المجسمات متعددة السطوح باستخدام الرفع تتجنب الازدواجية عن طريق اختيار أي وجه يحتوي على خمسة رؤوس على الأكثر كوجه خارجي. كل رسم بياني متعدد الأوجه له وجه كهذا، ومن خلال اختيار الشكل الثابت لهذا الوجه بعناية أكبر، يمكن رفع تضمين توت لبقية الرسم البياني. ^{[ 20 ]}

وفقًا لأحد أشكال نظرية تعبئة الدوائر ، لكل رسم بياني متعدد السطوح، يوجد نظام من الدوائر في المستوى أو على أي كرة، يمثل رؤوس ووجوه الرسم البياني، بحيث:

• يتم تمثيل كل رأسين متجاورين في الرسم البياني بدوائر متماسّة .
• يتم تمثيل كل وجهين متجاورين من الرسم البياني بدائرة مماسية،
• يتم تمثيل كل زوج من رأس ووجه يلامسه بدائرتين تتقاطعان بزاوية قائمة ، و
• جميع أزواج الدوائر الأخرى منفصلة عن بعضها البعض. ^{[ 21 ]}

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

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

وجد باحثون لاحقون خوارزميات تحقيق تعتمد على الرفع، وتستخدم عددًا خطيًا فقط من البتات لكل رأس. ^{[ 20 ] [ 24 ]} من الممكن أيضًا تخفيف شرط أن تكون الإحداثيات أعدادًا صحيحة، وتعيين الإحداثيات بطريقة تجعل${\displaystyle x}$إحداثيات الرؤوس هي أعداد صحيحة مميزة في النطاق من 0 إلى${\displaystyle 2n-4}$أما الإحداثيان الآخران فهما عددان حقيقيان في الفترة [0, 1] ، بحيث يكون طول كل ضلع واحدًا على الأقل، بينما يكون حجم المجسم متعدد السطوح خطيًا. ^{[ 25 ] [ 26 ]} من المعروف أن بعض الرسوم البيانية متعددة السطوح قابلة للتحقيق على شبكات ذات حجم متعدد الحدود فقط؛ وينطبق هذا بشكل خاص على الأهرامات (تحقيقات الرسوم البيانية الدائرية )، والموشورات (تحقيقات الرسوم البيانية الموشورية )، والمجسمات متعددة السطوح المكدسة (تحقيقات الشبكات الأبولونييّة ). ^{[ 27 ]}

هناك طريقة أخرى لبيان وجود تمثيلات عددية صحيحة، وهي أن لكل متعدد سطوح محدب ثلاثي الأبعاد متعدد سطوح عددي مكافئ له تركيبياً. ^{[ 23 ]} على سبيل المثال، لا يُعدّ المجسم ذو الاثني عشر وجهاً المنتظم متعدد سطوح عددي بحد ذاته، نظراً لأوجهه الخماسية المنتظمة، ولكنه يُمكن تمثيله كمجسم بيريتوهيدرون عددي مكافئ . ^{[ 20 ]} لا يكون هذا ممكناً دائماً في الأبعاد الأعلى، حيث توجد متعددات سطوح (مثل تلك المُنشأة من تكوين بيرلز ) ليس لها مكافئ عددي. ^{[ 28 ]}

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

في أي متعدد السطوح الذي يمثل رسمًا بيانيًا متعدد السطوح معينًا${\displaystyle G}$وجوه${\displaystyle G}$هي بالضبط الدورات في${\displaystyle G}$التي لا تفصل${\displaystyle G}$إلى عنصرين: أي إزالة دورة الوجه من${\displaystyle G}$يترك الباقي${\displaystyle G}$باعتبارها رسمًا بيانيًا فرعيًا متصلًا. تُسمى هذه الدورات بالدورات المحيطية . وبالتالي، يتم تحديد البنية التوافقية للوجوه (وليس أشكالها الهندسية) بشكل فريد من بنية الرسم البياني. وينص تعزيز آخر لنظرية شتاينيتز، من قِبل بارنيت وغرونباوم، على أنه لأي رسم بياني متعدد السطوح، وأي وجه من وجوه الرسم البياني، وأي مضلع محدب يمثل ذلك الوجه، من الممكن إيجاد تمثيل متعدد السطوح للرسم البياني بأكمله له الشكل المحدد للوجه المُعين. يرتبط هذا بنظرية توت، التي تنص على أنه يمكن رسم أي رسم بياني متعدد السطوح في المستوى مع جميع الوجوه محدبة وأي شكل محدد لوجهه الخارجي. ومع ذلك، فإن رسومات الرسم البياني المستوية التي تنتجها طريقة توت لا تتحول بالضرورة إلى متعددات سطوح محدبة. بدلاً من ذلك، يثبت بارنيت وغرونباوم هذه النتيجة باستخدام طريقة استقرائية. ^{[ 30 ]} من الممكن أيضًا دائمًا، بالنظر إلى رسم بياني متعدد السطوح${\displaystyle G}$ودورة عشوائية${\displaystyle C}$في${\displaystyle G}$، لإيجاد تحقق يكون فيه${\displaystyle C}$يشكل صورة ظلية للتنفيذ تحت الإسقاط المتوازي . ^{[ 31 ]}

يُقدّم تمثيل المجسمات متعددة الأوجه باستخدام نظرية تعبئة الدوائر تعزيزًا آخر لنظرية شتاينيتز: إذ يُمكن تمثيل أي رسم بياني مستوٍ ثلاثي الاتصال كمجسم محدب بحيث تكون جميع حوافه مماسية لنفس الكرة الوحدة ، وهي الكرة الوسطى للمجسم. ^{[ 22 ]} من خلال إجراء تحويل موبيوس مُختار بعناية لتعبئة الدوائر قبل تحويلها إلى مجسم متعدد الأوجه، يُمكن إيجاد تمثيل متعدد الأوجه يُحقق جميع تناظرات الرسم البياني الأساسي، بمعنى أن كل تماثل ذاتي للرسم البياني هو تناظر للتمثيل متعدد الأوجه. ^{[ 32 ] [ 33 ]} وبشكل أعم، إذا${\displaystyle G}$هو رسم بياني متعدد الأوجه و${\displaystyle K}$إذا كان أي جسم محدب ثلاثي الأبعاد أملس ، فمن الممكن إيجاد تمثيل متعدد السطوح لـ${\displaystyle G}$حيث تكون جميع الحواف مماسة لـ${\displaystyle K}$[ ^{34 ]​}

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