مسألة القطع الأدنى
في نظرية البيانات ، مسألة القطع الأدنى أو القص الأدنى تتعلق في إيجاد أقل عدد من الحواف التي تربط بين مجموعتين جزئيتين منفصلتين من الرؤوس. في حالة البيانات المقيّمة غالبا ما يقاس القص الأدنى بالمجموع التراكمي لأثقال هذه الحواف.
تعريفات[عدل]
بصفة عامة هذه المسألة تعتبر تجزئة مجموعة رؤوس البيان إلى مجموعتين فرعيتين أو أكثر.
القطع أو القص عبارة عن تقسيم مجموعة رؤوس البيان إلى مجموعتين فرعيتين منفصلتين. و يعرّف القص بمجموعة من الحواف التي لها طرف في كل مجموعة فرعية ناتجة عن التقسيم ، و المفروض أن تكون هاتان المجموعتان متصلتين بحافة واحدة على الأقل.
تنويعات إشكالية القصّ لأدنى[عدل]
مسألة التواصل عبر k-حافة[عدل]
إذا ظل البيان متصلاً كلما تمّت إزالة أقلّ من k حواف ، يعرّف تواصل الحواف للبيان بأكبر k حيث يكون البيان متواصلا عبر k-حافة.
القص الأدنى بين منبع و حوض[عدل]
من الممكن حساب القطع الذي يفصل زوجا معيّنا من الرؤوس في بيان موجّه ومقيّم ، يشار إليهما عادة المنبع s و البئرأو الحوض t. يقلّل القص الأدنى بين المنبع والحوض من الثقل الكلي على الحواف التي يتم توجيهها من جانبي القطع.
في حالة البيان الغير مقيّم ، يحدّد القص الأدنى أعلى عدد الطرق المستقلة التي يمكن سلكها من s إلى t.
شجرة جوموري-هو[عدل]
إنّ شجرة جوموري-هو تسمح تمثيل القطع الدنيا التي توجد بين لجميع أزواج s-t ممكنة في البيان.
التوازن بين المجموعتين[عدل]
مع إضافة قيود لتحقيق التوازن بين عدد الرؤوس في الجانبين من القطع ، لقيت مسألة القص الأدنى تطبيقا عمليا جدّ مروّجا في مسألة وضع المكونات في التصميم الإلكتروني.
الخوارزميات[عدل]
تعتبر خوارزمية كارجر[1] أفضل طريقة لحل هذه المسألة وهي تسمح العثور على القطع الأدنى في زمن كثير الحدود
مراجع[عدل]
- ^ KARGER, David R. Global Min-cuts in RNC, and Other Ramifications of a Simple Min-Cut Algorithm. In : SODA. 1993. p. 21-30.
