نظرية الفاصل للرسوم البيانية مع قاصر مستبعد وتطبيقاتها

يتوافق مع G في الزمن 0(n3/2). كما نصف دعوة G لتكون رسمًا بيانيًا ب n رأس مع أوزان غير سلبية مجموعها 1 مخصصة لرؤوسه، وبدون قاصر متماثل لرسم بياني معين ب h رأس H. نثبت أنه يوجد مجموعة X لا تزيد عن h3/2nl/2 من رؤوس G، حيث يؤدي حذفها إلى إنشاء رسم بياني يكون فيه الوزن الكلي لكل مكون متصل لا يزيد عن 1/2. هذا يمثل تمديدًا كبيرًا لنظرية معروفة لـ Lipton وTarjan للرسوم البيانية المستوية. نقدم خوارزمية التي تجد، نظرًا لرسم بياني ب n رأس G مع أوزان كما هو موضح أعلاه ورسم بياني ب h رأس H، إما مثل تلك المجموعة X أو قاصر لـ G متماثل لـ H. تعمل الخوارزمية في الزمن O(hl/2nl/2m)، حيث m هو عدد الحواف لـ G زائد عدد رؤوسه. تزود نتائجنا بتمديدات للعديد من التطبيقات المعروفة لنظرية فاصل Lipton-Tarjan من فئة الرسوم البيانية المستوية (أو فئة الرسوم البيانية ذات الجينوس المحدود) إلى أي فئة من الرسوم البيانية مع قاصر مستبعد. على سبيل المثال، يتبع أنه لأي رسم بياني ثابت H، نظرًا لرسم بياني G ب n رؤوس وبدون قاصر H يمكن تقدير حجم مجموعة الاستقلال القصوى لـ G بدقة نسبية تصل إلى 1/~/l-b-~ في وقت كثيرات الحدود، إيجاد هذا الحجم بدقة وإيجاد العدد اللوني لـ G في الزمن 2 ('~-) وحل أي نظام متفرق من n معادلات خطية في n مجهولاً هيكل الفراغ الخاص بها.