التوسع المحدود

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

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

التعريفات المكافئة لفئات التوسعات المحدودة هي أن جميع القواسم الجزئية الضحلة لها عدد لوني محدود بدالة لـ t ، ^{[ 1 ]} أو أن للعائلة المعطاة قيمة محدودة لمعامل طوبولوجي . هذا المعامل هو ثابت بياني رتيب عند أخذ الرسوم البيانية الجزئية، بحيث لا تتغير قيمة المعامل إلا بطريقة مضبوطة عند تقسيم الرسم البياني، وبحيث تشير قيمة المعامل المحدودة إلى أن الرسم البياني له انحلال محدود . ^{[ 2 ]}

يُعدّ مفهوم التوسيع متعدد الحدود مفهومًا أقوى ، ويعني أن الدالة f المستخدمة لتقييد كثافة حواف القواسم الجزئية الضحلة هي دالة متعددة الحدود . إذا كانت عائلة رسوم بيانية وراثية تخضع لنظرية فاصلة ، تنص على أنه يمكن تقسيم أي رسم بياني ذي n رأس في العائلة إلى أجزاء تحتوي على n /2 رأس على الأكثر عن طريق إزالة O ( nc ⁾ رأسًا لثابت c  <  1، فإن هذه العائلة تمتلك بالضرورة توسيعًا متعدد الحدود. وعلى العكس من ذلك، فإن الرسوم البيانية ذات التوسيع متعدد الحدود تمتلك نظريات فاصلة شبه خطية. ^{[ 3 ]}

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

على الرغم من أن الرسوم البيانية ذات سُمك الكتاب المحدود لا تحتوي على فواصل شبه خطية، ^{[ 9 ]} إلا أنها تتميز أيضًا بتوسع محدود. ^{[ 10 ]} تشمل الرسوم البيانية الأخرى ذات التوسع المحدود الرسوم البيانية ذات الدرجة المحدودة، ^{[ 11 ]} والرسوم البيانية العشوائية ذات الدرجة المتوسطة المحدودة في نموذج إردوش-ريني ، ^{[ 12 ]} والرسوم البيانية ذات عدد الطوابير المحدود . ^{[ 2 ] [ 13 ]}

يمكن حلّ مسائل تماثل الرسوم البيانية الجزئية، التي يكون الهدف فيها إيجاد رسم بياني مستهدف ذي حجم محدود، كرسم بياني جزئي لرسم بياني أكبر حجمه غير محدود، في زمن خطي عندما ينتمي الرسم البياني الأكبر إلى عائلة من الرسوم البيانية ذات التوسع المحدود. وينطبق الأمر نفسه على إيجاد الزمر ذات الحجم الثابت، أو إيجاد المجموعات المهيمنة ذات الحجم الثابت، أو بشكل أعم، اختبار الخصائص التي يمكن التعبير عنها بصيغة ذات حجم محدود في منطق الرتبة الأولى للرسوم البيانية . ^{[ 14 ] [ 15 ]}

بالنسبة للرسوم البيانية ذات التوسع متعدد الحدود، توجد مخططات تقريبية متعددة الحدود لمسألة تغطية المجموعة ، ومسألة المجموعة المستقلة القصوى ، ومسألة المجموعة المهيمنة ، والعديد من مسائل تحسين الرسوم البيانية الأخرى ذات الصلة. ^{[ 16 ]}