البيان: المجموعة المهيمنة

افترض أننا نضع صرّافًا آليًا في بعض تقاطعات مدينة. يجب أن يكون في كل تقاطع صرّاف، أو أن يصل منه الناس إلى تقاطع مجاور فيه صرّاف. ننمذج المسألة ببيان: التقاطعات رؤوس والشوارع أضلاع. الرأس الذي في المجموعة «يهيمن» على نفسه وعلى جيرانه.

تكون مجموعة من الرؤوس «مهيمنة» إذا كان كل رأس في البيان إما في المجموعة وإما مجاورًا لأحد رؤوسها. وأقل عدد من الرؤوس يلزم لمجموعة مهيمنة يسمّى «عدد الهيمنة» ويُرمز إليه بـγ(G)؛ والمجموعة التي لها هذا العدد «مهيمنة صغرى». هذا الموضوع ليس في الكتب السورية، لكنه مفيد لفهم البيانات وشبكات التغطية.

«غير القابلة للتصغير» تختلف عن «الصغرى». غير القابلة للتصغير تعني أنه إذا أزلنا أي رأس منها لم تعد مهيمنة؛ والصغرى تعني أن لها أقل عدد من الرؤوس. كل رأس يهيمن على Δ + ١ رأسًا على الأكثر (Δ هي أكبر درجة)، فلعدد n من الرؤوس يلزم على الأقل السقف لـn مقسومًا على Δ + ١. السقف يعني التقريب إلى الأعلى.