مسألة القطع الأدنى

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

تعريفات

بصفة عامة هذه المسألة تعتبر تجزئة مجموعة رؤوس البيان إلى مجموعتين فرعيتين أو أكثر.

القطع أو القص عبارة عن تقسيم مجموعة رؤوس البيان إلى مجموعتين فرعيتين منفصلتين. و يعرّف القص بمجموعة من الحواف التي لها طرف في كل مجموعة فرعية ناتجة عن التقسيم ، و المفروض أن تكون هاتان المجموعتان متصلتين بحافة واحدة على الأقل.

تنويعات إشكالية القصّ لأدنى

مسألة التواصل عبر k-حافة

إذا ظل البيان متصلاً كلما تمّت إزالة أقلّ من k حواف ، يعرّف تواصل الحواف للبيان بأكبر k حيث يكون البيان متواصلا عبر k-حافة.

القص الأدنى بين منبع و حوض

من الممكن حساب القطع الذي يفصل زوجا معيّنا من الرؤوس في بيان موجّه ومقيّم ، يشار إليهما عادة المنبع s و البئرأو الحوض t. يقلّل القص الأدنى بين المنبع والحوض من الثقل الكلي على الحواف التي يتم توجيهها من جانبي القطع.

في حالة البيان الغير مقيّم ، يحدّد القص الأدنى أعلى عدد الطرق المستقلة التي يمكن سلكها من s إلى t.

شجرة جوموري-هو

إنّ شجرة جوموري-هو تسمح تمثيل القطع الدنيا التي توجد بين لجميع أزواج s-t ممكنة في البيان.

التوازن بين المجموعتين

مع إضافة قيود لتحقيق التوازن بين عدد الرؤوس في الجانبين من القطع ، لقيت مسألة القص الأدنى تطبيقا عمليا جدّ مروّجا في مسألة وضع المكونات في التصميم الإلكتروني.

الخوارزميات

تعتبر خوارزمية كارجر أفضل طريقة لحل هذه المسألة وهي تسمح العثور على القطع الأدنى في زمن كثير الحدود