الگوریتم استور- واگنر

الگوریتم استور-واگنر یک الگوریتم بازگشتی برای حل مسئله برش کمینه در گراف‌های وزن‌دار بدون جهت با وزن‌های نامنفی است. این الگوریتم در سال ۱۹۹۵ توسط مکتیلد استور و فرانک واگنر پیشنهاد داده شد. همبندی گراف یکی از موضوعات کلاسیک در نظریه گراف‌ها می‌باشد و استفاده‌های کاربردی بسیاری مانند طراحی تراشه و مدار، قابل اعتماد بودن شبکات ارتباطی، برنامه‌ریزی حمل و نقل و خوشه بندی دارد. پیدا کردن برش کمینه یک گراف وزن‌دار یه مسئله اساسی الگوریتمی است. بطور دقیق این کار شامل پیدا کردن دو بخش مجزا از گراف بطوری که جمع وزن یال‌هایی که این دو بخش را به هم متصل می‌کنند کمینه شود می‌باشد.
برش کمینه در یک گراف از موضوعات بسیار مهم در زمینه بهینه‌سازی شبکه است. برش، برداشتن شماری از یال‌های یک گراف همبند است، به گونه‌ای که گراف را به دو بخش ناهمبند تبدیل کند. حال اگر وزن هر یال هزینه برداشتن آن یال درنظر گرفته شود، برش کمینه برشی است که جمع هزینه ایجاد آن کمینه شود.
الگوریتم
فرض کنید یک گراف ساده وزن‌دار با وزن‌های نامنفی است. یک برش از گراف یک زیرمجموعه ناتهی و ناسره از است. وزن یک برش در واقع جمع وزن یال‌هایی است که از آن برش عبور می‌کنند.
الگوریتم استور-واگنر از تکرار فازهای مشابه تشکیل شده است. این الگوریتم در هر فاز ۲ راس از گراف مانند و را در نظر می‌گیرد و برش کمینه متناظر با این ۲ راس مانند برش را بدست می‌آورد. برش کمینه متناظر با ۲ راس، برشی است که حتما شامل تنها یکی از آن ۲ راس باشد. حال اگر برشی کمینه از وجود داشته باشد که ۲ راس و را از هم جدا کند آنگاه برش برش کمینه گراف است. در غیر این صورت هر برش کمینه از گراف آن را بطوری تقسیم می‌کند که ۲ راس و در یک بخش می‌افتند. در نتیجه در این حالت اگر ۲ راس و را با یکدیگر ادغام کنیم و راسی جدید بجای آن دو بگذاریم گراف حاصل بعد از ادغام این ۲ راس، برشی کمینه مشابه برش کمینه گراف قبل از ادغام خواهد داشت. پس در هر فاز یک ادغام اتفاق می‌افتد و بعد از فاز گراف به یک راس تبدیل می‌شود. کم وزن‌ترین برش کمینه در بین برش‌های کمینه هر فاز برش کمینه گراف می‌باشد.
هر یک از فازهای الگوریتم استور-واگنر به الگوریتم پریم شباهت زیادی دارد.
MinimumCutPhase
while
add to the most tightly connected vertex
store the cut-of-the-phase and shrink by merging the two vertices added last
ابتدا یک زیر مجموعه از راس‌های گراف مانند را که در ابتدا تنها شامل ۱ راس دلخواه از گراف است را در نظر می‌گیریم. در هر مرحله راسی خارج از را که مجموعه وزن یال‌هایی که آن‌را به متصل کرده است بیشینه است، به اضافه می‌کنیم و این کار را تا جایی ادامه می‌دهیم که . در انتهای فاز آخرین ۲ راسی که باقی مانده‌اند را با یکدیگر ادغام می‌کنیم و راس جدید بجای آن دو می‌گذاریم. هر یالی که از این ۲ راس به راس‌های دیگر متصل است را با یک یال با وزنی معادل مجموع وزن ۲ یال پیشین جایگزین می‌کنیم.
MinimumCut
while
MinimumCutPhase
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
برشی از که در انتهای فاز، آخرین راس باقیمانده را از بقیه گراف جدا می‌کند برش کمینه فاز نامیده می‌شود. بعد از اینکه بار برش کمینه فاز بدست آمد، کمترین مقدار از این مقدار برش کمینه گراف است.
زمان اجرا
زمان اجرای الگوریتم برش کمینه، در واقع زمان اجرای بار MinimumCutPhase است. زمان اجرای MinimumCutPhase حداکثر از است. در نتیجه زمان اجرای کل الگوریتم از بدست می‌آید.
انتخاب کردن راس بعدی که باید به مجموعه اضافه شود می‌تواند در زمان اجرای الگوریتم تاثیر زیادی داشته باشد. برای بهینه کردن الگوریتم و آسان شدن پیدا کردن راس مورد نظر در هر مرحله، در طول اجرای هر فاز همه راس‌هایی که در مجموعه نیستند، درون یک صف اولویت درج می‌شوند. کلید هر راس از مجموع وزن همه یال‌هایی است که آن راس را به مجموعه متصل می‌کنند. هر بار که یک راس به اضافه می‌شود باید صف اولویت به‌روزرسانی شود. در به‌روزرسانی، راس را از صف حذف می‌کنیم و برای همه راس‌هایی که در نیستند کلید را به اندازه وزن یال بین آن راس و در صورت وجود چنین یالی، زیاد می‌کنیم. این عمل هر بار با زمان سرشکن ، بار اجرا می‌شود. از طرفی پیدا کردن کلید بیشینه به کمک هیپ فیبوناتچی با زمان سرشکن ، بار تکرار می‌شود. پس زمان اجرای مرحله پیدا کردن راس مناسب برای اضافه کردن به حداکثر از است.
کد الگوریتم
// 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)
include
include
include
using namespace std;
typedef vector VI;
typedef vector VVI;
const int INF = 1000000000;
pair GetMinCut(VVI -weights)
int N = weights.size();
VI used(N), cut, best_cut;
int best_weight = -1;
for (int phase = N-1; phase>= 0; phase--)
VI w = weights0;
VI added = used;
int prev, last = 0;
for (int i = 0; i <phase; i++)
prev = last;
last = -1;
for (int j = 1; j wlast)) last = j;
if (i == phase-1)
for (int j = 0; j <N; j++) weightsprevj += weightslastj;
for (int j = 0; j <N; j++) weightsjprev = weightsprevj;
usedlast = true;
cut.push_back(last);
if (best_weight == -1
wlast <best_weight)
best_cut = cut;
best_weight = wlast;
else
for (int j = 0; j <N; j++)
wj += weightslastj;
addedlast = true;
return make_pair(best_weight, best_cut);
const int maxn = 550;
const int inf = 1000000000;
int n, r;
int edgemaxnmaxn, distmaxn;
bool vismaxn, binmaxn;
void init()
memset(edge, 0, sizeof(edge));
memset(bin, false, sizeof(bin));
int contract( int -s, int -t ) // Find 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 maxc)
k = j; maxc = distj;
if(k == -1)return mincut;
s = t; t = k;
mincut = maxc;
visk = true;
for(j = 1; j <= n; j++)if(!binj -- !visj)
distj += edgekj;
return mincut;
int Stoer_Wagner()
int mincut, i, j, s, t, ans;
for(mincut = inf, i = 1; i ans)mincut = ans;
if(mincut == 0)return 0;
for(j = 1; j <= n; j++)if(!binj)
edgesj = (edgejs += edgejt);
return mincut;