الگوریتم استور- واگنر کیست؟ توضیح بده.
الگوریتم استور-واگنر یک الگوریتم بازگشتی برای حل مسئله برش کمینه در گراف‌های وزن‌دار بدون جهت با وزن‌های نامنفی است. این الگوریتم در سال ۱۹۹۵ توسط مکتیلد استور و فرانک واگنر پیشنهاد داده شد. همبندی گراف یکی از موضوعات کلاسیک در نظریه گراف‌ها می‌باشد و استفاده‌های کاربردی بسیاری مانند طراحی تراشه و مدار، قابل اعتماد بودن شبکات ارتباطی، برنامه‌ریزی حمل و نقل و خوشه بندی دارد. پیدا کردن برش کمینه یک گراف وزن‌دار یه مسئله اساسی الگوریتمی است. به‌طور دقیق این کار شامل پیدا کردن دو بخش مجزا از گراف بطوری که جمع وزن یال‌هایی که این دو بخش را به هم متصل می‌کنند کمینه شود می‌باشد.برش کمینه در یک گراف از موضوعات بسیار مهم در زمینه بهینه‌سازی شبکه است. برش، برداشتن شماری از یال‌های یک گراف همبند است، به گونه‌ای که گراف را به دو بخش ناهمبند تبدیل کند. حال اگر وزن هر یال هزینه برداشتن آن یال در نظر گرفته شود، برش کمینه برشی است که جمع هزینه ایجاد آن کمینه شود.الگوریتم.فرض کنید formula_1 یک گراف ساده وزن‌دار با وزن‌های نامنفی است. یک برش formula_2 از گراف formula_3 یک زیرمجموعه ناتهی و ناسره از formula_4 است. وزن یک برش در واقع جمع وزن یال‌هایی است که از آن برش عبور می‌کنند.الگوریتم استور-واگنر از تکرار فازهای مشابه تشکیل شده‌است. این الگوریتم در هر فاز ۲ راس از گراف مانند formula_5 و formula_6 را در نظر می‌گیرد و برش کمینه متناظر با این ۲ راس مانند برش formula_2 را بدست می‌آورد. برش کمینه متناظر با ۲ راس، برشی است که حتماً شامل تنها یکی از آن ۲ راس باشد. حال اگر برشی کمینه از formula_3 وجود داشته باشد که ۲ رأس formula_5 و formula_6 را از هم جدا کند آنگاه برش formula_2 برش کمینه گراف formula_3 است. در غیر این صورت هر برش کمینه از گراف formula_3 آن را بطوری تقسیم می‌کند که ۲ رأس formula_5 و formula_6 در یک بخش می‌افتند. در نتیجه در این حالت اگر ۲ راس formula_5 و formula_6 را با یکدیگر ادغام کنیم و راسی جدید بجای آن دو بگذاریم گراف حاصل بعد از ادغام این ۲ راس، برشی کمینه مشابه برش کمینه گراف formula_3 قبل از ادغام خواهد داشت. پس در هر فاز یک ادغام اتفاق می‌افتد و بعد از formula_19 فاز گراف به یک راس تبدیل می‌شود. کم وزن‌ترین برش کمینه در بین برش‌های کمینه هر فاز برش کمینه گراف formula_3 می‌باشد.هر یک از فازهای الگوریتم استور-واگنر به الگوریتم پریم شباهت زیادی دارد. formula_22 while formula_23 add to formula_24 the most tightly connected vertex store the cut-of-the-phase and shrink formula_3 by merging the two vertices added lastابتدا یک زیر مجموعه از راس‌های گراف مانند formula_24 را که در ابتدا تنها شامل ۱ راس دلخواه از گراف است را در نظر می‌گیریم. در هر مرحله راسی خارج از formula_24 را که مجموعه وزن یال‌هایی که آن‌را به formula_24 متصل کرده‌است بیشینه است، به formula_24 اضافه می‌کنیم و این کار را تا جایی ادامه می‌دهیم که formula_30. در انتهای فاز آخرین ۲ راسی که باقی مانده‌اند را با یکدیگر ادغام می‌کنیم و رأس جدید بجای آن دو می‌گذاریم. هر یالی که از این ۲ راس به راس‌های دیگر متصل است را با یک یال با وزنی معادل مجموع وزن ۲ یال پیشین جایگزین می‌کنیم. while formula_32 MinimumCutPhaseformula_21 if the cut-of-the-phase is lighter than the current minimum cut then store the cut-of-the-phase as the current minimum cutبرشی از formula_4 که در انتهای فاز، آخرین رأس باقی‌مانده را از بقیه گراف جدا می‌کند برش کمینه فاز نامیده می‌شود. بعد از اینکه formula_19 بار برش کمینه فاز بدست آمد، کمترین مقدار از این formula_19 مقدار برش کمینه گراف formula_3 است.زمان اجرا.زمان اجرای الگوریتم برش کمینه، در واقع زمان اجرای formula_19 بار MinimumCutPhase است. زمان اجرای MinimumCutPhase حداکثر از formula_39 است. در نتیجه زمان اجرای کل الگوریتم از formula_40 بدست می‌آید. انتخاب کردن رأس بعدی که باید به مجموعه formula_24 اضافه شود می‌تواند در زمان اجرای الگوریتم تأثیر زیادی داشته باشد. برای بهینه کردن الگوریتم و آسان شدن پیدا کردن رأس مورد نظر در هر مرحله، در طول اجرای هر فاز همه راس‌هایی که در مجموعه formula_24نیستند، درون یک صف اولویت درج می‌شوند. کلیدformula_43 هر راس از formula_4 مجموع وزن همه یال‌هایی است که آن راس را به مجموعه formula_24 متصل می‌کنند. هر بار که یک راس formula_43 به formula_24 اضافه می‌شود باید صف اولویت به‌روزرسانی شود. در به‌روزرسانی، راس formula_43 را از صف حذف می‌کنیم و برای همه راس‌هایی که در formula_24 نیستند کلید را به اندازه وزن یال بین آن راس و formula_43 در صورت وجود چنین یالی، زیاد می‌کنیم. این عمل هر بار با زمان سرشکن formula_51، formula_52 بار اجرا می‌شود. از طرفی پیدا کردن کلید بیشینه به کمک هیپ فیبوناتچی با زمان سرشکن formula_53، formula_54 بار تکرار می‌شود. پس زمان اجرای مرحله پیدا کردن رأس مناسب برای اضافه کردن به formula_24 حداکثر از formula_56 است.کد الگوریتم.// Adjacency matrix implementation of Stoer–Wagner min cut algorithm.// Running time:// O(|V|^3)// INPUT: // - graph, constructed using AddEdge()// OUTPUT:// - (min cut value, nodes in half of min cut)using namespace std;typedef vector&lt;int&gt; VI;typedef vector&lt;VI&gt; VVI;const int INF = 1000000000;pair&lt;int, VI&gt; GetMinCut(VVI &amp;weights) int N = weights.size(); VI used(N), cut, best_cut; int best_weight = -1; for (int phase = N-1; phase&gt;= 0; phase--) VI w = weights[0]; VI added = used; int prev, last = 0; for (int i = 0; i &lt;phase; i++) prev = last; last = -1; for (int j = 1; j &lt;N; j++) if (!added[j] &amp;&amp; (last == -1 || w[j]&gt; w[last])) last = j; if (i == phase-1) for (int j = 0; j &lt;N; j++) weights[prev][j] += weights[last][j]; for (int j = 0; j &lt;N; j++) weights[j][prev] = weights[prev][j]; used[last] = true; cut.push_back(last); if (best_weight == -1 || w[last] &lt;best_weight) best_cut = cut; best_weight = w[last]; else for (int j = 0; j &lt;N; j++) w[j] += weights[last][j]; added[last] = true; return make_pair(best_weight, best_cut);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 &amp;s, int &amp;t ) // Find s,t memset(dist, 0, sizeof(dist)); memset(vis, false, sizeof(vis)); int i, j, k, mincut, maxc; for(i = 1; i &lt;= n; i++) k = -1; maxc = -1; for(j = 1; j &lt;= n; j++)if(!bin[j] &amp;&amp; !vis[j] &amp;&amp; dist[j]&gt; maxc) k = j; maxc = dist[j]; if(k == -1)return mincut; s = t; t = k; mincut = maxc; vis[k] = true; for(j = 1; j &lt;= n; j++)if(!bin[j] &amp;&amp; !vis[j]) dist[j] += edge[k][j]; return mincut; int Stoer_Wagner() int mincut, i, j, s, t, ans; for(mincut = inf, i = 1; i &lt;n; i++) ans = contract( s, t ); bin[t] = true; if(mincut&gt; ans)mincut = ans; if(mincut == 0)return 0; for(j = 1; j &lt;= n; j++)if(!bin[j]) edge[s][j] = (edge[j][s] += edge[j][t]); return mincut;