نظرية فاغنر

في نظرية المخططات ، تُعدّ نظرية فاغنر وصفًا رياضيًا للمخططات المستوية ، سُمّيت نسبةً إلى كلاوس فاغنر ، وتنص على أن المخطط المحدود يكون مستويًا إذا وفقط إذا لم تتضمن حدوده الجزئية أيًا من K₅ ( المخطط الكامل ذو الخمسة رؤوس ) أو K₃ _,₃ ( مخطط المنفعة ، وهو مخطط ثنائي الأجزاء كامل ذو ستة رؤوس). كانت هذه إحدى أوائل النتائج في نظرية حدود المخططات الجزئية، _ويمكن اعتبارها مقدمة لنظرية روبرتسون-سيمور .

التمثيل المستوي لرسم بياني مُعطى هو رسم لهذا الرسم في المستوى الإقليدي ، حيث تمثل النقاط رؤوسه والمنحنيات حوافه ، بحيث تكون التقاطعات الوحيدة بين أزواج الحواف عند نقطة مشتركة بينهما. أما الرسم البياني المصغر لرسم بياني مُعطى فهو رسم بياني آخر يتكون من حذف رؤوس وحواف وتقليص حواف. عند تقليص حافة، تُدمج نقطتا نهايتها لتشكيل رأس واحد. في بعض صيغ نظرية الرسوم البيانية المصغرة، يُبسط الرسم البياني الناتج عن التقليص بإزالة الحلقات الذاتية والتجاورات المتعددة، بينما في صيغ أخرى يُسمح بالرسوم البيانية المتعددة ، لكن هذا الاختلاف لا يؤثر على نظرية فاغنر. تنص النظرية على أن لكل رسم بياني إما تمثيلًا مستويًا، أو رسمًا بيانيًا مصغرًا من أحد نوعين: الرسم البياني الكامل K⁵ أو الرسم البياني الثنائي الكامل K³ _{, ³} .

إذا كان الرسم البياني مستويًا، فإن جميع أجزاءه الصغرى تكون كذلك أيضًا: فحذف الرؤوس والحواف يحافظ على الاستواء، ويمكن أيضًا تقليص الحواف مع الحفاظ على الاستواء، وذلك بترك إحدى نقطتي نهاية الحافة المُقلصة في مكانها وتوجيه جميع الحواف المتصلة بالنقطة الأخرى على طول مسار الحافة المُقلصة. الرسم البياني غير المستوي ذو الحد الأدنى من الأجزاء الصغرى هو رسم بياني غير مستوٍ، ولكن جميع أجزائه الصغرى الصحيحة (الأجزاء الصغرى المُشكّلة من خلال حذف أو تقليص واحد على الأقل) تكون مستوية. وبعبارة أخرى، تنص نظرية فاغنر على أنه لا يوجد سوى رسمين بيانيين غير مستويين ذوي حد أدنى من الأجزاء الصغرى، وهما K₅ و K₃ _{, ₃} .

_{تنص نتيجة أخرى ،} تُعرف أحيانًا باسم نظرية فاغنر، على أن الرسم البياني رباعي الاتصال يكون مستويًا إذا وفقط إذا لم يكن لديه مُصغِّر K⁵ . أي، بافتراض مستوى اتصال أعلى، يُمكن الاستغناء عن الرسم البياني K⁳ _{,³ في التوصيف، ليتبقى مُصغِّر واحد ممنوع فقط، وهو} K⁵ . وبالمثل، تنص تخمينية كيلمانز-سيمور على أن الرسم البياني خماسي الاتصال يكون مستويًا إذا وفقط إذا لم يكن لديه K⁵ كمُصغِّر _{طوبولوجي} .

نشر فاغنر كلا النظريتين عام 1937، ^{[ 1 ]} بعد نشر نظرية كوراتوفسكي عام 1930 ، ^{[ 2 ]} والتي تنص على أن الرسم البياني يكون مستويًا إذا وفقط إذا لم يحتوِ كرسم بياني فرعي على تقسيم فرعي لأحد الرسمين البيانيين الممنوعين K5 و _K3,3 . بمعنى ما، تُعد نظرية كوراتوفسكي أقوى من نظرية فاغنر: إذ يمكن تحويل التقسيم الفرعي إلى رسم بياني فرعي من النوع نفسه عن طريق تقليص جميع الحواف باستثناء حافة واحدة في كل مسار _ناتج عن عملية التقسيم الفرعي، ولكن تحويل الرسم البياني الفرعي إلى تقسيم فرعي من النوع نفسه ليس ممكنًا دائمًا. مع ذلك، في حالة الرسمين البيانيين K5 و _{K3,3 ، من السهل إثبات أن الرسم البياني الذي يحتوي على واحد على الأقل من هذين الرسمين البيانيين كرسم بياني فرعي يحتوي أيضًا على واحد على الأقل منهما كتقسيم فرعي، وبالتالي} فإن النظريتين متكافئتان. ^{[ 3 ]}

إحدى نتائج النسخة الأقوى من نظرية فاغنر للرسوم البيانية رباعية الاتصال هي تحديد الرسوم البيانية التي لا تحتوي على مُقَصِّر K⁵ . يمكن إعادة صياغة النظرية على النحو _التالي : كل رسم بياني من هذا النوع إما أن يكون مستويًا أو يمكن تقسيمه إلى أجزاء أبسط. باستخدام هذه الفكرة، يمكن وصف الرسوم البيانية الخالية من مُقَصِّر K⁵ _{بأنها الرسوم البيانية التي يمكن تكوينها من خلال دمج الرسوم البيانية المستوية مع} رسم فاغنر ذي الرؤوس الثمانية ، وذلك عن طريق عمليات جمع الزمر . على سبيل المثال، يمكن تكوين K₃ , _₃ بهذه الطريقة كمجموع زمر لثلاثة رسوم بيانية مستوية، كل منها نسخة من الرسم البياني رباعي الأوجه K₄ _.

تُعدّ نظرية فاغنر مقدمةً مهمةً لنظرية القواسم الجزئية للرسوم البيانية، والتي تُوِّجت بإثبات نتيجتين عميقتين وواسعتي الأثر: نظرية بنية الرسم البياني (تعميم لتحليل فاغنر لمجموع الزمر للرسوم البيانية الخالية من القواسم الجزئية من _النوع K⁵ ) ^{[ 4 ]} ، ونظرية روبرتسون-سيمور (تعميم لتوصيف القواسم الجزئية المحظورة للرسوم البيانية المستوية، والتي تنص على أن كل عائلة رسوم بيانية مغلقة تحت عملية أخذ القواسم الجزئية لها توصيف بعدد محدود من القواسم الجزئية المحظورة). ^{[ 5 ]} ويمكن أيضًا توسيع نظائر نظرية فاغنر لتشمل نظرية الماترويدات : على وجه الخصوص، يظهر الرسمان البيانيان K⁵ و K⁳, _{³ (} إلى جانب ثلاثة تكوينات محظورة أخرى) في توصيف الماترويدات الرسومية بواسطة القواسم الجزئية المحظورة للماترويدات . ^{[ 6 ]}