الرسم البياني الفائق ذو الفاصل الزمني D

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

أبسط الحالات هي d = 1. مجموعة رؤوس الرسم البياني الفائق ذي الفاصل الواحد هي مجموعة الأعداد الحقيقية؛ كل حافة في هذا الرسم البياني الفائق هي فاصلة من خط الأعداد الحقيقية. على سبيل المثال، المجموعة { [−2, −1], [0, 5], [3, 7]} تُعرّف رسمًا بيانيًا فائقًا ذا فاصل واحد. لاحظ الفرق بينه وبين الرسم البياني الفاصل : في الرسم البياني الفاصل، تكون الرؤوس هي الفواصل ( مجموعة منتهية )؛ أما في الرسم البياني الفائق ذي الفاصل الواحد، فتكون الرؤوس جميع النقاط على خط الأعداد الحقيقية ( مجموعة غير قابلة للعد ).

كمثال آخر، في الرسم البياني الفائق ذي الفترات الثنائية، تكون مجموعة الرؤوس عبارة عن اتحاد منفصل لخطين حقيقيين، وكل حافة هي اتحاد فترتين: واحدة في الخط رقم 1 وواحدة في الخط رقم 2.

يتم تعريف المفهومين التاليين للرسوم البيانية الفائقة ذات الفترات الزمنية d تمامًا كما هو الحال بالنسبة للرسوم البيانية الفائقة المحدودة:

• التطابق هو مجموعة من الحواف غير المتقاطعة، أي مجموعة من الفترات غير المتقاطعة ذات d . على سبيل المثال، في الرسم البياني الفائق ذي الفترة الواحدة {[−2, −1], [0, 5], [3, 7]}، تُعدّ المجموعة {[−2, −1], [0, 5]} تطابقًا بحجم 2، بينما لا تُعدّ المجموعة {[0, 5], [3, 7]} تطابقًا لأن عناصرها متقاطعة. يُرمز إلى أكبر حجم تطابق في H بالرمز ν ( H ) .
• التغطية أو المقطع العرضي هو مجموعة من الرؤوس التي تتقاطع مع كل حافة، أي مجموعة من النقاط التي تتقاطع مع كل فاصل زمني من الرتبة d . على سبيل المثال، في الرسم البياني الفائق ذي الفاصل الزمني الواحد {[−2, −1], [0, 5], [3, 7]}، تُعدّ المجموعة {−1.5, 4} تغطية بحجم 2، بينما لا تُعدّ المجموعة {−1.5, 1} تغطية لأنها لا تتقاطع مع الحافة [3, 7] . يُرمز إلى أصغر حجم مقطع عرضي في H بالرمز τ ( H ) .

ν ( H ) ≤ τ ( H ) صحيح لأي رسم بيانيفائق H.

أثبت تيبور جالاي أنه في الرسم البياني الفائق ذي الفاصل الزمني الواحد، يكونان متساويين: τ ( H ) = ν ( H ) . وهذا مماثل لنظرية كونيغ للرسوم البيانية ثنائية الأجزاء .

أثبت غابور تاردوس ^{[ 1 ]} أنه في الرسم البياني الفائق ذي الفترات 2، τ ( H ) ≤ 2ν ( H ) ، وهو محكم (أي أن كل رسم بياني فائق ذي فترات 2 مع مطابقة بحجم m ، يمكن تغطيته بواسطة 2m نقطة ).

أثبت كايزر ^{[ 2 ]} أنه في الرسم البياني الفائق ذي الفاصل الزمني d ، فإن τ ( H ) ≤ d ( d – 1) ν ( H ) ، وعلاوة على ذلك، يمكن تغطية كل رسم بياني فائق ذي فاصل زمني d مع مطابقة بحجم m ، بواسطة d ( d − 1) m نقطة، ( d − 1) m نقطة على كل خط.

أثبت فريك وزربيب ^{[ 3 ]} نسخة ملونة (" قوس قزح ") من هذه النظرية.