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

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

إن مكمل الرسم البياني ليس مكمل المجموعة للرسم البياني: فقط الحواف هي التي يتم إكمالها.

ليكن G = ( V , E ) رسمًا بيانيًا بسيطًا غير موجه ، وليكن P يتكون من جميع أزواج الرؤوس المختلفة في V. عندئذٍ ، يكون الرسم البياني البسيط غير الموجه H = ( V , P \ E ) مكملًا لـ G ، ^{[ 2 ]} حيث P \ E هو المكمل النسبي لـ E في P.

ليكن G = ( V , A ) رسمًا بيانيًا بسيطًا موجهًا، وليكن O يتكون من جميع الأزواج المرتبة من الرؤوس المختلفة في V. عندئذٍ يكون الرسم البياني البسيط الموجه H = ( V , O \ A ) هو مكمل G.

ليكن G رسمًا بيانيًا بسيطًا غير موجه/موجه، وليكن K الرسم البياني البسيط الكامل غير الموجه/الموجه على نفس عدد الرؤوس (أي أن جميع المدخلات تساوي واحدًا باستثناء مدخلات القطر التي تساوي صفرًا)،${\displaystyle \mathbb {A} (G)}$و${\displaystyle \mathbb {A} (K)}$إذا كانت H و K مصفوفات تجاور G و K على التوالي ، فإن مصفوفة تجاور المتممة H لـ G هي:${\displaystyle \mathbb {A} (H)=\mathbb {A} (K)-\mathbb {A} (G)}$.

المكمل غير معرف للرسوم البيانية المتعددة .

بالنسبة للرسوم البيانية التي تسمح بالحلقات الذاتية (ولكن ليس بالتجاور المتعدد)، يمكن تعريف مكمل الرسم البياني G بإضافة حلقة ذاتية إلى كل رأس لا يحتوي على حلقة ذاتية في G ، وإزالة هذه الحلقة الذاتية من كل رأس يحتوي على حلقة ذاتية في G ، وبخلاف ذلك، يتم استخدام الصيغة نفسها المذكورة أعلاه. مع ذلك، تختلف هذه العملية عن تلك الخاصة بالرسوم البيانية البسيطة، إذ أن تطبيقها على رسم بياني لا يحتوي على حلقات ذاتية ينتج عنه رسم بياني يحتوي على حلقات ذاتية في جميع رؤوسه.

ترتبط العديد من المفاهيم المتعلقة بنظرية الرسم البياني ببعضها البعض من خلال التكامل:

• مكمل الرسم البياني عديم الحواف هو رسم بياني كامل ، والعكس صحيح.
• أي رسم بياني فرعي مستحث من الرسم البياني المكمل للرسم البياني G هو مكمل الرسم البياني الفرعي المستحث المقابل في G.
• تُعتبر المجموعة المستقلة في الرسم البياني زمرةً في الرسم البياني المُكمِّل، والعكس صحيح. هذه حالة خاصة من الخاصيتين السابقتين، حيث أن المجموعة المستقلة هي رسم بياني فرعي مُستحث بدون حواف، والزمرة هي رسم بياني فرعي مُستحث كامل.
• مجموعة التشاكل الذاتي للرسم البياني هي مجموعة التشاكل الذاتي لمكمله.
• إن مكمل كل رسم بياني خالٍ من المثلثات هو رسم بياني خالٍ من المخالب ، ^{[ 3 ]} ولكن العكس ليس صحيحًا.

الرسم البياني المُكمِّل ذاتيًا هو رسم بياني متماثل مع مُكمِّله. ^{[ 1 ]} ومن الأمثلة عليه الرسم البياني للمسار ذي الرؤوس الأربعة والرسم البياني للدورة ذي الرؤوس الخمسة . ولا توجد خصائص معروفة للرسوم البيانية المُكمِّلة ذاتيًا.

هناك عدة فئات من الرسوم البيانية مكملة ذاتيًا، بمعنى أن مكمل أي رسم بياني في إحدى هذه الفئات هو رسم بياني آخر في نفس الفئة.

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

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