الرسم البياني الخطي المثالي
في نظرية الرسم البياني ، الرسم البياني الخطي المثالي هو الرسم البياني الذي يكون رسمه الخطي رسمًا بيانيًا مثاليًا . وعلى نحو مكافئ، هذه هي الرسوم البيانية التي يكون فيها كل دورة بسيطة ذات طول فردي عبارة عن مثلث. [1]
يكون الرسم البياني خطيًا مثاليًا إذا وفقط إذا كان كل من مكوناته المتصلة رسمًا بيانيًا ثنائي الأجزاء ، أو الرسم البياني الكامل K 4 ، أو كتابًا مثلثيًا K 1,1, n . [2] ولأن هذه الأنواع الثلاثة من المكونات المتصلة هي كلها رسوم بيانية مثالية في حد ذاتها، فإن كل رسم بياني خطي مثالي يكون في حد ذاته مثاليًا. [1] وبنفس المنطق، فإن كل رسم بياني خطي مثالي هو رسم بياني تكافؤ ، [3] ورسم بياني ماينيل ، [4] ورسم بياني قابل للترتيب تمامًا .
تعمم الرسوم البيانية الخطية المثالية الرسوم البيانية ثنائية الأجزاء، وتشترك معها في الخصائص التي تتمثل في أن الحد الأقصى للمطابقة والحد الأدنى لغطاء الرأس لهما نفس الحجم، وأن المؤشر اللوني يساوي الدرجة القصوى . [5]
انظر أيضا
- الرسم البياني المختنق ، وهو الرسم البياني الذي تكون فيه كل دورة محيطية على شكل مثلث
مراجع
- ^ ab Trotter, LE Jr. (1977)، "الرسوم البيانية الخطية المثالية"، البرمجة الرياضية ، 12 (2): 255–259، doi :10.1007/BF01593791، MR 0457293
- ^ مافري، فريديريك (1992)، "النوى في الرسوم البيانية الخطية المثالية"، مجلة النظرية التوافقية ، السلسلة ب، 55 (1): 1-8، doi : 10.1016/0095-8956(92)90028-V ، MR 1159851.
- ^ غروتشل، مارتن ؛ الأماكن القريبة : Schrijver، Alexander (1993)، الخوارزميات الهندسية والتحسين التوافقي، الخوارزميات والتوافقيات، المجلد. 2 (الطبعة الثانية)، سبرينغر-فيرلاغ، برلين، دوى :10.1007 / 978-3-642-78240-4، ISBN 978-3-642-78242-8السيد 1261419
- ^ Wagler, Annegret (2001)، "Critical and anticritical edge in perfect graphs"، مفاهيم نظرية الرسم البياني في علوم الكمبيوتر: ورشة العمل الدولية السابعة والعشرون، مجموعة العمل 2001، بولتنهاجن، ألمانيا، 14-16 يونيو 2001، وقائع ، مذكرات محاضرات في علوم الكمبيوتر، المجلد 2204، برلين: سبرينغر، ص 317-327، doi :10.1007/3-540-45477-2_29، MR 1905643.
- ^ دي فيرا، د. (1978)، "الرسوم البيانية على الخط المثالي"، البرمجة الرياضية ، 15 (2): 236-238، doi :10.1007/BF01609025، MR 0509968.
