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

📅 آخر تحديث: ٢١ يوليو ٢٠٢٦
✍️ نُشر في: ٢١ يوليو ٢٠٢٦
📷 يحتوي على 41 صور
الموسوعة الحرة

الرسم البياني للمنشور المزدوج 3-3 ( الرسم البياني الخطي لـك3،3{\displaystyle K_{3,3}}) مثالي. هنا تم تلوينه بثلاثة ألوان، مع تسليط الضوء على إحدى مجموعات الرؤوس القصوى الثلاث.

في نظرية المخططات ، يُعرَّف المخطط المثالي بأنه المخطط الذي يتساوى فيه العدد اللوني مع حجم الزمرة القصوى ، سواء في المخطط نفسه أو في كل مخطط فرعي مُستحث . في جميع المخططات، يكون العدد اللوني أكبر من أو يساوي حجم الزمرة القصوى، ولكن قد يكون الفرق بينهما كبيرًا. يكون المخطط مثاليًا عندما يتساوى هذان العددان، ويظلان متساويين حتى بعد حذف أي مجموعة فرعية من الرؤوس.

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

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

التعريفات والخصائص

دورة ذات سبعة رؤوس ومتممتها، تُظهر في كل حالة تلوينًا مثاليًا وأكبر زمرة (موضحة بحواف سميكة). لا يستخدم أي من الرسمين البيانيين عددًا من الألوان يساوي حجم زمرته، لذا لا يُعد أي منهما مثاليًا.

الزمرة في الرسم البياني غير الموجه هي مجموعة جزئية من رؤوسه المتجاورة، مثل مجموعات الرؤوس المتصلة بحواف سميكة في الرسم التوضيحي. عدد الزمرة هو عدد الرؤوس في أكبر زمرة: رأسان في دورة الرؤوس السبعة الموضحة، وثلاثة في الرسم البياني الآخر. يُخصص تلوين الرسم البياني لونًا لكل رأس بحيث يكون لكل رأسين متجاورين لونان مختلفان، كما هو موضح في الرسم التوضيحي. العدد اللوني للرسم البياني هو الحد الأدنى لعدد الألوان في أي تلوين. التلوينات الموضحة هي الأمثل، لذا فإن العدد اللوني هو ثلاثة لدورة الرؤوس السبعة وأربعة للرسم البياني الآخر. يجب أن تكون رؤوس أي زمرة بألوان مختلفة، لذا فإن العدد اللوني دائمًا أكبر من أو يساوي عدد الزمرة. بالنسبة لبعض الرسوم البيانية، يكون العدد اللوني مساويًا لعدد الزمرة؛ وبالنسبة لرسوم بيانية أخرى، مثل تلك الموضحة، يكون العدد اللوني غير مساوي. تُعرَّف الرسوم البيانية المثالية بأنها الرسوم البيانية التي تتساوى فيها هاتان العددتان، ليس فقط في الرسم البياني نفسه، ولكن في كل رسم بياني فرعي مستحث يتم الحصول عليه عن طريق حذف بعض رؤوسه. [ 1 ]

رسمان بيانيان متكاملان مثاليان

تنص نظرية الرسم البياني المثالي على أن الرسم البياني المكمل للرسم البياني المثالي يكون مثاليًا في حد ذاته. يحتوي الرسم البياني المكمل على حافة بين رأسين إذا وفقط إذا لم يكن الرسم البياني المعطى يحتوي على حافة. ​​تُقابل الزمرة، في الرسم البياني المكمل، مجموعة مستقلة في الرسم البياني المعطى. يُقابل تلوين الرسم البياني المكمل غطاء الزمر ، وهو تقسيم رؤوس الرسم البياني المعطى إلى زمر. حقيقة أن الرسم البياني المكمل للرسم البياني المثاليجي{\displaystyle G}كما أن كلمة "مثالي" تعني أنه فيجي{\displaystyle G}في حد ذاتها، يساوي عدد الاستقلال (حجم أكبر مجموعة مستقلة ) عدد تغطية الزمر (أقل عدد من الزمر اللازمة لتغطية الزمر). وبشكل أدق، ينطبق الأمر نفسه على كل رسم بياني فرعي مستحث من الرسم البياني المكمل. وهذا يوفر تعريفًا بديلًا ومكافئًا للرسوم البيانية المثالية: فهي الرسوم البيانية التي يكون فيها عدد الاستقلال في كل رسم بياني فرعي مستحث مساويًا لعدد تغطية الزمر. [ 2 ] [ 3 ]

تُقدّم نظرية الرسم البياني المثالي القوي طريقةً مختلفةً لتعريف الرسوم البيانية المثالية، وذلك من خلال بنيتها بدلاً من خصائصها. وتستند هذه النظرية إلى وجود الرسوم البيانية الدورية ومكملاتها ضمن رسم بياني مُعطى. فالدورة ذات الطول الفردي، الأكبر من ثلاثة، ليست مثالية: إذ يبلغ عدد زمرها اثنين، بينما يبلغ عدد ألوانها ثلاثة. وبحسب نظرية الرسم البياني المثالي، فإن مكمل الدورة الفردية ذات الطول الأكبر من ثلاثة ليس مثالياً أيضاً. مكمل الدورة ذات الطول 5 هو دورة أخرى ذات طول 5، ولكن بالنسبة للأطوال الفردية الأكبر، فإن المكمل ليس دورة؛ بل يُسمى دورة مضادة . وتؤكد نظرية الرسم البياني المثالي القوي أن هذه هي الرسوم البيانية الفرعية المستحثة الوحيدة الممنوعة للرسوم البيانية المثالية: يكون الرسم البياني مثالياً إذا وفقط إذا لم تتضمن رسومه البيانية الفرعية المستحثة دورة فردية ولا دورة مضادة فردية ذات خمسة رؤوس أو أكثر. في هذا السياق، تُسمى الدورات المستحثة التي ليست مثلثات "ثقوبًا"، وتُسمى مكملاتها "ثقوبًا مضادة"، لذا يمكن صياغة نظرية الرسم البياني المثالي القوي بشكل أكثر إيجازًا: يكون الرسم البياني مثاليًا إذا وفقط إذا لم يكن به ثقب فردي ولا ثقب مضاد فردي. [ 4 ]

يمكن دمج هذه النتائج في توصيف آخر للرسوم البيانية المثالية: وهي الرسوم البيانية التي يكون فيها حاصل ضرب عدد الزمر وعدد الاستقلال أكبر من أو يساوي عدد الرؤوس، وينطبق الأمر نفسه على جميع الرسوم البيانية الفرعية المستحثة. ولأن هذا التوصيف يظل ثابتًا عند استكمال الرسوم البيانية، فإنه يستلزم نظرية الرسم البياني المثالي. أحد اتجاهات هذا التوصيف ينبثق بسهولة من التعريف الأصلي للمثالية: عدد الرؤوس في أي رسم بياني يساوي مجموع أحجام فئات الألوان في التلوين الأمثل، وهو أقل من أو يساوي عدد الألوان مضروبًا في عدد الاستقلال. في الرسم البياني المثالي، يساوي عدد الألوان عدد الزمر، ويمكن استبداله بعدد الزمر في هذه المتباينة. يمكن إثبات الاتجاه الآخر مباشرةً، [ 5 ] [ 6 ] ولكنه يتبع أيضًا من نظرية الرسم البياني الكامل القوي: إذا لم يكن الرسم البياني كاملاً، فإنه يحتوي على دورة فردية أو مكملتها، وفي هذه الرسوم البيانية الفرعية يكون حاصل ضرب عدد الزمر وعدد الاستقلال أقل بواحد من عدد الرؤوس. [ 7 ]

تاريخ

تطورت نظرية الرسوم البيانية الكاملة انطلاقًا من نتيجة توصل إليها تيبور غالاي عام 1958 ، والتي يمكن تفسيرها بلغة العصر الحديث على أنها تنص على أن مكمل الرسم البياني ثنائي الأجزاء هو رسم بياني كامل؛ [ 8 ] ويمكن أيضًا اعتبار هذه النتيجة مكافئًا بسيطًا لنظرية كونيغ ، وهي نتيجة أقدم بكثير تربط بين المطابقات وتغطية الرؤوس في الرسوم البيانية ثنائية الأجزاء. أما أول صياغة لمفهوم الرسوم البيانية الكاملة بشكل أعم، فكانت في ورقة بحثية نشرها كلود بيرج عام 1961 باللغة الألمانية، [ 9 ] ويبدو أن أول استخدام لعبارة "الرسم البياني الكامل" كان في ورقة بحثية أخرى لبيرج عام 1963. [ 10 ] في هذه الأعمال، وحّد بيرج نتيجة غالاي مع العديد من النتائج المماثلة من خلال تعريف الرسوم البيانية الكاملة، كما افترض كلًا من نظرية الرسم البياني الكامل ونظرية الرسم البياني الكامل القوي. عند صياغة هذه المفاهيم، استلهم بيرج من مفهوم سعة شانون للرسم البياني ، ومن حقيقة أنها تساوي عدد الاستقلال في الرسوم البيانية (المشتركة) الكاملة، ومن البحث عن أمثلة دنيا للرسوم البيانية التي لا ينطبق عليها هذا الشرط. [ 11 ] وحتى إثبات نظرية الرسم البياني الكامل القوي، كانت الرسوم البيانية التي تصفها هذه النظرية (أي الرسوم البيانية التي لا تحتوي على ثقب فردي ولا على ثقب مضاد فردي) تُسمى رسوم بيرج البيانية . [ 12 ]

أثبت لازلو لوفاس نظرية الرسم البياني المثالي عام 1972، [ 2 ] وفي العام نفسه أثبت المتباينة الأقوى بين عدد الرؤوس وحاصل ضرب عدد الزمر وعدد الاستقلال، دون الاستعانة بنظرية الرسم البياني المثالي القوية. [ 5 ] وفي عام 1991، فاز ألفريد ليمان بجائزة فولكرسون ، التي ترعاها جمعية التحسين الرياضي والجمعية الرياضية الأمريكية ، لعمله على تعميم نظرية الرسوم البيانية المثالية لتشمل المصفوفات المنطقية . [ 13 ] أصبحت نظرية الرسم البياني المثالي القوي المفترضة محورًا للبحث في نظرية الرسوم البيانية المثالية لسنوات عديدة، [ 12 ] إلى أن أُعلن عن برهانها في عام 2002 من قِبل ماريا تشودنوفسكي ، ونيل روبرتسون ، وبول سيمور ، وروبن توماس ، [ 14 ] ونُشر من قِبلهم في عام 2006. [ 4 ] وقد فاز مؤلفو هذا العمل بجائزة فولكرسون لعام 2009. [ 15 ] تتميز نظرية الرسم البياني المثالي ببرهان قصير، [ 5 ] [ 6 ] لكن برهان نظرية الرسم البياني المثالي القوي طويل ومعقد، ويعتمد على تحليل هيكلي عميق لرسوم بيرج البيانية. وقد أثمرت تقنيات التحليل ذات الصلة أيضًا في دراسة فئات أخرى من الرسوم البيانية، ولا سيما الرسوم البيانية الخالية من المخالب . [ 16 ] تم اقتراح التوصيف المتناظر للرسوم البيانية المثالية من حيث حاصل ضرب عدد الزمر وعدد الاستقلال في الأصل من قبل هاينال وتم إثباته من قبل لوفاس. [ 5 ]

عائلات الرسوم البيانية

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

الرسوم البيانية ثنائية الأجزاء والرسوم البيانية الخطية

رسم بياني ثنائي الأجزاء (يسار) ورسمه البياني الخطي (يمين). تمثل المجموعات المظللة في الرسم البياني الخطي رؤوس الرسم البياني ثنائي الأجزاء الأساسي، ويبلغ حجمها درجة الرأس المقابل.

في الرسوم البيانية ثنائية الأجزاء (ذات حافة واحدة على الأقل)، يساوي كل من العدد اللوني وعدد الزمر اثنين. وتبقى الرسوم البيانية الفرعية الناتجة عنها ثنائية الأجزاء، لذا فإن الرسوم البيانية ثنائية الأجزاء مثالية. [ 12 ] توجد عائلات أخرى مهمة من الرسوم البيانية ثنائية الأجزاء، وبالتالي فهي مثالية أيضًا، بما في ذلك على سبيل المثال الأشجار والرسوم البيانية الوسيطة . [ 17 ] وبحسب نظرية الرسم البياني المثالي، فإن أكبر مجموعة مستقلة في الرسوم البيانية ثنائية الأجزاء لها نفس حجم أصغر غطاء زمر لها. تُكمل أكبر مجموعة مستقلة غطاء الرؤوس الأدنى ، وهو مجموعة من الرؤوس التي تلامس جميع الحواف. يتكون غطاء الزمر الأدنى من أكبر تطابق (أكبر عدد ممكن من الحواف المنفصلة) بالإضافة إلى زمر ذات رأس واحد لجميع الرؤوس المتبقية، وحجمه هو عدد الرؤوس مطروحًا منه عدد الحواف المتطابقة. لذلك، يمكن التعبير عن هذه المساواة بشكل مكافئ على أنها مساواة بين حجم المطابقة القصوى والحد الأدنى لتغطية الرؤوس في الرسوم البيانية ثنائية الأجزاء، وهي الصيغة المعتادة لنظرية كونيغ . [ 18 ] [ 19 ]

التطابق، في أي رسم بيانيجي{\displaystyle G}، هو نفسه مجموعة مستقلة في الرسم البياني الخطيل(جي){\displaystyle L(G)}، وهو رسم بياني يحتوي على رأس لكل حافة فيجي{\displaystyle G}وحافة بين رأسين فيل(جي){\displaystyle L(G)}لكل زوج من الحواف فيجي{\displaystyle G}التي تشترك في نقطة نهاية واحدة. تحتوي الرسوم البيانية الخطية على نوعين من الزمر: مجموعات من الحواف فيجي{\displaystyle G}بنقطة نهاية مشتركة، ومثلثات فيجي{\displaystyle G}في الرسوم البيانية ثنائية الأجزاء، لا توجد مثلثات، لذا فإن غطاء الزمرة فيل(جي){\displaystyle L(G)}يتوافق مع غطاء الرؤوس فيجي{\displaystyle G}لذلك، في الرسوم البيانية الخطية للرسوم البيانية ثنائية الأجزاء، يتساوى عدد الاستقلال مع عدد تغطية الزمر. الرسوم البيانية الفرعية المستحثة للرسوم البيانية الخطية للرسوم البيانية ثنائية الأجزاء هي رسوم بيانية خطية لرسوم بيانية فرعية، وبالتالي فإن الرسوم البيانية الخطية للرسوم البيانية ثنائية الأجزاء كاملة. [ 19 ] تشمل الأمثلة رسوم الرخ البيانية ، والرسوم البيانية الخطية للرسوم البيانية ثنائية الأجزاء الكاملة . كل رسم بياني خطي لرسم بياني ثنائي الأجزاء هو رسم بياني فرعي مستحث لرسم الرخ البياني. [ 20 ]

نظرًا لأن الرسوم البيانية الخطية للرسوم البيانية ثنائية الأجزاء مثالية، فإن عدد زمرها يساوي عددها اللوني. عدد الزمر في الرسم البياني الخطي للرسم البياني ثنائي الأجزاء هو أعلى درجة لأي رأس في الرسم البياني ثنائي الأجزاء الأساسي. أما العدد اللوني في الرسم البياني الخطي للرسم البياني ثنائي الأجزاء فهو المؤشر اللوني للرسم البياني ثنائي الأجزاء الأساسي، وهو الحد الأدنى لعدد الألوان اللازمة لتلوين الحواف بحيث تكون الحواف المتلامسة بألوان مختلفة. تشكل كل فئة لونية تطابقًا، والمؤشر اللوني هو الحد الأدنى لعدد التطابقات اللازمة لتغطية جميع الحواف. تُعد مساواة أعلى درجة والمؤشر اللوني، في الرسوم البيانية ثنائية الأجزاء، نظرية أخرى لدينيس كونيغ . [ 21 ] في الرسوم البيانية البسيطة، يمكن أن يختلفا بمقدار واحد؛ وهذه هي نظرية فيزينغ . [ 19 ]

رسم بياني خطي مثالي ، بمكونات ثنائية الأجزاء سوداء اللون ومتصلة ثنائياً، وأزرق اللون.ك4{\displaystyle K_{4}}وكتب مثلثة حمراء

الرسم البياني الأساسيجي{\displaystyle G}رسم بياني خطي مثاليل(جي){\displaystyle L(G)}هو رسم بياني خطي مثالي . هذه هي الرسوم البيانية التي تكون مكوناتها ثنائية الاتصال عبارة عن رسوم بيانية ثنائية الأجزاء، أي الرسم البياني الكاملك4{\displaystyle K_{4}}والكتب المثلثية ، وهي مجموعات من المثلثات التي تشترك في ضلع. هذه المكونات مثالية، وتركيبها يحافظ على الكمال، لذا فإن كل رسم بياني مثالي هو رسم بياني مثالي. [ 19 ]

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

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

مخطط هاس لمجموعة مرتبة جزئياً، ومخطط قابلية المقارنة الخاص بها

تُعرَّف المجموعة المرتبة جزئيًا بمجموعة عناصرها وعلاقة مقارنة.≤{\displaystyle \leq }هذا انعكاسي (لجميع العناصر)x{\displaystyle x}،x≤x{\displaystyle x\leq x}), متناظر عكسيًا (إذاx≤y{\displaystyle x\leq y}وy≤x{\displaystyle y\leq x}، ثمx=y{\displaystyle x=y}، ومتعدية ( إذاx≤y{\displaystyle x\leq y}وy≤z{\displaystyle y\leq z}، ثمx≤z{\displaystyle x\leq z}). عناصرx{\displaystyle x}وy{\displaystyle y}تكون قابلة للمقارنة إذاx≤y{\displaystyle x\leq y}أوy≤x{\displaystyle y\leq x}وغير قابلة للمقارنة في غير ذلك. على سبيل المثال، تضمين المجموعة (⊆{\displaystyle \subseteq }يُرتب الترتيب الجزئي أي عائلة من المجموعات . يتكون مخطط المقارنة لمجموعة مرتبة جزئيًا من عناصر المجموعة كرؤوس، مع وجود حافة تربط أي عنصرين قابلين للمقارنة. يُسمى مكمله مخطط عدم المقارنة . قد يكون للترتيبات الجزئية المختلفة نفس مخطط المقارنة؛ على سبيل المثال، عكس جميع المقارنات يُغير الترتيب ولكن ليس المخطط. [ 22 ]

تكون رسوم المقارنة المحدودة (ورسوم عدم المقارنة المكملة لها) مثالية دائمًا. [ 23 ] تتكون الزمرة، في رسم المقارنة، من مجموعة جزئية من العناصر التي يمكن مقارنة كل عنصر منها على حدة؛ وتُسمى هذه المجموعة الجزئية سلسلة ، وهي مرتبة خطيًا وفقًا للترتيب الجزئي المُعطى. أما المجموعة المستقلة فتتكون من مجموعة جزئية من العناصر التي لا يمكن مقارنة أي عنصرين منها؛ وتُسمى هذه المجموعة الجزئية سلسلة مضادة . على سبيل المثال، في رسم الترتيب الجزئي ورسم المقارنة الموضح،{أ،ب،ج}{\displaystyle \{A,B,C\}}هي سلسلة في الترتيب وزمرة في الرسم البياني، بينما{ج،د}{\displaystyle \{C,D\}}هي سلسلة مضادة في الترتيب ومجموعة مستقلة في الرسم البياني. بالتالي، فإن تلوين رسم بياني للمقارنة هو تقسيم لعناصره إلى سلاسل مضادة، وغطاء الزمر هو تقسيم لعناصره إلى سلاسل. تنص نظرية ديلورث ، في نظرية الترتيبات الجزئية، على أنه لكل ترتيب جزئي منتهٍ، فإن حجم أكبر سلسلة مضادة يساوي الحد الأدنى لعدد السلاسل التي يمكن تقسيم العناصر إليها. بلغة الرسوم البيانية، يمكن التعبير عن ذلك على النحو التالي: كل رسم بياني للمقارنة منتهٍ هو رسم بياني مثالي. وبالمثل، تنص نظرية ميرسكي على أنه لكل ترتيب جزئي منتهٍ، فإن حجم أكبر سلسلة يساوي الحد الأدنى لعدد السلاسل المضادة التي يمكن تقسيم العناصر إليها، أو أن كل رسم بياني لعدم المقارنة منتهٍ هو رسم بياني مثالي. هاتان النظريتان متكافئتان عبر نظرية الرسم البياني الكامل، لكن إثبات نظرية ميرسكي أسهل من إثبات نظرية ديلورث مباشرةً: إذا تم تصنيف كل عنصر بحجم أكبر سلسلة يكون فيها أقصى ما يمكن، فإن المجموعات الجزئية ذات التصنيفات المتساوية تُشكل تقسيمًا إلى سلاسل مضادة، ويكون عدد السلاسل المضادة مساويًا لحجم أكبر سلسلة إجمالًا. [ 24 ] كل رسم بياني ثنائي الأجزاء هو رسم بياني قابل للمقارنة. بالتالي، يمكن اعتبار نظرية كونيغ حالة خاصة من نظرية ديلورث، مرتبطة بها من خلال نظرية الرسوم البيانية الكاملة. [ 25 ]

يربط الرسم البياني للتبديل (4،3،5،1،2) أزواج العناصر التي يتم عكس ترتيبها بواسطة التبديل.

يُعرَّف مخطط التبديلات من خلال تبديل على سلسلة مرتبة ترتيبًا كليًا من العناصر (عادةً، الأعداد الصحيحة من1{\displaystyle 1}لن{\displaystyle n}تشكل هذه العناصر رؤوس الرسم البياني. تربط حواف الرسم البياني للتبديل أزواجًا من العناصر التي ينعكس ترتيبها بالتبديل المعطى. هذه الرسوم البيانية هي بطبيعتها رسوم بيانية غير قابلة للمقارنة، وذلك لترتيب جزئي يكون فيهx≤y{\displaystyle x\leq y}حينماx{\displaystyle x}يحدث قبلy{\displaystyle y}في كلٍّ من التسلسل المُعطى وتبديله. مُكمِّل مخطط التبديل هو مخطط تبديل آخر، لعكس التبديل المُعطى. لذلك، بالإضافة إلى كونها مخططات عدم قابلية للمقارنة، فإن مخططات التبديل هي أيضًا مخططات قابلية للمقارنة. في الواقع، مخططات التبديل هي بالضبط المخططات التي تُعدّ في آنٍ واحد مخططات قابلية للمقارنة وعدم قابلية للمقارنة. [ 26 ] الزمرة، في مخطط التبديل، هي سلسلة فرعية من العناصر التي تظهر بترتيب تصاعدي في التبديل المُعطى، والمجموعة المستقلة هي سلسلة فرعية من العناصر التي تظهر بترتيب تنازلي. في أي مخطط مثالي، يكون حاصل ضرب عدد الزمر وعدد الاستقلال على الأقل عدد الرؤوس؛ الحالة الخاصة لهذه المتباينة لمخططات التبديل هي نظرية إردوش-سيكيريس . [ 24 ]

الرسم البياني للفترات والفترات التي تحدده

تُعدّ رسوم الفترات البيانية رسومًا بيانية لعدم قابلية المقارنة لترتيبات الفترات ، وهي ترتيبات مُعرّفة بمجموعات من الفترات على خط الأعداد الحقيقية.x≤y{\displaystyle x\leq y}كلما كانت الفترةx{\displaystyle x}يقع بالكامل إلى يسار الفاصل الزمنيy{\displaystyle y}في الرسم البياني للفترات المقابل، توجد حافة منx{\displaystyle x}لy{\displaystyle y}عندما تشترك فترتان في نقطة واحدة. يمكن استخدام تلوين هذه الرسوم البيانية لنمذجة مشاكل تخصيص الموارد للمهام (مثل تخصيص الفصول الدراسية للصفوف) مع فترات تصف الوقت المُجدول لكل مهمة. [ 27 ] تُعمم الرسوم البيانية شبه المنحرفة كلاً من الرسوم البيانية للفترات والرسوم البيانية للتباديل . [ 28 ] تُنتج أنظمة الفترات التي لا تتداخل فيها فترتان فئةً أكثر تقييدًا من الرسوم البيانية، وهي رسوم بيانية اللامبالاة ، ورسوم بيانية عدم قابلية المقارنة للأشكال شبه المرتبة . وقد استُخدمت هذه الرسوم البيانية لنمذجة التفضيلات البشرية بافتراض أنه عندما تكون منافع العناصر متقاربة جدًا، فإنها ستكون غير قابلة للمقارنة. [ 29 ] تُنتج الفترات التي يكون فيها كل زوج متداخلًا أو منفصلًا رسومًا بيانية مثالية بشكل بديهي ، [ 30 ] وهي رسوم بيانية قابلية المقارنة للأشجار المرتبة . في هذه الرسوم البيانية، يساوي عدد الاستقلال عدد الزمر القصوى . [ 31 ]

الرسوم البيانية المنقسمة والرسوم البيانية المثالية العشوائية

التلوين الأمثل للرسم البياني المنقسم ، والذي يتم الحصول عليه بإعطاء كل رأس من رؤوس الزمرة القصوى (الرؤوس والحواف الثقيلة) لونًا منفصلاً، ثم إعطاء كل رأس متبقٍ نفس لون رأس الزمرة الذي لا يجاوره

الرسم البياني المنقسم هو رسم بياني يمكن تقسيمه إلى زمرة ومجموعة مستقلة. يمكن تلوينه بتخصيص لون منفصل لكل رأس من رؤوس الزمرة القصوى، ثم تلوين كل رأس متبقٍ بنفس لون رأس زمرة غير مجاور. لذلك، تحتوي هذه الرسوم البيانية على أعداد زمر وأعداد ألوان متساوية، وهي مثالية. [ 32 ] يمكن تقسيم فئة أوسع من الرسوم البيانية، وهي الرسوم البيانية أحادية القطب، إلى زمرة ورسم بياني عنقودي ، وهو اتحاد منفصل من الزمر. تشمل هذه أيضًا الرسوم البيانية ثنائية الأجزاء، حيث يكون الرسم البياني العنقودي عبارة عن زمرة واحدة فقط. تشكل الرسوم البيانية أحادية القطب ومكملاتها معًا فئة الرسوم البيانية المنقسمة المعممة . جميع الرسوم البيانية المثالية تقريبًا هي رسوم بيانية منقسمة معممة، بمعنى أن نسبة الرسوم البيانية المثاليةن{\displaystyle n}تؤول الرسوم البيانية ذات الرؤوس المتعددة، والتي تُعتبر رسومًا بيانية منقسمة معممة، إلى واحد في النهاية عندمان{\displaystyle n}ينمو بشكل كبير بشكل تعسفي. [ 33 ]

يمكن تحديد خصائص أخرى محددة لجميع الرسوم البيانية المثالية تقريبًا من خلال دراسة الرسوم البيانية المنقسمة المعممة. وبهذه الطريقة، تم إثبات أن جميع الرسوم البيانية المثالية تقريبًا تحتوي على دورة هاميلتونية .ح{\displaystyle H}إذا كان الرسم البياني عشوائيًا، فإن الاحتمالية الحدية هيح{\displaystyle H}يحدث ذلك كرسم بياني فرعي مستحث من رسم بياني كامل عشوائي كبير، وتكون قيمته 0 أو 1/2 أو 1 على التوالي.ح{\displaystyle H}ليس رسمًا بيانيًا منقسمًا معمّمًا، أو أحادي القطب أو أحادي القطب المشترك ولكن ليس كلاهما، أو أحادي القطب وأحادي القطب المشترك معًا. [ 34 ]

الإنشاءات التدريجية

يمكن تمييز العديد من عائلات الرسوم البيانية المثالية من خلال بناء تدريجي يتم فيه بناء الرسوم البيانية في العائلة عن طريق إضافة رأس واحد في كل مرة، وفقًا لقواعد معينة، والتي تضمن أن يظل الرسم البياني مثاليًا بعد إضافة كل رأس.

  • الرسوم البيانية الوترية هي الرسوم البيانية التي تتشكل من خلال بناء من هذا النوع، حيث تُشكل رؤوسه المجاورة زمرةً عند إضافة رأس جديد. ويمكن وصف الرسوم البيانية الوترية أيضًا بأنها الرسوم البيانية التي لا تحتوي على ثقوب (زوجية أو فردية). [ 35 ] وتشمل كحالات خاصة الغابات، والرسوم البيانية الفاصلية، [ 36 ] والرسوم البيانية الخارجية المستوية القصوى . [ 37 ] أما الرسوم البيانية المنقسمة فهي تحديدًا الرسوم البيانية الوترية التي لها مكمل وتري. [ 38 ] وتُعد الأشجار من الرتبة k ، وهي أساسية في تعريف عرض الشجرة ، رسومًا بيانية وترية تتشكل من خلال البدء بزمرة من الرؤوس ( k + 1) وإضافة رأس جديد بشكل متكرر بحيث يُشكل هو وجيرانه زمرة من نفس الحجم. [ 35 ]
ثلاثة أنواع من إضافة الرؤوس في رسم بياني وراثي للمسافة
  • تُشكَّل الرسوم البيانية الوراثية للمسافة ، بدءًا من رسم بياني ذي رأس واحد، بإضافة رؤوس من الدرجة الأولى ("رؤوس معلقة") أو نسخ من رؤوس موجودة (لها نفس الجيران) بشكل متكرر. قد يكون كل رأس ونسخته متجاورين ( توائم حقيقية ) أو غير متجاورين ( توائم زائفة ). في كل رسم بياني فرعي متصل مُستحث من هذه الرسوم البيانية، تكون المسافات بين الرؤوس هي نفسها في الرسم البياني الكامل. إذا استُخدمت عمليات التوأمة فقط، تكون النتيجة رسمًا بيانيًا مُكمِّلًا . [ 39 ] الرسوم البيانية المُكمِّلة هي رسوم بيانية للمقارنة للترتيبات الجزئية المتسلسلة المتوازية [ 40 ] ، ويمكن أيضًا تشكيلها من خلال عملية بناء مختلفة تجمع بين التكامل والاتحاد المنفصل للرسوم البيانية . [ 41 ]
  • تُسمى الرسوم البيانية التي تجمع بين خاصية الوراثة الوترية والمسافة بالرسوم البيانية البطلمية ، لأن مسافاتها تخضع لمتباينة بطليموس . [ 42 ] ولها شكل مقيد من تسلسل البناء الوراثي للمسافة، حيث لا يمكن إضافة توأم زائف إلا إذا شكلت جيرانه زمرة. [ 39 ] وتشمل هذه الرسوم، كحالات خاصة، رسومًا بيانية على شكل طواحين هواء تتكون من زمر متصلة عند رأس واحد، ورسومًا بيانية كتلية يكون فيها كل مكون ثنائي الاتصال زمرة. [ 42 ]
  • تُشكَّل الرسوم البيانية الحدية من رسم بياني فارغ عن طريق إضافة رأس معزول (غير متصل بأي رأس آخر) أو رأس شامل (متصل بجميع الرؤوس الأخرى) بشكل متكرر . [ 43 ] وهي حالات خاصة من الرسوم البيانية المنقسمة والرسوم البيانية الكاملة التافهة. إنها تحديدًا الرسوم البيانية التي تكون كاملة تافهة ومكملة لرسم بياني كامل تافه؛ وهي أيضًا تحديدًا الرسوم البيانية التي تكون رسومًا بيانية مكملة ورسومًا بيانية منقسمة. [ 44 ]

إذا لُوِّنت رؤوس الرسم البياني الوترية بترتيب تسلسل بناء تزايدي باستخدام خوارزمية تلوين جشعة ، فستكون النتيجة تلوينًا أمثل. يُسمى عكس ترتيب الرؤوس المستخدم في هذا البناء بترتيب الحذف . [ 45 ] وبالمثل، إذا لُوِّنت رؤوس الرسم البياني الوراثي للمسافة بترتيب تسلسل بناء تزايدي، فسيكون التلوين الناتج أمثل. [ 46 ] وإذا لُوِّنت رؤوس الرسم البياني للمقارنة بترتيب امتداد خطي لترتيبه الجزئي الأساسي، فسيكون التلوين الناتج أمثل. تُعمَّم هذه الخاصية في عائلة الرسوم البيانية القابلة للترتيب تمامًا ، وهي الرسوم البيانية التي يوجد لها ترتيب، عند تقييده بأي رسم بياني فرعي مُستحث، يجعل التلوين الجشع أمثل. [ 47 ] الرسوم البيانية المُكمِّلة هي تحديدًا الرسوم البيانية التي تتمتع جميع ترتيبات رؤوسها بهذه الخاصية. [ 48 ] ​​فئة فرعية أخرى من الرسوم البيانية القابلة للترتيب تمامًا هي مكملات الرسوم البيانية للتسامح ، وهي تعميم للرسوم البيانية الفاصلية. [ 49 ]

إتقان قوي

الرسوم البيانية المثالية بقوة هي رسوم بيانية يوجد فيها، في كل رسم بياني فرعي مُستحث، مجموعة مستقلة تتقاطع مع جميع الزمر القصوى . في رسوم مينيل البيانية، أو الرسوم البيانية المثالية بقوة شديدة ، ينتمي كل رأس إلى هذه المجموعة المستقلة. يمكن أيضًا وصف رسوم مينيل البيانية بأنها الرسوم البيانية التي تحتوي فيها كل دورة فردية بطول خمسة أو أكثر على وترين على الأقل. [ 50 ]

رسم بياني للتكافؤ ليس وراثيًا بالمسافة ولا ثنائي الأجزاء

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

المصفوفات، والمجسمات متعددة الأوجه، والبرمجة العددية

ترتبط الرسوم البيانية المثالية ارتباطًا وثيقًا بنظرية البرمجة الخطية والبرمجة العددية . ويتم التعبير عن كل من البرامج الخطية والبرمجة العددية في شكلها المتعارف عليه من خلال البحث عن متجه .x{\displaystyle x}الذي يُعظّم دالة هدف خطيةج⋅x{\displaystyle c\cdot x}مع مراعاة القيود الخطيةx≥0{\displaystyle x\geq 0}وأx≤ب{\displaystyle Ax\leq b}. هنا،أ{\displaystyle A}يتم تقديمها على شكل مصفوفة ، وب{\displaystyle b}وج{\displaystyle c}يتم تحديدها كمتجهين. على الرغم من أن البرامج الخطية وبرامج الأعداد الصحيحة تُحدد بنفس الطريقة، إلا أنها تختلف في أن متجه الحل في البرنامج الخطيx{\displaystyle x}يُسمح للبرمجة الخطية بأن تكون معاملاتها أعدادًا حقيقية عشوائية، بينما في البرمجة العددية يجب أن تكون هذه المعاملات المجهولة أعدادًا صحيحة. وهذا يُحدث فرقًا كبيرًا في التعقيد الحسابي لهذه المسائل: يمكن حل البرمجة الخطية في وقت متعدد الحدود ، لكن البرمجة العددية تُصنف ضمن مسائل NP-hard . [ 1 ]

عندما تكون القيم المعطاة نفسهاأ{\displaystyle A}،ب{\displaystyle b}، وج{\displaystyle c}تُستخدم هذه الأساليب لتعريف كلٍّ من البرنامج الخطي والبرنامج الصحيح، وعادةً ما يكون لهما حلول مثلى مختلفة. يُسمى البرنامج الخطي برنامجًا خطيًا تكامليًا إذا كان الحل الأمثل للبرنامج الصحيح هو أيضًا الحل الأمثل للبرنامج الخطي. (وإلا، تُسمى النسبة بين قيمتي الحلين بفجوة التكامل ، وهي مهمة في تحليل خوارزميات التقريب للبرنامج الصحيح). يمكن استخدام الرسوم البيانية المثالية لتوصيف المصفوفات (0، 1).أ{\displaystyle A}(أي المصفوفات التي تكون فيها جميع المعاملات 0 أو 1) مع الخاصية التالية: إذاب{\displaystyle b}إذا كان المتجه مكونًا من جميع القيم 1 ، فعندئذٍ لجميع اختياراتج{\displaystyle c}البرنامج الخطي الناتج هو برنامج متكامل. [ 1 ]

وكما أثبت فاتسلاف شفاتال ، فإن كل مصفوفةأ{\displaystyle A}تُمثل هذه الخاصية (بعد حذف الصفوف "المهيمنة" غير ذات الصلة) مصفوفة وقوع الرؤوس مقابل الزمرة القصوى في الرسم البياني المثالي. تحتوي هذه المصفوفة على عمود لكل رأس من رؤوس الرسم البياني، وصف لكل زمرة قصوى ، بمعامل يساوي واحدًا في أعمدة الرؤوس التي تنتمي إلى الزمرة وصفرًا في الأعمدة المتبقية. تسعى البرامج الخطية التكاملية المشفرة بواسطة هذه المصفوفة إلى إيجاد المجموعة المستقلة ذات الوزن الأقصى للرسم البياني المعطى، حيث تُعطى الأوزان بواسطة المتجه.ج{\displaystyle c}[ 1 ] [ 53 ]​

بالنسبة للمصفوفةأ{\displaystyle A}وبتعريفها بهذه الطريقة من رسم بياني مثالي، فإن المتجهاتx{\displaystyle x}تحقيق نظام المتبايناتx≥0{\displaystyle x\geq 0}،أx≤1{\displaystyle Ax\leq 1}يشكل متعدد السطوح التكاملي . وهو الغلاف المحدب لمتجهات المؤشر للمجموعات المستقلة في الرسم البياني، مع أوجه تتوافق مع الزمر القصوى في الرسم البياني. الرسوم البيانية الكاملة هي الرسوم البيانية الوحيدة التي يتطابق فيها متعددا السطوح المعرفان بهذه الطريقة من المجموعات المستقلة ومن الزمر القصوى. [ 53 ]

الخوارزميات

في جميع الرسوم البيانية المثالية، يمكن حل مشكلة تلوين الرسم البياني ، ومشكلة الزمرة القصوى ، ومشكلة المجموعة المستقلة القصوى في وقت متعدد الحدود . تتضمن خوارزمية الحالة العامة عدد لوفاس لهذه الرسوم البيانية. يمكن تحديد عدد لوفاس لأي رسم بياني عن طريق تسمية رؤوسه بمتجهات وحدة عالية الأبعاد ، بحيث يكون لكل رأسين غير متجاورين تسميات متعامدة، وبحيث تقع جميع المتجهات في مخروط بزاوية فتح صغيرة قدر الإمكان. عندئذٍ، يكون عدد لوفاس هو1/كوس2⁡θ{\displaystyle 1/\cos ^{2}\theta }، أينθ{\displaystyle \theta }يمثل نصف زاوية هذا المخروط. على الرغم من هذا التعريف المعقد، يمكن حساب قيمة عددية دقيقة لعدد لوفاس باستخدام البرمجة شبه المحددة ، وبالنسبة لأي رسم بياني، يقع عدد لوفاس بين العدد اللوني وعدد الزمر. ولأن هذين العددين متساويان في الرسوم البيانية المثالية، فإنهما يساويان أيضًا عدد لوفاس. وبالتالي، يمكن حسابهما بتقريب عدد لوفاس بدقة كافية وتقريب النتيجة إلى أقرب عدد صحيح. [ 54 ] [ 55 ]

تعتمد طريقة حل البرامج شبه المحددة، المستخدمة في هذه الخوارزمية، على طريقة القطع الناقص للبرمجة الخطية . وتؤدي هذه الطريقة إلى خوارزمية ذات زمن متعدد الحدود لحساب العدد اللوني وعدد الزمر في الرسوم البيانية الكاملة. مع ذلك، فإن حل هذه المسائل باستخدام عدد لوفاس وطريقة القطع الناقص معقد ويتطلب أسًا متعدد الحدود عاليًا. [ 54 ] [ 55 ] توجد خوارزميات توافقية أكثر كفاءة للعديد من الحالات الخاصة. [ 56 ]

يمكن تعميم هذه الطريقة لإيجاد أقصى وزن لمجموعة متجانسة في رسم بياني مُثقَّل، بدلاً من عدد المجموعات المتجانسة. كما يمكن إيجاد المجموعة المتجانسة ذات الوزن الأقصى، والتلوين الأمثل للرسم البياني، باستخدام هذه الطرق، ويمكن إيجاد المجموعة المستقلة القصوى بتطبيق نفس المنهج على مُكمِّل الرسم البياني. على سبيل المثال، يمكن إيجاد المجموعة المتجانسة القصوى باستخدام الخوارزمية التالية: [ 54 ]

  • قم بالمرور على رؤوس الرسم البياني. لكل رأسv{\displaystyle v}قم بتنفيذ الخطوات التالية:
    • إزالة مؤقتةv{\displaystyle v}من الرسم البياني.
    • استخدم البرمجة شبه المحددة لتحديد رقم الزمرة للرسم البياني الفرعي الناتج.
    • إذا كان عدد هذه الزمرة هو نفسه في الرسم البياني بأكمله، فقم بإزالتها نهائيًاv{\displaystyle v}وإلا، فقم بالاستعادةv{\displaystyle v}إلى الرسم البياني.
  • أعد الرسم البياني الفرعي المتبقي بعد جميع عمليات الإزالة الدائمة.

إن خوارزمية إيجاد التلوين الأمثل أكثر تعقيدًا، وتعتمد على نظرية الازدواجية للبرامج الخطية، باستخدام خوارزمية إيجاد الزمرة هذه كأداة فصل . [ 54 ]

إلى جانب حل هذه المشكلات، تبرز مشكلة حسابية أخرى مهمة تتعلق بالرسوم البيانية الكاملة، وهي التعرف عليها، أي اختبار ما إذا كان رسم بياني معين كاملاً. لسنوات عديدة، نُظر في تعقيد التعرف على رسوم بيرج البيانية والرسوم البيانية الكاملة بشكل منفصل (لأنه لم يكن معروفًا بعدُ تكافؤهما)، وظلت كلتا المسألتين مفتوحة. كان من المعروف أن كلتيهما تنتميان إلى فئة co-NP ؛ بالنسبة لرسوم بيرج البيانية، يتبع ذلك من التعريف [ 57 ]، بينما بالنسبة للرسوم البيانية الكاملة، يتبع ذلك من التوصيف باستخدام حاصل ضرب عدد الزمر وعدد الاستقلال [ 6 ] . بعد إثبات نظرية الرسم البياني الكامل القوي، اكتشف تشودنوفسكي، وكورنيولز، وليو، وسيمور، وفوشكوفيتش خوارزمية زمنية متعددة الحدود لاختبار وجود الثقوب الفردية أو الثقوب المضادة. وبموجب نظرية الرسم البياني الكامل القوي، يمكن استخدام هذه الخوارزمية لاختبار ما إذا كان رسم بياني معين كاملاً، في زمن متعدد الحدود [ 58 ] .

بتعميم مفهوم الرسوم البيانية المثالية، يُقال إن فئة من الرسوم البيانية محدودة بـ χ إذا كان بالإمكان تحديد العدد اللوني للرسوم البيانية في هذه الفئة بدالة لعدد زمرها. الرسوم البيانية المثالية هي تحديدًا تلك الرسوم البيانية التي تكون فيها هذه الدالة هي دالة التطابق ، سواءً للرسم البياني نفسه أو لجميع الرسوم البيانية الفرعية المستحثة منه. [ 59 ]

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

مراجع

  1. 1 2 3 4 تشودنوفسكي، ماريا ؛ روبرتسون، نيل ؛ سيمور، بول ؛ توماس، روبن (2003). "التقدم في الرسوم البيانية المثالية" ( ملف PDF) . البرمجة الرياضية . 97 (1-2(ب)): 405-422 . doi : 10.1007 /s10107-003-0449-8 . MR 2004404. S2CID 5226655. Zbl 1028.05035 .   
  2. 1 2 لوفاس، لازلو (1972). "الرسوم البيانية الفائقة العادية وتخمين الرسم البياني المثالي". الرياضيات المتقطعة . 2 (3): 253-267 . doi : 10.1016/0012-365X(72)90006-4 . MR 0302480. Zbl 0239.05111 .  
  3. 1 2 كورنيجول، جيرار (2002). "فرضية الرسم البياني المثالي القوي". وقائع المؤتمر الدولي للرياضيات، المجلد الثالث (بكين، 2002) . بكين: دار النشر للتعليم العالي. ص 547-559 . arXiv : math/0304464 . MR 1957560. Zbl 1004.05034 .   
  4. 1 2 تشودنوفسكي، ماريا ؛ روبرتسون، نيل ؛ سيمور، بول ؛ توماس، روبن (2006). "نظرية الرسم البياني الكامل القوي" . حوليات الرياضيات . 164 (1): 51-229 . arXiv : math/0212070 . doi : 10.4007/annals.2006.164.51 . MR 2233847. S2CID 119151552. Zbl 1112.05042 .   
  5. 1 2 3 4 لوفاس، لازلو (1972). "وصف للرسوم البيانية المثالية". مجلة نظرية التوافيق . السلسلة ب. 13 (2): 95-98 . doi : 10.1016/0095-8956(72)90045-7 . MR 0309780. Zbl 0241.05107 .  
  6. 1 2 3 غاسباريان، جي إس (يونيو 1996). "الرسوم البيانية غير الكاملة الدنيا: منهج بسيط". كومبيناتوريكا . 16 (2): 209-212 . doi : 10.1007/bf01844846 .
  7. ↑ بادبيرغ، مانفريد دبليو. (ديسمبر 1974). "المصفوفات المثالية ذات الصفر والواحد" (ملف PDF) . البرمجة الرياضية . 6 (1): 180-196 . doi : 10.1007/bf01580235 .للاطلاع على العلاقة بين نظرية الرسم البياني المثالي القوي وتوصيف المنتج للرسوم البيانية المثالية، انظر الملاحظات السابقة للنظرية 2.1 واللاحقة للنظرية 2.2.
  8. ^ جالاي ، تيبور (1958). "الحد الأقصى والحد الأدنى Sätze über Graphen". Acta Mathematica Academiae Scientiarum Hungaricae . 9 ( 3– 4): 395– 434. دوى : 10.1007/BF02020271 . السيد 0124238 . S2CID 123953062 . زبل 0084.19603 .   
  9. ^ بيرج ، كلود (1961). "Färbung von Graphen deren sämtliche bzw. deren ungerade Kreise starr sind". ويس. Z. مارتن لوثر جامعة. هالي-فيتنبرغ الرياضيات-الطبيعة. ريهي . 10 : 114.
  10. ↑ بيرج، كلود (1963). "الرسوم البيانية المثالية". ستة أبحاث في نظرية الرسوم البيانية . كلكتا: المعهد الإحصائي الهندي. ص 1-21 . 
  11. ↑ تشودنوفسكي وآخرون (2003) ؛ لاحظ أن تشودنوفسكي وآخرون يعرفون السعة باستخدام مكمل الرسوم البيانية المستخدمة في تعريف سعة الرسم البياني في شانون ، ويشملون لوغاريتمًا لا يتضمنه المقال المرتبط.
  12. ١ ٢ ٣ ٤ هوغاردي، ستيفان (٢٠٠٦). " فئات الرسوم البيانية المثالية" . الرياضيات المتقطعة . ٣٠٦ ( ١٩-٢٠ ): ٢٥٢٩-٢٥٧١ . doi : 10.1016/j.disc.2006.05.021 . MR 2261918. Zbl 1104.05029 .  
  13. ↑ «جوائز د. ر. فولكرسون في الرياضيات المتقطعة لعام 1991» (ملف PDF) . الفائزون بجوائز عام 1991. نشرة جمعية أوبتيما: جمعية التحسين الرياضي (35): 4-8 . نوفمبر 1991. تاريخ الاطلاع: 21 يناير 2023 .
  14. ↑ ماكنزي، دانا (5 يوليو 2002). "الرياضيات: نظرية الرسم البياني تكشف جذور الكمال". مجلة ساينس . 297 (5578): 38. doi : 10.1126/science.297.5578.38 . PMID 12098683. S2CID 116891342 .  
  15. ↑ "بيان جائزة فولكرسون لعام 2009" . جمعية التحسين الرياضي . تم الاطلاع عليه بتاريخ 21 يناير 2023 .
  16. ↑ تشودنوفسكي، ماريا ؛ سيمور، بول (2005). "بنية الرسوم البيانية الخالية من المخالب" (ملف PDF) . دراسات في التوافقية 2005. أوراق من المؤتمر البريطاني العشرين للتوافقية، جامعة دورهام، دورهام، المملكة المتحدة، 10-15 يوليو 2005. مطبعة جامعة كامبريدج. الصفحات 153-171 . ISBN  0-521-61523-2. السيد 2187738 . زبل 1109.05092 .  
  17. ↑ "الرسوم البيانية ثنائية الأجزاء" . نظام معلومات حول فئات الرسوم البيانية ومحتوياتها . تم الاسترجاع في 24-01-2023 .
  18. ^ كونيج ، دينيس (1931). "Gráfok és matrixok". Matematikai és Fizikai Lapok . 38 : 116 - 119.
  19. ١ ٢ ٣ ٤ تروتر، إل إي جونيور (١٩٧٧). "الرسوم البيانية الخطية المثالية". البرمجة الرياضية . ١٢ ( ٢): ٢٥٥-٢٥٩ . doi : 10.1007/BF01593791 . MR 0457293. S2CID 38906333. Zbl 0366.05043 .   
  20. ↑ بوروس، إي .؛ غورفيتش، ف. (2006). "الرسوم البيانية المثالية، والنوى، ولب الألعاب التعاونية". الرياضيات المتقطعة . 306 ( 19-20 ): 2336-2354 . doi : 10.1016/j.disc.2005.12.031 . MR 2261906. Zbl 1103.05034 .  
  21. ^ كونيج ، دينيس (1916). "Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre" . الرياضيات أنالن . 77 (4): 453-465 . دوى : 10.1007 / BF01456961 . جي اف ام 46.0146.03 . السيد 1511872 . S2CID 121097364 .   
  22. ↑ هارتزهايم، إيغبرت (2005). "مخططات المقارنة". المجموعات المرتبة . سلسلة التقدم في الرياضيات. المجلد 7. نيويورك: سبرينغر. الصفحات 353-368 . doi : 10.1007/0-387-24222-8_12 . ISBN   0-387-24219-8. السيد 2127991 . زبل 1072.06001 .  
  23. ↑ بيرج، كلود (1967). " بعض فئات الرسوم البيانية المثالية". نظرية الرسوم البيانية والفيزياء النظرية . لندن: أكاديميك برس. ص 155-165 . MR 0232694. Zbl 0203.26403 .   
  24. 1 2 ميرسكي، ليون (1971). " ثنائية لنظرية تفكيك ديلورث". المجلة الرياضية الأمريكية الشهرية . 78 (8): 876-877 . doi : 10.2307/2316481 . JSTOR 2316481. MR 0288054. Zbl 0263.06002 .   
  25. ↑ بيرفكت، هازل (1980). " ملاحظات حول نظرية ديلورث فيما يتعلق بنظرية التقاطع" . مجلة غلاسكو الرياضية . 21 (1): 19-22 . doi : 10.1017/S0017089500003931 . MR 0558270. Zbl 0428.06001 .  
  26. ↑ بنويلي، أ .؛ ليمبل، أ .؛ إيفن، س. (1971). "التوجيه المتعدي للرسوم البيانية وتحديد رسوم التبديل" . المجلة الكندية للرياضيات . 23 : 160-175 . doi : 10.4153/CJM-1971-016-5 . MR 0292717. Zbl 0204.24604 .  
  27. ^ كولين، أنطون دبليو جيه ؛ الأماكن القريبة : باباديمتريو، كريستوس هـ . سبيكسما، فريتس سي آر (2007). "جدولة الفاصل الزمني: استطلاع" . لوجستيات البحوث البحرية . 54 (5): 530-543 . دوى : 10.1002/nav.20231 . السيد 2335544 . زبل 1143.90337 .  
  28. ↑ داغان، إيدو؛ غولومبيك، مارتن تشارلز ؛ بينتر، رون يائير (1988). "الرسوم البيانية شبه المنحرفة وتلوينها". الرياضيات التطبيقية المنفصلة . 21 (1): 35-46 . doi : 10.1016/0166-218X(88)90032-7 . MR 0953414. Zbl 0658.05067 .  
  29. ↑ روبرتس، فريد س. (1969). "مخططات اللامبالاة". تقنيات البرهان في نظرية المخططات (وقائع المؤتمر الثاني لنظرية المخططات في آن أربور، آن أربور، ميشيغان، 1968) . نيويورك: أكاديميك برس. ص 139-146 . MR 0252267. Zbl 0193.24205 .   
  30. ↑ سكرين، ديل ج. (1982). "علاقة بين الرسوم البيانية المثلثية، ورسوم المقارنة، ورسوم الفترات المناسبة، ورسوم الأقواس الدائرية المناسبة، ورسوم الفترات المتداخلة". مجلة نظرية الرسوم البيانية . 6 (3): 309-316 . doi : 10.1002/jgt.3190060307 . MR 0666799. Zbl 0495.05027 .  
  31. ↑ غولومبيك، مارتن تشارلز (1978). "الرسوم البيانية المثالية بشكل تافه". الرياضيات المتقطعة . 24 (1): 105-107 . doi : 10.1016/0012-365X(78)90178-4 . MR 0522739. Zbl 0384.05057 .  
  32. ↑ هامر، بيتر ل.؛ سيميون، برونو (1981). "انقسام الرسم البياني". كومبيناتوريكا . 1 (3): 275-284 . doi : 10.1007/BF02579333 . MR 0637832 . 
  33. ↑ بروميل، هانز يورغن؛ ستيغر ، أنجليكا (1992). " جميع مخططات بيرج تقريبًا مثالية". التوافقية، الاحتمالات والحوسبة . 1 (1): 53-79 . doi : 10.1017/S0963548300000079 . MR 1167295. S2CID 28696495. Zbl 0793.05063 .   
  34. ↑ ماكديارميد، كولين؛ يولوف، نيكولا (2019). "الرسوم البيانية المثالية العشوائية". الهياكل والخوارزميات العشوائية . 54 (1): 148-186 . arXiv : 1604.00890 . doi : 10.1002/rsa.20770 . MR 3884617. S2CID 53489550. Zbl 1405.05165 .   
  35. 1 2 روز، دونالد ج. (ديسمبر 1970). "الرسوم البيانية المثلثية وعملية الحذف". مجلة التحليل الرياضي والتطبيقات . 32 (3): 597-609 . doi : 10.1016/0022-247x(70)90282-9 .
  36. ^ ديراك، جورجيا (1961). “على الرسوم البيانية الدائرية الصلبة”. Abhandlungen aus dem Mathatischen Seminar der Universität هامبورغ . 25 ( 1 – 2): 71 – 76. دوى : 10.1007 / BF02992776 . السيد 0130190 . S2CID 120608513 .  
  37. ↑ هاراري، فرانك (1974). "نتائج حديثة حول الأشجار". في: باري، روث أ .؛ هاراري، فرانك (محرران). الرسوم البيانية والتوافقية: وقائع مؤتمر العاصمة حول نظرية الرسوم البيانية والتوافقية في جامعة جورج واشنطن، 18-22 يونيو 1973. سلسلة محاضرات في الرياضيات. المجلد 406. سبرينغر. الصفحات 1-9 . doi : 10.1007/bfb0066429 . ISBN   9783540378099.
  38. ↑ فولديس، ستيفان؛ هامر، بيتر لاديسلاو (1977). "الرسوم البيانية المنقسمة". وقائع المؤتمر الثامن لجنوب شرق الولايات المتحدة حول التوافقية ونظرية الرسوم البيانية والحوسبة (جامعة ولاية لويزيانا، باتون روج، لويزيانا، 1977) . كونغرسوس نوميرانتيوم. المجلد التاسع عشر. وينيبيغ: يوتيليتاس ماث. الصفحات 311-315 . MR 0505860 .   
  39. 1 2 باندلت، هانز-يورغن؛ مولدر، هنري مارتن (1986). "الرسوم البيانية الوراثية للمسافة". مجلة نظرية التوافيق . السلسلة ب. 41 (2): 182-208 . doi : 10.1016 / 0095-8956(86)90043-2 . ​​MR 0859310. Zbl 0605.05024 .  
  40. ↑ يونغ، هـ. أ. (1978). "حول فئة من المجموعات المرتبة جزئيًا ورسوم المقارنة المقابلة لها" . مجلة نظرية التوافيق، السلسلة ب . 24 (2): 125-133 . doi : 10.1016/0095-8956(78)90013-8 . Zbl 0382.05045 . 
  41. ↑ كورنيل، دي جي ؛ ليرشس، إتش؛ ستيوارت بيرلينغهام، إل. (1981). "الرسوم البيانية المختزلة التكميلية". الرياضيات التطبيقية المنفصلة . 3 (3): 163-174 . doi : 10.1016/0166-218X(81)90013-5 . MR 0619603. Zbl 0463.05057 .  
  42. 1 2 كاي، ديفيد سي؛ تشارتراند، غاري (1965). "وصف لبعض الرسوم البيانية البطلمية" . المجلة الكندية للرياضيات . 17 : 342-346 . doi : 10.4153/CJM-1965-034-0 . MR 0175113. Zbl 0139.17301 .  
  43. ↑ هيغيرنيس، بينار ؛ كراتش، ديتر (2007). "خوارزميات التعرف المعتمدة ذات الزمن الخطي والرسوم البيانية الفرعية المحظورة المستحثة" (ملف PDF) . المجلة الإسكندنافية للحوسبة . 14 ( 1-2 ): 87-108 (2008). MR 2460558. Zbl 1169.68653 . مؤرشف من الأصل (ملف PDF) في 24 أبريل 2008.  
  44. ↑ "الرسوم البيانية العتبية" . نظام معلومات حول فئات الرسوم البيانية ومحتوياتها . تم الاسترجاع في 12 فبراير 2023 .
  45. ↑ غافريل، فانيكا (1972). "خوارزميات للتلوين الأدنى، والزمرة القصوى، والتغطية الدنيا بواسطة الزمر، والمجموعة المستقلة القصوى للرسم البياني الوترية". مجلة SIAM للحوسبة . 1 (2): 180-187 . doi : 10.1137/0201013 .
  46. ↑ هامر، بيتر ل.؛ مافري، فريدريك (1990). "الرسوم البيانية القابلة للفصل تمامًا" . الرياضيات التطبيقية المنفصلة . 27 ( 1-2 ): 85-99 . doi : 10.1016/0166-218x(90)90131-u .
  47. ↑ هوانغ، سي تي؛ ريد، بي إيه (سبتمبر 1989). "بعض فئات الرسوم البيانية القابلة للترتيب التام". مجلة نظرية الرسوم البيانية . 13 (4): 445-463 . doi : 10.1002/jgt.3190130407 .
  48. ↑ غيارفاس، أ.؛ ليهيل، ج. (يونيو 1988). "تلوين الرسوم البيانية عبر الإنترنت والتلوين الأولي". مجلة نظرية الرسوم البيانية . 12 (2): 217-227 . doi : 10.1002/jgt.3190120212 .
  49. ↑ غولومبيك، مارتن تشارلز ؛ ترينك، آن ن. (2004). رسوم بيانية للتسامح . دراسات كامبريدج في الرياضيات المتقدمة. المجلد 89. مطبعة جامعة كامبريدج. doi : 10.1017/CBO9780511542985 . ISBN  0-521-82758-2MR 2051713 .​ 
  50. ↑ هوانغ، سي تي (1987). " حول تخمين مينيل". مجلة نظرية التوافيق، السلسلة ب . 42 (3): 302-312 . doi : 10.1016/0095-8956(87)90047-5 . MR 0888682. Zbl 0634.05058 .  
  51. ↑ سيسيروني، سيرافينو؛ دي ستيفانو، غابرييل (1999). "فئات الرسوم البيانية بين الرسوم البيانية الزوجية والرسوم البيانية الوراثية للمسافة". الرياضيات التطبيقية المنفصلة . 95 ( 1-3 ): 197-216 . doi : 10.1016/S0166-218X(99)00075-X . MR 1708837. Zbl 0933.05144 .  
  52. ↑ جانسن، كلاوس (1998). "توصيف جديد لرسوم التكافؤ ومسألة تلوين مع التكاليف". في: لوتشيسي، كلاوديو ل.؛ مورا، أرنالدو ف. (محرران). LATIN '98: المعلوماتية النظرية، الندوة اللاتينية الأمريكية الثالثة، كامبيناس، البرازيل، 20-24 أبريل 1998، وقائع المؤتمر . سلسلة محاضرات في علوم الحاسوب. المجلد 1380. سبرينغر. الصفحات 249-260 . doi : 10.1007/BFb0054326 . hdl : 11858/00-001M-0000-0014-7BE2-3 . ISBN   978-3-540-64275-6. السيد 1635464 . زبل 0910.05028 .  
  53. 1 2 تشفاتال، فاكلاف (1975). "حول بعض متعددات الوجوه المرتبطة بالرسوم البيانية". مجلة نظرية التوافيق، السلسلة ب . 18 (2): 138-154 . doi : 10.1016 / 0095-8956(75)90041-6 . MR 0371732. Zbl 0277.05139 .  
  54. 1 2 3 4 جروتشيل, مارتن ; الأماكن القريبة : شريفر ، ألكسندر (1984). "خوارزميات متعددة الحدود للرسوم البيانية المثالية" . في بيرج، سي. شفاتال، ف. (محرران). موضوعات عن الرسوم البيانية المثالية . دراسات الرياضيات في شمال هولندا. المجلد. 88. شمال هولندا، أمستردام. الصفحات من 325 إلى 356. دوى : 10.1016/S0304-0208(08)72943-8 . رقم ISBN   978-0-444-86587-8MR 0778770 .​ 
  55. 1 2 جروتشيل, مارتن ; الأماكن القريبة : شريفر ، ألكسندر (1988). الخوارزميات الهندسية والتحسين التوافقي . سبرينغر-فيرلاغ. السيد 0936633 . زبل 0634.05001 .  انظر على وجه الخصوص الفصل 9، "المجموعات المستقرة في الرسوم البيانية"، الصفحات  273-303.
  56. ↑ غولومبيك، مارتن تشارلز (1980). نظرية الرسم البياني الخوارزمية والرسوم البيانية المثالية . دار النشر الأكاديمية. doi : 10.1016/C2013-0-10739-8 . ISBN 0-444-51530-5.الطبعة الثانية، حوليات الرياضيات المتقطعة 57، إلسيفير، 2004.
  57. ↑ لوفاس، لازلو (1983). "الرسوم البيانية المثالية". في بينيك، لويل دبليو .؛ ويلسون، روبن جيه. (محرران). مواضيع مختارة في نظرية الرسوم البيانية، المجلد 2. دار النشر الأكاديمية. الصفحات 55-87 . ISBN  0-12-086202-6.
  58. ^ شودنوفسكي، ماريا ؛ الأماكن القريبة : ليو، شينمينغ؛ سيمور, بول ; فوسكوفيتش، كريستينا (2005). “التعرف على الرسوم البيانية بيرج”. كومبيناتوريكا . 25 (2): 143-186 . دوى : 10.1007 / s00493-005-0012-8 . S2CID 2229369 . 
  59. ↑ غيارفاس، أ. (1987). "مشكلات من العالم المحيط بالرسوم البيانية المثالية" (ملف PDF) . وقائع المؤتمر الدولي حول التحليل التوافقي وتطبيقاته (بوكريزونا، 1985). زاستوسوفانيا ماتيماتيكي . 19 ( 3-4 ): 413-441 (1988). MR 0951359 . 
  60. ↑ فودري، رالف ؛ فلاندري، إيفلين؛ رياتشيك، زدينيك (1997). "الرسوم البيانية الخالية من المخالب - دراسة استقصائية" . الرياضيات المتقطعة . 164 ( 1-3 ): 87-147 . doi : 10.1016/S0012-365X(96)00045-3 . MR 1432221 .