نظرية الرسم البياني القصوى
تتساءل نظرية الرسم البياني القصوى عن مدى كبر أو كثافة الرسم البياني مع تجنب بنية فرعية محددة مسبقًا، وتحدد التكوينات القصوى.
Definition
دراسة القيمة القصوى أو الدنيا لمعامل الرسم البياني، مثل عدد الحواف، مع مراعاة قيد هيكلي مثل غياب رسم بياني فرعي ثابت.
Scope
يركز هذا الموضوع على مسائل من نوع توران - العدد الأقصى للحواف في رسم بياني لا يحتوي على رسم بياني فرعي معين - بدءًا من نظريتي مانتل وتوران وامتدادًا إلى نظرية إيردوس-ستون، التي تحدد الكثافة القصوى التقاربية لأي رسم بياني فرعي محظور. ويقدم التفاعل بين الكثافة والبنية وطريقة انتظام سزيميريدي.
Core questions
- ما هو العدد الأقصى للحواف في رسم بياني على n رأس لا يحتوي على نسخة من رسم بياني فرعي معين؟
- ما هي الرسوم البيانية التي تحقق هذه الحدود القصوى؟
- كيف يتحكم العدد اللوني للرسم البياني الفرعي المحظور في الإجابة التقاربية؟
- كيف تقلل طرق الانتظام الرسوم البيانية الكثيفة إلى بنية محدودة؟
Key concepts
- الرسوم البيانية الفرعية المحظورة
- رسم توران البياني
- نظرية مانتل
- العدد الأقصى (عدد توران)
- نظرية إيردوس-ستون
- مبرهنة انتظام سزيميريدي
Key theories
- نظرية توران
- من بين جميع الرسوم البيانية على n رأس التي لا تحتوي على رسم بياني كامل على r+1 رأس، فإن الرسم البياني الكامل المتوازن r-جزئي يمتلك أكبر عدد من الحواف، مما يعمم حد مانتل الخالي من المثلثات ويرسخ نظرية الرسم البياني القصوى.
- نظرية إيردوس-ستون
- لأي رسم بياني فرعي محظور H ثابت، يتم تحديد الكثافة القصوى للحواف في رسم بياني خالٍ من H بشكل تقاربي بواسطة العدد اللوني لـ H، مما يوحد النتائج القصوى من نوع توران.
Clinical relevance
تحدد نتائج الكثافة القصوى بنية الشبكات الكبيرة وأنظمة القيود، ولطريقة الانتظام التي طُورت في هذا المجال تطبيقات في اختبار الخصائص، وعلوم الحاسوب النظرية، والتوافقيات الإضافية.
History
أطلقت حدود مانتل لعام 1907 الخالية من المثلثات وتعميم توران لعام 1941 هذا المجال؛ وجعلت نظرية إيردوس-ستون-سيمونوفيتس ومبرهنة انتظام سزيميريدي منه ركيزة أساسية في التوافقيات الحديثة.
Key figures
- Paul Turan
- Paul Erdos
- Endre Szemeredi
Related topics
Seminal works
- bollobas1998
- diestel2017
Frequently asked questions
- ما هي مشكلة من نوع توران؟
- تتساءل عن أكبر عدد من الحواف التي يمكن أن يحتويها الرسم البياني مع تجنب رسم بياني فرعي ثابت؛ والمثال النموذجي هو الحد الأقصى للحواف في رسم بياني خالٍ من المثلثات.
- كيف ترتبط نظرية الرسم البياني القصوى بنظرية رامزي؟
- كلاهما يدرس البنية التي لا يمكن تجنبها، لكن النظرية القصوى تثبت رسمًا بيانيًا فرعيًا محظورًا وتزيد الحواف إلى أقصى حد، بينما تضمن نظرية رامزي بنية أحادية اللون بمجرد أن يصبح الرسم البياني كبيرًا بما يكفي.