القطع (نظرية الرسم البياني)

في نظرية المخططات ، ^{يُعرَّف} القطع بأنه تقسيم رؤوس المخطط إلى مجموعتين فرعيتين منفصلتين . ^{[ 1} ] يُحدد أي قطع مجموعة قطع ، وهي مجموعة الحواف التي لها نقطة نهاية واحدة في كل مجموعة فرعية من التقسيم. تُسمى هذه الحواف التي تعبر القطع. في المخطط المتصل ، تُحدد كل مجموعة قطع قطعًا فريدًا، وفي بعض الحالات، تُعرَّف القطع بمجموعات القطع الخاصة بها بدلًا من تقسيمات رؤوسها.

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

القطع C = ( S , T ) هو تقسيم للرسم البياني V من الرسم البياني G = ( V , E ) إلى مجموعتين جزئيتين S و T. مجموعة القطع للقطع C = ( S , T ) هي مجموعة {( u , v ) ∈ E | u ∈ S , v ∈ T } من الحواف التي لها طرف في S وطرف آخر في T. إذا كان s و t رأسين محددين في الرسم البياني G ، فإن القطع s – t هو قطع ينتمي فيه s إلى المجموعة S وينتمي فيه t إلى المجموعة T.

في الرسم البياني غير الموجه وغير الموزون، يُعرَّف حجم أو وزن القطع بعدد الحواف التي تعبره. أما في الرسم البياني الموزون ، فيُعرَّف حجم أو وزن القطع بمجموع أوزان الحواف التي تعبره.

الرابط هو مجموعة قطع لا تحتوي على أي مجموعة قطع أخرى كمجموعة فرعية مناسبة .

يُعتبر القطع أدنى ما يمكن إذا لم يتجاوز حجمه أو وزنه حجم أي قطع آخر. يوضح الرسم التوضيحي على اليمين قطعًا أدنى ما يمكن: حجم هذا القطع هو 2، ولا يوجد قطع بحجم 1 لأن الرسم البياني لا يحتوي على جسور .

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

يكون القطع أقصى ما يمكن إذا لم يكن حجمه أصغر من حجم أي قطع آخر. يوضح الرسم التوضيحي على اليمين قطعًا أقصى ما يمكن: حجم القطع يساوي 5، ولا يوجد قطع بحجم 6، أو | E | (عدد الحواف)، لأن الرسم البياني ليس ثنائي الأجزاء (يوجد دورة فردية ).

بشكل عام، يُعدّ إيجاد القطع الأقصى أمرًا صعبًا حسابيًا. ^{[ 3 ]} تُصنّف مسألة القطع الأقصى ضمن مسائل كارب الـ 21 الكاملة من فئة NP . ^{[ 4 ]} كما تُصنّف مسألة القطع الأقصى ضمن فئة APX-hard ، ما يعني أنه لا توجد طريقة تقريبية لها في زمن متعدد الحدود إلا إذا كانت P  =  NP . ^{[ 5 ]} مع ذلك، يُمكن تقريبها بنسبة تقريب ثابتة باستخدام البرمجة شبه المحددة . ^{[ 6 ]}

تجدر الإشارة إلى أن مسألتي القطع الأدنى والقطع الأقصى ليستا مسألتين متقابلتين بالمعنى المتعارف عليه في البرمجة الخطية ، على الرغم من إمكانية الانتقال من إحداهما إلى الأخرى بتغيير الحد الأدنى إلى الحد الأقصى في دالة الهدف . وتُعد مسألة التدفق الأقصى المسألة المقابلة لمسألة القطع الأدنى . ^{[ 7 ]}

تتمثل مشكلة القطع الأقل كثافة في تقسيم الرؤوس إلى نصفين بحيث يتم تقليل نسبة عدد الحواف التي تعبر القطع إلى عدد الرؤوس في النصف الأصغر من التقسيم. تُفضل دالة الهدف هذه الحلول التي تتسم بالكثافة (عدد قليل من الحواف التي تعبر القطع) والتوازن (قريبة من التقسيم الثنائي). من المعروف أن هذه المشكلة صعبة الحل (NP-hard)، وأفضل خوارزمية تقريب معروفة هي...${\displaystyle O({\sqrt {\log n}})}$التقريب بسبب أرورا، راو وفازيراني (2009) . ^{[ 8 ]}

تُعرف عائلة جميع مجموعات القطع في الرسم البياني غير الموجه باسم فضاء القطع للرسم البياني. وهو يُشكل فضاءً متجهيًا على الحقل المنتهي ذي العنصرين في الحساب بتردد اثنين، حيث يُمثل الفرق المتناظر بين مجموعتي قطع عملية جمع متجهية، وهو المتمم المتعامد لفضاء الدورات . ^{[ 9 ] [ 10 ]} إذا أُعطيت حواف الرسم البياني أوزانًا موجبة، فيمكن وصف أساس الوزن الأدنى لفضاء القطع بشجرة على نفس مجموعة رؤوس الرسم البياني، تُسمى شجرة جوموري-هو . ^{[ 11 ]} ترتبط كل حافة من حواف هذه الشجرة برابطة في الرسم البياني الأصلي، والقطع الأدنى بين عقدتين s و t هو رابطة الوزن الأدنى بين الروابط المرتبطة بالمسار من s إلى t في الشجرة.

• الاتصال (نظرية الرسم البياني)
• قطع الرسوم البيانية في رؤية الكمبيوتر
• الانقسام (نظرية الرسم البياني)
• فاصل الرؤوس
• الجسر (نظرية الرسم البياني)
• عرض القطع
• مقطع