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

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

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

يكون لمتمم الرسم البياني حافة بين رأسين إذا وفقط إذا لم يكن للرسم البياني الأصلي حافة بين هذين الرأسين. وبالتالي، تصبح الزمرة في الرسم البياني الأصلي مجموعة مستقلة في المتمم، ويصبح تلوين الرسم البياني الأصلي غطاءً للزمر في المتمم.

تنص نظرية الرسم البياني المثالي على ما يلي:

مكمل الرسم البياني المثالي هو رسم بياني مثالي.

وبالمثل، في الرسم البياني المثالي، يساوي حجم المجموعة المستقلة القصوى الحد الأدنى لعدد الزمر في غطاء الزمر.

يترك${\displaystyle G}$ليكن الرسم البياني الدوري ذو طول فردي أكبر من ثلاثة (ما يسمى "ثقب فردي"). عندئذٍ${\displaystyle G}$يتطلب أي تلوين ثلاثة ألوان على الأقل، لكنه لا يحتوي على مثلث، لذا فهو ليس مثاليًا. وبحسب نظرية الرسم البياني المثالي، فإن متمم${\displaystyle G}$وبالتالي، فإن (الثقب المضاد الغريب) لا بد أن يكون غير مثالي أيضاً. إذا${\displaystyle G}$إذا كانت دورة من خمسة رؤوس، فهي متماثلة مع متممتها ، لكن هذه الخاصية لا تنطبق على الدورات الفردية الأطول، كما أن حساب عدد الزمر وعدد الألوان في ثقب مضاد فردي ليس بالأمر البسيط كما هو الحال في ثقب فردي. وكما تنص نظرية الرسم البياني المثالي القوي ، فإن الثقوب الفردية والثقوب المضادة الفردية تُعدّ أصغر الرسوم البيانية الفرعية المستحثة المحظورة للرسوم البيانية المثالية.

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

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

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

بافتراض وجود رسم بياني مثالي${\displaystyle G}$، يشكل لوفاس رسمًا بيانيًا${\displaystyle G^{*}}$عن طريق استبدال كل رأس${\displaystyle v}$بواسطة زمرة من${\displaystyle t_{v}}$الرؤوس، حيث${\displaystyle t_{v}}$يمثل عدد المجموعات المستقلة القصوى المتميزة في${\displaystyle G}$التي تحتوي${\displaystyle v}$من الممكن مطابقة كل مجموعة من المجموعات المستقلة القصوى المتميزة في${\displaystyle G}$مع إحدى المجموعات المستقلة القصوى في${\displaystyle G^{*}}$، بحيث تكون المجموعات المستقلة القصوى المختارة في${\displaystyle G^{*}}$جميعها منفصلة وكل رأس من رؤوس${\displaystyle G^{*}}$يظهر في مجموعة واحدة مختارة؛ أي${\displaystyle G^{*}}$يحتوي على تلوين تكون فيه كل فئة لونية عبارة عن مجموعة مستقلة قصوى. بالضرورة، هذا التلوين هو تلوين أمثل لـ${\displaystyle G^{*}}$. لأن${\displaystyle G}$مثالي، وكذلك${\displaystyle G^{*}}$وبالتالي، فإن لها زمرة قصوى${\displaystyle K^{*}}$حجمها يساوي عدد الألوان في هذا التلوين، وهو عدد المجموعات المستقلة القصوى المتميزة في${\displaystyle G}$بالضرورة،${\displaystyle K^{*}}$تحتوي على ممثل مميز لكل مجموعة من هذه المجموعات المستقلة القصوى. المجموعة المقابلة${\displaystyle K}$عدد الرؤوس في${\displaystyle G}$(الرؤوس التي تكون زمرها الموسعة في${\displaystyle G^{*}}$تتقاطع${\displaystyle K^{*}}$) هي زمرة في${\displaystyle G}$مع خاصية أنها تتقاطع مع كل مجموعة مستقلة قصوى في${\displaystyle G}$لذلك، فإن الرسم البياني المتكون من${\displaystyle G}$عن طريق الإزالة${\displaystyle K}$يحتوي على رقم غطاء المجموعة أقل بواحد على الأكثر من رقم مجموعة${\displaystyle G}$ويكون عدد الاستقلال أقل بواحد على الأقل من عدد الاستقلال لـ${\displaystyle G}$والنتيجة تتبع بالاستقراء على هذا العدد. ^{[ 6 ]}

تنص نظرية الرسم البياني الكامل القوي لتشودنوفسكي وآخرون (2006) على أن الرسم البياني يكون كاملاً إذا وفقط إذا لم يكن أي من الرسوم البيانية الفرعية المستحثة فيه عبارة عن دورات ذات طول فردي أكبر من أو يساوي خمسة، أو مكملاتها. ولأن هذا التوصيف لا يتأثر بتكملة الرسم البياني، فإنه يستلزم مباشرةً نظرية الرسم البياني الكامل الضعيف.

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

• Berge، Claude (1961)، “Färbung von Graphen، deren sämtliche beziehungsweise deren ungerade Kreise starr sind”، Wissenschaftliche Zeitschrift der Martin-Luther-Universität Halle-Wittenberg، Mathematisch-naturwissenschaftliche Reihe (بالألمانية)، 10 : 114.
• بيرج، كلود ( 1963)، "الرسوم البيانية المثالية"، ستة أوراق بحثية في نظرية الرسوم البيانية ، كلكتا: المعهد الإحصائي الهندي، ص 1-21 .
• كاميرون، ك. إدموندز، J .؛ Lovász، L. (1986)، “ملاحظة حول الرسوم البيانية المثالية”، الدورية Mathematica Hungarica ، 17 (3): 173–175 ، دوى : 10.1007 / BF01848646 ، MR 0859346 ، S2CID 121018903  .
• تشودنوفسكي، ماريا ؛ روبرتسون، نيل ؛ سيمور، بول ؛ توماس، روبن (2006)، "نظرية الرسم البياني المثالي القوي"، حوليات الرياضيات ، 164 (1): 51-229 ، arXiv : math/0212070 ، doi : 10.4007/annals.2006.164.51 ، MR 2233847 ، S2CID 119151552  .
• تشودنوفسكي، ماريا ؛ روبرتسون، نيل ؛ سيمور، بول ؛ توماس، روبن (2003)، "التقدم في الرسوم البيانية المثالية" (ملف PDF) ، البرمجة الرياضية ، السلسلة ب، 97 ( 1-2 ): 405-422 ، doi : 10.1007/s10107-003-0449-8 ، MR 2004404 .
• Gallai، Tibor (1958)، “Maximum-minimum Sätze über Graphen”، Acta Mathematica Academiae Scientiarum Hungaricae (بالألمانية)، 9 ( 3– 4): 395– 434، دوى : 10.1007 / BF02020271 ، MR 0124238 
• غولومبيك، مارتن تشارلز (1980)، "3.2. نظرية الرسم البياني المثالي"، نظرية الرسم البياني الخوارزمية والرسوم البيانية المثالية ، نيويورك: أكاديميك برس، ص 53-58 ، ISBN  0-12-289260-7، MR 0562306 .
• كونيغ، دينيس (1931)، “Gráfok és mátrixok”، Matematikai és Fizikai Lapok (باللغة الهنغارية)، 38 : 116– 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.
• ريد، بروس أ. (2001)، "من التخمين إلى النظرية"، في راميريز ألفونسين، خورخي ل.؛ ريد، بروس أ. (محرران)، الرسوم البيانية المثالية ، سلسلة وايلي-إنترساينس في الرياضيات المتقطعة والتحسين، تشيتشستر: وايلي، ص 13-24 ، MR 1861356  .