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

في مجال نظرية المخططات الرياضية ، يُعرف المخطط التكميلي الذاتي بأنه مخطط متماثل مع مكمله . وأبسط المخططات التكميلية الذاتية غير التافهة هي مخطط المسار ذو 4 رؤوس ومخطط الدورة ذو 5 رؤوس .

كل رسم بياني من نوع بالي مكمل ذاتيًا. ^{[ 1 ]} على سبيل المثال، رسم الرخ 3 × 3 (رسم بالي من الرتبة 9) مكمل ذاتيًا، وذلك بفضل تناظر يُبقي الرأس المركزي في مكانه ولكنه يُبدل أدوار نقاط المنتصف الأربعة للأضلاع وزوايا الشبكة الأربع. ^{[ 2 ]} جميع الرسوم البيانية المنتظمة بقوة والمكملة ذاتيًا والتي تحتوي على أقل من 37 رأسًا هي رسوم بيانية من نوع بالي؛ ومع ذلك، توجد رسوم بيانية منتظمة بقوة تحتوي على 37 و41 و49 رأسًا وليست رسومًا بيانية من نوع بالي. ^{[ 3 ]}

يُعد مخطط رادو مخططًا لانهائيًا مكملًا ذاتيًا. ^{[ 4 ]}

يحتوي الرسم البياني المكمل ذاتيًا ذو n رأسًا على نصف عدد حواف الرسم البياني الكامل بالضبط ، أي n ( n − 1)/4 حافة، وإذا كان هناك أكثر من رأس واحد، فيجب أن يكون قطره إما 2 أو 3. ^{[ 1 ]} بما أن n ( n − 1) يجب أن يكون قابلاً للقسمة على 4، فيجب أن يكون n متطابقًا مع 0 أو 1 بتردد 4؛ على سبيل المثال، لا يمكن أن يكون الرسم البياني ذو 6 رؤوس مكملًا ذاتيًا.

إن مشكلتي التحقق مما إذا كان الرسمان البيانيان المتكاملان ذاتيًا متماثلين، والتحقق مما إذا كان الرسم البياني المعطى متكاملًا ذاتيًا، مكافئتان من حيث الوقت متعدد الحدود لمشكلة تماثل الرسم البياني العامة . ^{[ 5 ]}

• وايسشتاين، إريك دبليو ، "الرسم البياني التكميلي الذاتي" ، عالم الرياضيات