الرسم البياني للعتبة

في نظرية الرسوم البيانية ، الرسم البياني العتبة هو رسم بياني يمكن إنشاؤه من رسم بياني ذي رأس واحد عن طريق التطبيق المتكرر للعمليتين التاليتين:

1. إضافة رأس معزول واحد إلى الرسم البياني.
2. إضافة رأس مهيمن واحد إلى الرسم البياني، أي رأس واحد متصل بجميع الرؤوس الأخرى.

على سبيل المثال، الرسم البياني للشكل هو رسم بياني عتبوي. يمكن إنشاؤه بالبدء برسم بياني ذي رأس واحد (الرأس 1)، ثم إضافة رؤوس سوداء كرؤوس معزولة ورؤوس حمراء كرؤوس مهيمنة، بالترتيب الذي تم ترقيمها به.

تم تقديم الرسوم البيانية العتبية لأول مرة بواسطة تشفاتال وهامر (1977) . ويظهر فصل عن الرسوم البيانية العتبية في كتاب غولومبيك (1980) ، كما أن كتاب ماهاديف وبيليد (1995) مخصص لها.

التعريف المكافئ هو التالي: الرسم البياني هو رسم بياني عتبة إذا كان هناك عدد حقيقي${\displaystyle S}$ولكل رأس${\displaystyle v}$وزن رأس حقيقي${\displaystyle w(v)}$بحيث يكون لأي رأسين${\displaystyle v,u}$،${\displaystyle uv}$تكون الحافة إذا وفقط إذا${\displaystyle w(u)+w(v)>S}$.

تعريف مكافئ آخر هو التالي: الرسم البياني هو رسم بياني عتبة إذا كان هناك عدد حقيقي${\displaystyle T}$ولكل رأس${\displaystyle v}$وزن رأس حقيقي${\displaystyle a(v)}$بحيث يكون لأي مجموعة رؤوس${\displaystyle X\subseteq V}$،${\displaystyle X}$تكون مستقلة إذا وفقط إذا${\displaystyle \sum _{v\in X}a(v)\leq T.}$

يأتي اسم "الرسم البياني العتبة" من هذه التعريفات: S هي "العتبة" لخاصية كونها حافة، أو بشكل مكافئ T هي العتبة لكونها مستقلة.

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

انطلاقاً من التعريف الذي يستخدم الإضافة المتكررة للرؤوس، يمكن للمرء أن يستنتج طريقة بديلة لوصف الرسم البياني للعتبة بشكل فريد، عن طريق سلسلة من الرموز.${\displaystyle \epsilon }$يمثل دائمًا الحرف الأول من السلسلة، ويمثل الرأس الأول للرسم البياني. كل حرف لاحق إما${\displaystyle u}$، وهو ما يشير إلى إضافة رأس معزول (أو رأس اتحاد )، أو${\displaystyle j}$، وهو ما يشير إلى إضافة رأس مهيمن (أو رأس ربط ). على سبيل المثال، السلسلة${\displaystyle \epsilon uuj}$يمثل رسمًا بيانيًا نجميًا بثلاثة فروع، بينما${\displaystyle \epsilon uj}$يمثل مسارًا على ثلاثة رؤوس. يمكن تمثيل الرسم البياني للشكل على النحو التالي:${\displaystyle \epsilon uuujuuj}$

تُعدّ الرسوم البيانية العتبية حالة خاصة من الرسوم البيانية التكميلية ، والرسوم البيانية المنقسمة ، والرسوم البيانية الكاملة التافهة . يكون الرسم البياني رسمًا بيانيًا عتبيًا إذا وفقط إذا كان رسمًا بيانيًا تكميليًا ورسمًا بيانيًا منقسمًا في آنٍ واحد. كل رسم بياني يكون رسمًا بيانيًا كاملًا تافهًا ورسمًا بيانيًا مكملًا لرسم بياني كامل تافه هو رسم بياني عتبي. كما تُعدّ الرسوم البيانية العتبية حالة خاصة من الرسوم البيانية الفاصلية . يمكن تفسير جميع هذه العلاقات من خلال خصائصها بواسطة الرسوم البيانية الفرعية المستحثة المحظورة. الرسم البياني التكميلي هو رسم بياني لا يحتوي على مسار مستحث على أربعة رؤوس، P⁴ _، بينما الرسم البياني العتبي هو رسم بياني لا يحتوي على P⁴ مستحث _، C⁴ _، ولا 2K⁲ _. C⁴ _هي دورة من أربعة رؤوس، و2K⁲ _هي مكملتها، أي حافتان منفصلتان. وهذا يفسر أيضًا سبب كون الرسوم البيانية العتبية مغلقة عند أخذ المكملات. إن P ₄ مكمل ذاتيًا، وبالتالي إذا كان الرسم البياني خاليًا من P ₄ - و C ₄ - و 2K _{2 -} فإن مكمله كذلك.

أظهر هيجيرنيس وكراتش (2007) أنه يمكن التعرف على الرسوم البيانية العتبية في وقت خطي؛ إذا لم يكن الرسم البياني عتبة، فسيتم إخراج عائق (واحد من P ₄ أو C ₄ أو 2K _{2 ).}

• رسم بياني للحياد
• رسم بياني متسلسل-متوازي
• الرسوم البيانية الفائقة ذات العتبة ^{[ 1 ]}

• تشفاتال، فاكلاف ؛ هامر، بيتر ل. (1977)، "تجميع المتباينات في البرمجة العددية الصحيحة"، في هامر، ب. ل.؛ جونسون، إ. ل.؛ كورت، ب. هـ.؛ وآخرون (  محررون)، دراسات في البرمجة العددية الصحيحة (وقائع ورشة عمل بون 1975) ، حوليات الرياضيات المتقطعة، المجلد  1، أمستردام: نورث هولاند، الصفحات 145-162 .
• جولومبيك، مارتن تشارلز (1980)، نظرية الرسم البياني الخوارزمية والرسوم البيانية المثالية ، نيويورك: أكاديميك برسالطبعة الثانية، حوليات الرياضيات المتقطعة، 57 ، إلسيفير، 2004.
• هيغيرنيس، بينار ؛ كراتش، ديتر (2007)، "خوارزميات التعرف المعتمدة ذات الوقت الخطي والرسوم البيانية الفرعية المستحثة المحظورة" (ملف PDF) ، المجلة الإسكندنافية للحوسبة ، 14 ( 1-2 ): 87-108 (2008)، MR 2460558 ، مؤرشف من الأصل (ملف PDF) في 24 أبريل 2008 .
• ماهاديف، إن في آر؛ بيليد، أوري إن. (1995)، الرسوم البيانية العتبية والمواضيع ذات الصلة ، إلسيفير.

• الرسوم البيانية العتبية ، نظام معلومات حول فئات الرسوم البيانية ومحتوياتها.