نظرية الرسم البياني المثالي القوي

في نظرية المخططات ، تُعرّف نظرية المخطط المثالي القوي المخططات المثالية بأنها تلك المخططات التي لا تحتوي على ثقوب فردية (دورات مستحثة بطول فردي لا يقل عن 5) ولا على ثقوب مضادة فردية (مكملات للثقوب الفردية). وقد افترضها كلود بيرج عام 1961. أُعلن عن برهانها عام 2002 من قِبل ماريا تشودنوفسكي ، ونيل روبرتسون ، وبول سيمور ، وروبن توماس ^{[ 1 ]} ، ونُشر عام 2006.

وقد فاز مؤلفو برهان نظرية الرسم البياني المثالي القوي بجائزة قدرها 10000 دولار مقدمة من جيرار كورنويجول من جامعة كارنيجي ميلون ^{[ 2 ]} وجائزة فولكرسون لعام 2009. ^{[ 3 ]}

الرسم البياني المثالي هو رسم بياني يكون فيه حجم أكبر زمرة ، لكل رسم بياني فرعي مُستحث ، مساويًا لأصغر عدد من الألوان في تلوين الرسم البياني. تشمل الرسوم البيانية المثالية العديد من فئات الرسوم البيانية المعروفة، بما في ذلك الرسوم البيانية ثنائية الأجزاء ، والرسوم البيانية الوترية ، ورسوم المقارنة . في أعماله التي عرّف فيها هذه الفئة من الرسوم البيانية لأول مرة عامي 1961 و1963، لاحظ كلود بيرج أنه من المستحيل أن يحتوي الرسم البياني المثالي على ثقب فردي، وهو رسم بياني فرعي مُستحث على شكل رسم بياني دوري فردي الطول بطول خمسة أو أكثر، لأن الثقوب الفردية لها عدد زمر اثنين وعدد ألوان ثلاثة. وبالمثل، لاحظ أن الرسوم البيانية المثالية لا يمكن أن تحتوي على ثقوب مضادة فردية، وهي رسوم بيانية فرعية مُستحثة مكملة للثقوب الفردية: الثقب المضاد الفردي الذي يحتوي على 2k + 1 رأسًا له عدد زمر k وعدد ألوان k + 1، وهو أمر مستحيل أيضًا بالنسبة للرسوم البيانية المثالية. أصبحت الرسوم البيانية التي لا تحتوي على ثقوب فردية ولا على ثقوب مضادة فردية تُعرف باسم رسوم بيرج البيانية.    

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

من بين تخمينات بيرج الأخرى، التي أثبتها لازلو لوفاس عام ١٩٧٢ ، أن مكمل كل رسم بياني كامل هو رسم بياني كامل أيضًا. عُرفت هذه الفرضية بنظرية الرسم البياني الكامل ، أو (لتمييزها عن تخمين/نظرية الرسم البياني الكامل القوي) بنظرية الرسم البياني الكامل الضعيف. ولأن توصيف بيرج للرسوم البيانية المحظورة مكمل ذاتيًا، فإن نظرية الرسم البياني الكامل الضعيف تتبع مباشرةً من نظرية الرسم البياني الكامل القوي.

يتبع برهان نظرية الرسم البياني المثالي القوي، الذي قدمه تشودنوفسكي وآخرون، مخططًا افترضه كونفورتي وكورنيول وروبرتسون وسيمور وتوماس عام ٢٠٠١، والذي ينص على أن كل رسم بياني من نوع بيرج إما أن يشكل أحد أنواع الوحدات البنائية الأساسية الخمسة (فئات خاصة من الرسوم البيانية المثالية) أو أنه يمتلك أحد أنواع التفكيك الهيكلي الأربعة المختلفة إلى رسوم بيانية أبسط. لا يمكن أن يمتلك الرسم البياني من نوع بيرج غير المثالي الأدنى أيًا من هذه التفكيكات، ومن ثم لا يمكن أن يوجد مثال مضاد للنظرية. ^{[ ٤ ]} استندت هذه الفكرة إلى تفكيكات هيكلية مفترضة سابقة من نوع مماثل كان من شأنها أن تؤدي إلى فرضية الرسم البياني المثالي القوي، ولكن تبين أنها خاطئة. ^{[ ٥ ]}

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

الأنواع الأربعة من عمليات التفكيك التي تم النظر فيها في هذا البرهان هي عمليات الربط الثنائية، ومكملات عمليات الربط الثنائية، والتقسيمات المائلة المتوازنة، والأزواج المتجانسة.

الوصل الثنائي هو تقسيم رؤوس الرسم البياني إلى مجموعتين فرعيتين، بحيث تشكل الحواف التي تمتد عبر القطع بين هاتين المجموعتين الفرعيتين رسمين بيانيين ثنائيين كاملين منفصلين رأسيًا . عندما يحتوي الرسم البياني على وصل ثنائي، يمكن تقسيمه إلى رسوم بيانية فرعية مستحثة تسمى "كتل"، وذلك باستبدال إحدى المجموعتين الفرعيتين من الرؤوس بأقصر مسار داخل تلك المجموعة الفرعية يربط أحد الرسمين البيانيين الثنائيين الكاملين بالآخر؛ وعندما لا يوجد مثل هذا المسار، تتشكل الكتلة بدلاً من ذلك باستبدال إحدى المجموعتين الفرعيتين من الرؤوس برأسين، رأس واحد لكل رسم بياني ثنائي كامل فرعي. يكون الوصل الثنائي مثاليًا إذا وفقط إذا كانت كتلتاه مثاليتين. لذلك، إذا كان الرسم البياني غير الكامل الأدنى يحتوي على وصل ثنائي، فيجب أن يساوي إحدى كتلتيه، ومن ثم فإنه يجب أن يكون دورة فردية وليس بيرج. وللسبب نفسه، لا يمكن أن يكون الرسم البياني غير الكامل الأدنى الذي يحتوي مكمله على وصلة ثنائية رسمًا بيانيًا من نوع بيرج. ^{[ 7 ]}

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

يرتبط الزوج المتجانس بتقسيم معياري للرسم البياني. وهو عبارة عن تقسيم للرسم البياني إلى ثلاث مجموعات فرعية V1 _و V2 و _V3 ، بحيث تحتوي V1 و V2 معًا على ثلاثة رؤوس على الأقل، وتحتوي _{V3 على} رأسين على الأقل، ولكل رأس v _في V3 ولكل i في _{المجموعة} {1,2}، إما أن يكون v مجاورًا لجميع الرؤوس في V1 أو غير مجاور لأي منها. من غير الممكن أن يحتوي الرسم البياني ذو العيوب الدنيا على زوج متجانس. _[ 9 ^{] بعد إثبات} حدسية الرسم البياني الكامل القوي، _قام تشودنوفسكي (2006) بتبسيطها من خلال إظهار إمكانية حذف الأزواج المتجانسة من مجموعة التقسيمات المستخدمة في الإثبات.

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

• بيرج ، كلود (1961)، “Färbung von Graphen، deren sämtliche bzw. deren ungerade Kreise starr sind”، ويس. Z. مارتن لوثر جامعة. هالي-فيتنبرغ الرياضيات-الطبيعة. الريهي ، 10 : 114.
• بيرج، كلود ( 1963)، "الرسوم البيانية المثالية"، ستة أوراق بحثية في نظرية الرسوم البيانية ، كلكتا: المعهد الإحصائي الهندي، ص 1-21 .
• تشودنوفسكي، ماريا (2006)، "مخططات بيرج الثلاثية"، مجلة نظرية المخططات ، 53 (1): 1-55 ، doi : 10.1002/jgt.20165 ، MR 2245543 .
• تشودنوفسكي، ماريا ؛ روبرتسون، نيل ؛ سيمور، بول ؛ توماس، روبن (2006)، "نظرية الرسم البياني الكامل القوي" ، حوليات الرياضيات ، 164 (1): 51-229 ، arXiv : math/0212070 ، doi : 10.4007/annals.2006.164.51 ، MR 2233847 .
• تشودنوفسكي، ماريا ؛ روبرتسون، نيل ؛ سيمور، بول ؛ توماس، روبن (2003)، "التقدم في الرسوم البيانية المثالية"، البرمجة الرياضية ، السلسلة ب، 97 ( 1-2 ): 405-422 ، CiteSeerX 10.1.1.137.3013 ، doi : 10.1007/s10107-003-0449-8 ، MR 2004404  .
• تشفاتال، فاكلاف (1985)، "مجموعات القطع النجمية والرسوم البيانية المثالية"، مجلة نظرية التوافيق ، السلسلة ب، 39 (3): 189-199 ، doi : 10.1016/0095-8956(85)90049-8 ، MR 0815391 .
• تشفاتال، فاكلاف ؛ سبيحي، نجيبة (1987)، "مخططات بيرج الخالية من الثور مثالية"، المخططات والتوافقية ، 3 (2): 127-139 ، doi : 10.1007/BF01788536 ، MR 0932129 .
• كورنويجول، جيرار (2002)، "تخمين الرسم البياني المثالي القوي"، وقائع المؤتمر الدولي للرياضيات، المجلد الثالث (بكين، 2002) (ملف PDF) ، بكين: دار النشر للتعليم العالي، الصفحات 547-559 ، MR 1957560  .
• كورنويجولز، جي .؛ كانينغهام، دبليو إتش (1985)، "تركيبات للرسوم البيانية المثالية"، الرياضيات المتقطعة ، 55 (3): 245-254 ، doi : 10.1016/S0012-365X(85)80001-7 ، MR 0802663 .
• هوغاردي، س. (1991)، أمثلة مضادة لثلاثة تخمينات تتعلق بالرسوم البيانية الكاملة ، تقرير فني RR870-M، غرونوبل، فرنسا: مختبر أرتيميس-IMAG، جامعة جوزيف فورييه. كما استشهد به روسيل وروسو وثويلير (2009) .
• Kőnig، Dénes (1916)، “Gráfok és alkalmazásuk a deferminánsok és a halmazok elméletére”، Matematikai és Természettudományi Értesítő ، 34 : 104– 119.
• لوفاس، لازلو (1972أ)، "الرسوم البيانية الفائقة العادية وتخمين الرسم البياني المثالي"، الرياضيات المتقطعة ، 2 (3): 253-267 ، doi : 10.1016/0012-365X(72)90006-4.
• لوفاس، لازلو (1972ب)، "توصيف للرسوم البيانية المثالية"، مجلة نظرية التوافيق ، السلسلة ب، 13 (2): 95-98 ، doi : 10.1016/0095-8956(72)90045-7.
• ماكنزي، دانا (5 يوليو 2002)، "الرياضيات: نظرية الرسم البياني تكشف جذور الكمال"، مجلة ساينس ، 297 (5578): 38، doi : 10.1126/science.297.5578.38 ، PMID 12098683 .
• ريد، بكالوريوس (1986)، نظرية الرسم البياني المثالي شبه القوي ، أطروحة دكتوراه، مونتريال، كيبيك، كندا: قسم علوم الحاسوب، جامعة ماكجيل. كما استشهد به روسيل وروسو وثويلير (2009) .
• روسيل، ف.؛ روسو، إ.؛ ثويلييه، هـ. (2009)، "تخمين الرسم البياني المثالي القوي: 40 عامًا من المحاولات، وحلها"، الرياضيات المتقطعة ، 309 (20): 6092-6113 ، doi : 10.1016/j.disc.2009.05.024 ، MR 2552645 .
• روسو، إيرينا (1997)، "بناء أمثلة مضادة"، الرياضيات المتقطعة ، 171 ( 1-3 ): 213-227 ، doi : 10.1016/S0012-365X(96)00081-7 ، MR 1454452 .
• سيمور، بول (2006)، "كيف تم التوصل إلى برهان تخمين الرسم البياني المثالي القوي" (ملف PDF) ، مجلة الرياضيات (109): 69-83 ، MR 2245898 .

• نظرية الرسم البياني الكامل القوي ، فاتسلاف شفاتال
• وايسشتاين، إريك دبليو. "نظرية الرسم البياني المثالي القوي" . عالم الرياضيات .