غطاء الرؤوس في الرسوم البيانية الفائقة

في نظرية المخططات ، يُعرَّف غطاء الرؤوس في المخطط الفائق بأنه مجموعة من الرؤوس ، بحيث يحتوي كل ضلع فائق في المخطط الفائق على رأس واحد على الأقل من تلك المجموعة. وهو امتداد لمفهوم غطاء الرؤوس في المخطط. ^{[ 1 ] : 466-470 [ 2 ]}

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

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

تذكر أن الرسم البياني الفائق H هو زوج ( V ، E ) ، حيث V هي مجموعة من الرؤوس و E هي مجموعة من المجموعات الجزئية من V تسمى الحواف الفائقة . قد تحتوي كل حافة فائقة على رأس واحد أو أكثر.

يتم تعيين غطاء الرأس (المعروف أيضًا باسم مجموعة الضرب أو العرضي ) في H T ⊆ V بحيث يكون لجميع الحواف الفائقة e ∈ E ، أن T ∩ e ​​≠ ∅ .

يُعرف عدد تغطية الرؤوس ( أو العدد المستعرض ) للرسم البياني الفائق H بأنه أصغر حجم لتغطية الرؤوس في H. ويُرمز له غالبًا بالرمز τ ( H ) . ^{[ 1 ] : 466}

على سبيل المثال، إذا كان H هو هذا الرسم البياني الفائق المنتظم ثلاثي الأبعاد:

{ {1,2,3}, {1,4,5}, {4,5,6}, {2,3,6} }

ثم تقبل H عدة أغطية رأسية بحجم 2، على سبيل المثال:

{1، 6}

ومع ذلك، لا توجد مجموعة فرعية بحجم 1 تغطي جميع الحواف الفائقة لـ H. وبالتالي فإن عدد تغطية الرؤوس لـ H هو 2.

لاحظ أننا نعود إلى حالة تغطية الرؤوس للرسوم البيانية البسيطة إذا كان الحد الأقصى لحجم الحواف الفائقة هو 2.

يتم تعريف المشكلات الحسابية لمجموعة الضرب الأدنى ومجموعة الضرب كما هو الحال في حالة الرسوم البيانية.

إذا كان الحد الأقصى لحجم الحافة الفائقة محصورًا في d ، فإن مسألة إيجاد مجموعة الضربات الدنيا من d تسمح بخوارزمية تقريبية من d . وبافتراض صحة فرضية الألعاب الفريدة ، فإن هذه هي أفضل خوارزمية ^ذات عامل ثابت ممكنة، وإلا فإنه من الممكن تحسين التقريب إلى d − 1. ^{[ 3} ]

بالنسبة لمسألة مجموعة الضرب، فإنّ استخدام معلمات مختلفة أمر منطقي. ^{[ 4 ]} تُعتبر مسألة مجموعة الضرب مسألة W [2] كاملة بالنسبة للمعلمة OPT ، أي أنه من غير المرجح وجود خوارزمية تعمل في زمن f (OPT) ⁿO ^{(1)، حيث} OPT هي عدد عناصر أصغر مجموعة ضرب. تكون مسألة مجموعة الضرب قابلة للحل بمعامل ثابت بالنسبة للمعلمة OPT + d ، حيث d هو حجم أكبر حافة في الرسم البياني الفائق. وبشكل أكثر تحديدًا، توجد خوارزمية لمجموعة الضرب تعمل في زمن d ^OPTⁿO ( ^{1 )} .

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

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

الغطاء الرأسي الجزئي هو دالة تُسند وزنًا في الفترة [0,1] لكل رأس في V ، بحيث يكون مجموع كسور الرؤوس في كل حافة فائقة e في E أكبر من أو يساوي 1. الغطاء الرأسي هو حالة خاصة من الغطاء الرأسي الجزئي حيث تكون جميع الأوزان إما 0 أو 1. حجم الغطاء الرأسي الجزئي هو مجموع كسور جميع الرؤوس.

يُعرف عدد تغطية الرؤوس الجزئية للرسم البياني الفائق H بأنه أصغر حجم لتغطية الرؤوس الجزئية في H. وغالبًا ما يُرمز إليه بـ τ *( H ) .

بما أن غطاء الرؤوس هو حالة خاصة من غطاء الرؤوس الجزئي، فإنه لكل رسم بياني فائق H :

عدد تغطية الرؤوس الجزئي ( H ) ≤ عدد تغطية الرؤوس ( H )؛

بالرموز:

${\displaystyle \tau ^{*}(H)\leq \tau (H).}$

يكون عدد تغطية الرؤوس الجزئي للرسم البياني الفائق، بشكل عام، أصغر من عدد تغطية الرؤوس. وتقدم نظرية لازلو لوفاس حدًا أعلى للنسبة بينهما: ^{[ 7 ]}

• إذا كان كل رأس موجودًا في d حافة فائقة على الأكثر (أي أن درجة الرسم البياني الفائق هي d على الأكثر )، فإن

  ${\displaystyle {\frac {\tau (H)}{\tau ^{*}(H)}}\leq 1+\ln(d).}$

المستوى الإسقاطي المنتهي هو رسم بياني فائق يتقاطع فيه كل ضلعين فائقين. كل مستوى إسقاطي منتهٍ يكون منتظمًا من الدرجة r لعدد صحيح r . نرمز بـ H _{_r} إلى المستوى الإسقاطي المنتظم من الدرجة r . من المعروف وجود المستويات الإسقاطية التالية:

• H ₂ : إنه ببساطة رسم بياني مثلثي.
• H ₃ : إنها مستوى فانو .
• H _{p +1} موجود عندمايكون p قوة لعدد أولي .

عندما يكون H _r موجودًا، فإنه يتمتع بالخصائص التالية: ^{[ 8 ]}

• يحتوي على r ² – r + 1 رأسًا و r ² – r + 1 حافة فائقة.
• إنها منتظمة من الدرجة r - كل حافة فائقة تحتوي على r رأس بالضبط.
• إنها منتظمة من النوع r - كل رأس موجود في r حافة فائقة بالضبط.
• τ ( H _r ) = r : الرؤوس r في كل حافة فائقة e هي غطاء رأس لـ H _r (لأن كل حافة فائقة أخرى تتقاطع مع e ).
• إن المستعرضات الوحيدة ذات الحجم r هي الحواف الفائقة؛ أما جميع المستعرضات الأخرى فلها حجم لا يقل عن r + 2 .
• τ *( H _r ) = ν *( H ) = r – 1 + ⁠ 1 / r ⁠ .
• ν ( H _r ) = 1 : كل تطابق في H _r يحتوي على حافة فائقة واحدة على الأكثر.

يُطلق على غطاء الرؤوس (المستعرض) T اسم الحد الأدنى إذا لم تكن أي مجموعة فرعية مناسبة من T مستعرضة.

الرسم البياني الفائق المستعرض لـ H هو الرسم البياني الفائق ( X ، F ) الذي تتكون مجموعة حوافه الفائقة F من جميع المستعرضات الدنيا لـ H.

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

• المطابقة في الرسوم البيانية الفائقة - يناقش أيضًا الازدواجية بين تغطية الرؤوس والمطابقة.