خوارزمية ستوير-فاغنر

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

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

يترك${\displaystyle G=(V,E,w)}$ليكن رسمًا بيانيًا غير موجه وموزونًا. لنفترض أن${\displaystyle s,t\in V}$يُطلق على هذا القطع اسم${\displaystyle s}$-${\displaystyle t}$يُقطع إذا كان واحد فقط من${\displaystyle s}$أو${\displaystyle t}$هو في${\displaystyle S}$الحد الأدنى من القطع${\displaystyle G}$هذا أيضًا${\displaystyle s}$-${\displaystyle t}$يُطلق على القطع اسم${\displaystyle s}$-${\displaystyle t}$الحد الأدنى للقطع من${\displaystyle G}$[ ^{3 ]​}

تبدأ هذه الخوارزمية بإيجاد${\displaystyle s}$و أ${\displaystyle t}$في${\displaystyle V}$، وقصة قصيرة${\displaystyle (S,T)}$ل${\displaystyle G}$لأي زوج${\displaystyle \left\{s,t\right\}}$هناك حالتان محتملتان: إما${\displaystyle (S,T)}$هو الحد الأدنى العالمي لـ${\displaystyle G}$، أو${\displaystyle s}$و${\displaystyle t}$ينتمي إلى نفس جانب القطع الأدنى العالمي لـ${\displaystyle G}$لذلك، يمكن إيجاد القطع الأدنى العالمي عن طريق فحص الرسم البياني.${\displaystyle G\cup \{st\}/\left\{s,t\right\}}$وهو الرسم البياني بعد دمج الرؤوس${\displaystyle s}$و${\displaystyle t}$إلى رأس جديد${\displaystyle st}$أثناء عملية الدمج، إذا${\displaystyle s}$و${\displaystyle t}$إذا كانت هناك علاقة بين عنصرين، فإن هذه العلاقة تختفي.${\displaystyle s}$و${\displaystyle t}$كلاهما له حواف إلى رأس ما${\displaystyle v}$ثم وزن الحافة من الرأس الجديد${\displaystyle st}$ل${\displaystyle v}$يكون${\displaystyle w(s,v)+w(t,v)}$[ ^{3 ]} يتم وصف الخوارزمية على النحو التالي ^{: [ 2 ]}

مرحلة القطع الدنيا${\displaystyle (G,w,a)}$${\displaystyle A\gets \left\{a\right\}}$بينما${\displaystyle \ A\neq V}$ اضف إليه${\displaystyle A}$الطرف الأكثر اتصالاً بالرأس  قم بتخزين القطع الذي يكون فيه الرأس الأخير المتبقي بمفرده (قطع المرحلة). تقلص${\displaystyle G}$عن طريق دمج الرأسين (s, t) المضافين أخيرًا (قيمة "قطع الطور" هي قيمة الحد الأدنى لقطع s, t). الحد الأدنى للقطع${\displaystyle (G,w,a)}$بينما${\displaystyle |V|>1}$مرحلة القطع الدنيا${\displaystyle (G,w,a)}$إذا كان قطع الطور أخف من الحد الأدنى الحالي للقطع، فقم بتخزين قطع الطور كحد أدنى حالي للقطع

تعمل الخوارزمية على مراحل. في مرحلة القطع الأدنى، المجموعة الفرعية${\displaystyle A}$ينمو عدد رؤوس الرسم البياني بدءًا من رأس واحد عشوائي حتى${\displaystyle A}$يساوي${\displaystyle V}$في كل خطوة، يتم تحديد الرأس الذي يقع خارج${\displaystyle A}$لكنها مرتبطة ارتباطًا وثيقًا بـ${\displaystyle A}$تمت إضافته إلى المجموعة${\displaystyle A}$يمكن تمثيل هذا الإجراء رسميًا على النحو التالي: ^{[ 2 ]} إضافة رأس${\displaystyle z\notin A}$بحيث${\displaystyle w(A,z)=\max\{w(A,y)\mid y\notin A\}}$، أين${\displaystyle w(A,y)}$هو مجموع أوزان جميع الحواف بين${\displaystyle A}$و${\displaystyle y}$لذا، في مرحلة واحدة، زوج من الرؤوس${\displaystyle s}$و${\displaystyle t}$، و دقيقة${\displaystyle s{\text{-}}t}$يقطع${\displaystyle C}$يتم تحديده. ^{[ 4 ]} بعد مرحلة واحدة من مرحلة القطع الأدنى، يتم دمج الرأسين لتكوين رأس جديد، ويتم استبدال الحواف من الرأسين إلى الرأس المتبقي بحافة موزونة بمجموع أوزان الحافتين السابقتين. تُزال الحواف التي تربط العقد المدمجة. إذا كان هناك قطع أدنى لـ${\displaystyle G}$الفصل${\displaystyle s}$و${\displaystyle t}$، ال${\displaystyle C}$الحد الأدنى للقطع${\displaystyle G}$وإلا، فإن الحد الأدنى للقطع هو${\displaystyle G}$لا غنى عنه${\displaystyle s}$و${\displaystyle t}$على نفس الجانب. لذلك، ستدمج الخوارزمية العقدتين كعقدة واحدة. بالإضافة إلى ذلك، ستسجل دالة MinimumCut وتُحدّث الحد الأدنى العالمي للقطع بعد كل مرحلة من مراحل MinimumCutPhase. بعد ذلك${\displaystyle n-1}$في المراحل، يمكن تحديد الحد الأدنى للقطع . ^{[ 4 ]}

لإثبات صحة هذه الخوارزمية، نحتاج إلى إثبات أن القطع الذي تحدده دالة MinimumCutPhase هو في الواقع قيمة دنيا.${\displaystyle s{\text{-}}t}$مقطع من الرسم البياني، حيث يمثل s و t الرأسين اللذين تمت إضافتهما آخر مرة في المرحلة. لذلك، تظهر اللمة أدناه:

اللمة 1 : تُعيد دالة MinimumCutPhase قيمة دنيا${\displaystyle s{\text{-}}t}$-مقتطف من${\displaystyle G}$.

يترك${\displaystyle C=(X,{\overline {X}})}$كن تعسفيًا${\displaystyle s{\text{-}}t}$قطع، و${\displaystyle CP}$ليكن القطع المحدد بواسطة الطور. يجب أن نبين ذلك.${\displaystyle W(C)\geq W(CP)}$لاحظ أن تشغيلًا واحدًا لـ MinimumCutPhase يعطينا ترتيبًا لجميع الرؤوس في الرسم البياني (حيث${\displaystyle a}$هو الأول و${\displaystyle s}$و${\displaystyle t}$(هما الرأسان اللذان تمت إضافتهما أخيرًا في المرحلة). نقول الرأس${\displaystyle v}$يكون نشطًا إذا${\displaystyle v}$والرأس المضاف قبل ذلك مباشرة${\displaystyle v}$تقع هذه الرؤوس على جانبين متقابلين من القطع. نبرهن على اللمة بالاستقراء على مجموعة الرؤوس النشطة. نُعرّف${\displaystyle A_{v}}$باعتبارها مجموعة الرؤوس المضافة إلى${\displaystyle A}$قبل${\displaystyle v}$، و${\displaystyle C_{v}}$أن تكون مجموعة الحواف في${\displaystyle C}$مع وجود طرفيهما في${\displaystyle A_{v}\cup \{v\}}$، أي${\displaystyle C_{v}\subseteq C}$هل القطع ناتج عن${\displaystyle A_{v}\cup \{v\}}$نثبت، لكل رأس نشط${\displaystyle v}$،

${\displaystyle w(A_{v},v)\leq w(C_{v})}$

يترك${\displaystyle v_{0}}$ليكن الرأس النشط الأول. بحسب تعريف هاتين الكميتين،${\displaystyle w(A_{v_{0}},v_{0})}$و${\displaystyle w(C_{v_{0}})}$متكافئان.${\displaystyle A_{v_{0}}}$هي ببساطة جميع الرؤوس المضافة إلى${\displaystyle A}$قبل${\displaystyle v_{0}}$والحواف بين هذه الرؤوس و${\displaystyle v_{0}}$هي الحواف التي تعبر القطع${\displaystyle C}$لذلك، كما هو موضح أعلاه، بالنسبة للرؤوس النشطة${\displaystyle v}$و${\displaystyle u}$، مع${\displaystyle v}$تمت إضافته إلى${\displaystyle A}$قبل${\displaystyle u}$:

${\displaystyle w(A_{u},u)=w(A_{v},u)+w(A_{u}-A_{v},u)}$

${\displaystyle w(A_{u},u)\leq w(C_{v})+w(A_{u}-A_{v},u)}$بالحث،${\displaystyle w(A_{v},u)\leq w(A_{v},v)\leq w(C_{v})}$

${\displaystyle w(A_{u},u)\leq w(C_{u})}$منذ${\displaystyle w(A_{u}-A_{v},u)}$يساهم في${\displaystyle w(C_{u})}$لكن ليس لـ${\displaystyle w(C_{v})}$(والحواف الأخرى ذات أوزان غير سالبة)

وبالتالي، بما أن${\displaystyle t}$هو دائمًا رأس نشط لأن القطع الأخير من الطور يفصل${\displaystyle s}$من${\displaystyle t}$بحسب التعريف، لأي رأس نشط${\displaystyle t}$:

${\displaystyle w(A_{t},t)\leq w(C_{t})=w(C)}$

لذلك، فإن قطع الطور يكون على الأكثر ثقيلاً مثل${\displaystyle C}$.

زمن تشغيل خوارزمية MinimumCut يساوي مجموع زمن تشغيل خوارزمية${\displaystyle |V|-1}$تشغيل MinimumCutPhase ، والتي يتم استدعاؤها على الرسوم البيانية ذات عدد متناقص من الرؤوس والحواف.

بالنسبة لمرحلة القطع الأدنى ، فإن تشغيلها مرة واحدة يحتاج على الأكثر${\displaystyle O(|E|+|V|\log |V|)}$وقت.

لذلك، ينبغي أن يكون إجمالي وقت التشغيل ناتجًا عن تعقيد المرحلتين، وهو${\displaystyle O(|V||E|+|V|^{2}\log |V|)}$[ ^{2 ]​}

لتحقيق مزيد من التحسين، يكمن المفتاح في تسهيل اختيار الرأس التالي المراد إضافته إلى المجموعة.${\displaystyle A}$، الرأس الأكثر اتصالاً. أثناء تنفيذ مرحلة ما، يتم نقل جميع الرؤوس التي ليست في${\displaystyle A}$تتواجد في قائمة انتظار ذات أولوية بناءً على حقل مفتاح. مفتاح رأس${\displaystyle V}$هو مجموع أوزان الحواف التي تربطه بالتيار الحالي${\displaystyle A}$، إنه،${\displaystyle w(A,v)}$كلما كان هناك رأس${\displaystyle v}$يُضاف إلى${\displaystyle A}$علينا إجراء تحديث لقائمة الانتظار.${\displaystyle v}$يجب حذفها من قائمة الانتظار، ومفتاح كل رأس${\displaystyle w}$ليس في${\displaystyle A}$، متصلة بـ${\displaystyle v}$يجب زيادتها بوزن الحافة${\displaystyle vw}$إن وُجد. وبما أن هذا يتم مرة واحدة فقط لكل حافة، فإجمالاً علينا أن ننفذ${\displaystyle |V|}$استخراج أقصى قدر من البيانات${\displaystyle |E|}$عمليات زيادة المفتاح. باستخدام كومة فيبوناتشي، يمكننا إجراء عملية استخراج القيمة القصوى في${\displaystyle O(\log |V|)}$الوقت المستهلك وعملية زيادة المفتاح في${\displaystyle O(1)}$الوقت المستهلك. وبالتالي، فإن الوقت الذي نحتاجه لهذه الخطوة الرئيسية التي تهيمن على بقية المرحلة هو${\displaystyle O(|E|+|V|\log |V|)}$[ ^{2 ]​}

فيما يلي تطبيق موجز لخوارزمية ستوير-فاغنر بلغة C++ . ^{[ 5 ]}

// تطبيق مصفوفة التجاور لخوارزمية ستوير-فاغنر للقطع الأدنى. // // زمن التشغيل: // O(|V|^3)#include <bits/stdc++.h> using namespace std ;زوج < عدد صحيح ، متجه < عدد صحيح >> globalMinCut ( متجه < متجه < عدد صحيح >> mat ) { زوج < عدد صحيح ، متجه < عدد صحيح >> best = { INT_MAX ، {}}; عدد صحيح n = mat . size (); متجه < متجه < عدد صحيح >> co ( n );for ( int i = 0 ; i < n ; i ++ ) co [ i ] = { i };for ( int ph = 1 ; ph < n ; ph ++ ) { vector <int> w = mat [ 0 ]; size_t s = 0, t = 0; for (int it = 0; it < n - ph ; it ++ ) { // O ( V ^ 2 ) - > O ( E log V ) مع قائمة انتظار ذات أولوية w [ t ] = INT_MIN ; s = t , t = max_element ( w.begin ( ) , w.end ( ) ) - w.begin ( ); for ( int i = 0 ; i < n ; i ++ ) w [ i ] += mat [ t ][ i ] ; } best = min ( best , { w [ t ] - mat [ t ] [ t ], co [ t ]}); co [ s ] . أضف ( نهاية العنصر s ، بداية العنصر t ، نهاية العنصر t ) ؛ ثم ، من أجل ( عدد صحيح i = 0 ؛ i < n ؛ i ++ ) ، أضف العنصر t إلى العنصر s ؛ ثم ، من أجل ( عدد صحيح i = 0 ؛ i < n ؛ i ++ ) ، اجعل العنصر s يساوي العنصر t .​​[ s ][ i ]; mat [ 0 ][ t ] = INT_MIN ; }أعد الأفضل ؛ }

const int maxn = 550 ; const int inf = 1000000000 ; int n , r ; int edge [ maxn ][ maxn ], dist [ maxn ]; bool vis [ maxn ], bin [ maxn ];void init () { memset ( edge , 0 , sizeof ( edge )); memset ( bin , false , sizeof ( bin )); }int contract ( int & s , int & t ) // إيجاد s,t { memset ( dist , 0 , sizeof ( dist )); memset ( vis , false , sizeof ( vis )); int i , j , k , mincut , maxc ;for ( i = 1 ; i <= n ; i ++ ) { k = -1 ; maxc = -1 ; for ( j = 1 ; j <= n ; j ++ ) if ( ! bin [ j ] && ! vis [ j ] && dist [ j ] > maxc ) { k = j ; maxc = dist [ j ]; } if ( k == -1 ) return mincut ; s = t ; t = k ; mincut = maxc ; vis [ k ] = true ; for ( j = 1 ; j <= n ; j ++ ) if ( ! bin [ j ] && ! vis [ j ]) dist [ j ] += edge [ k ][ j ]; }أعد mincut ؛ }int Stoer_Wagner () { int mincut , i , j , s , t , ans ;for ( mincut = inf , i = 1 ; i < n ; i ++ ) { ans = contract ( s , t ); bin [ t ] = true ; if ( mincut > ans ) mincut = ans ; if ( mincut == 0 ) return 0 ; for ( j = 1 ; j <= n ; j ++ ) if ( ! bin [ j ]) edge [ s ][ j ] = ( edge [ j ][ s ] += edge [ j ][ t ]); }أعد mincut ؛ }

• StoerWagnerMinCut.java - مكتبة جافا تُنفذ خوارزمية ستوير-فاغنر