مسألة القطع الأدنى
المحتويات

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