الگوریتم شکوفه ادموندز

قضیه برژ بیان می کند که یک جورسازی بیشینه است اگر، و فقط اگر، هیچ مسیر M – افزوده وجود نداشته باشد. از این رو می توانیم یک جور سازی بیشینه را با یافتن مکرر مسیرهای افزوده بسازیم. چون تنها n/2 بار افزایش می دهیم، یک الگوریتم خوب می یابیم اگر جستجو برای یک مسیر افزوده خیلی طولانی نباشد. ادموندز [ 1965 ] نخستین الگوریتم از این گونه را در مقاله معروفش "مسیر ها، درخت‌ها و گل‌ها " ارائه کرد.

صورت مسئله

در گراف‌های دو بخشی، می توانیم به تندی مسیرهای افزوده را جستجو کنیم زیرا می توانیم مسیرها را محدد کنیم. هنگامی که از یک راس خاص u مسیرهای M – افزوده را جستجو می کنیم، راس هایی که در همان مجموعه بخشی هستند که uدر آن است، تنها از راه یال‌های در M (یال‌های اشباع شده ) در دسترس قرار می گیرند، و راس‌ها در مجموعهٔ بخشس متقابل تنها از راه یال هایی که در M نیستند در دسترس می باشند (یال‌های اشباع نشده ). به این دلیل، جستجویمان را از یک راس داده شده حداکثر یک بار گسترش می دهیم.این ویژگی در گراف‌های با دورهای فرد دیده نمی شود، در این گراف‌ها مسیر متناوب از یک راس اشباع نشده ممکن است به یک راس x در امتداد یال‌های اشباع شده یا در امتداد یال‌ها اشباع نشده برسند.

راه حل ادموندز

در گراف زیر یک جورسازی M که با یال‌های یک پارچه نشان داده شده است، یک جستجو برای کوتاه‌ترین مسیرهای M – افزوده از u، از راه یال اشباع نشده ax به x می رسد.اگر همچنین مسیر طولانی تری را که از راه یک یال اشباع شده به x می رسد در نظر بگیریم، مسیر افزوده y,x,d,c,b,a,v,u را از دست خواهیم داد.

شکل 1

اگر یک جستجوی مسیرهای M-متناوب از u، به وسیله یالی اشباع نشده در مسیری و یالی اشباع شده در مسیر دیگر، به راس x برسد، آن گاه x به یک دور فرد تعلق دارد. مسیرهای متناوب از u را تنها هنگامی می توان برید که یال بعدی اشباع نشده باشد ( ترک کننده راس a در مثال فوق)؛ هنگامی که یال بعدی اشباع شده باشد تنها یک انتخاب برای آن وجود دارد.از راسی که مسیرها در آنجا واگرا می شوند، مسیری که روی یک یال اشباع نشده به x می رسد دارای طول فرد است، و مسیری که روی یک یال اشباع شده به آن میرسد دارای طول زوج است. آن‌ها با یکدیگر یک دور فرد را تشکیل می دهند.

تعریف

فرض کنیم M یک جورسازی در گراف G باشد، و فرض کنیم u یک راس M – اشباع نشده باشد.یک گل اجتماع دو مسیر M- متناوب از u است که روی گام هایی با دو تایگی متقابل ( که بیشتر استفاده نشده باشند ) به x می رسند. ساقه ی گل مسیر آغازی مشترک ماکسیمال است ( با طول زوج نا منفی). شکوفه ی گل عبارت است از دور فرد به دست آمده از حذف ساقه.

شرح الگوریتم

در مثال مطرح شده در بالا گل تمام گراف به جز y است، ساقه مسیر a,v,u است. و شکوفه ۵-دور است. این اصطلاحات مربوط به باغبانی است و اتگیزهٔ آن استفاده از درخت برای ساختارهای ایجاد شده با بیشترین فرآیندهای جستجو است. شکوفه‌ها جستجوی ما را کند نمی کنند.برای هر راس z در یک شکوفه، یک u,z مسیر M –متناوب وجود دارد که روی یک یال اشباع شده به z می رسد، و با عبور روی جهت درست به دور شکوفه برای رسیدن به z از ساقه پیدا می شود. پس جستجویمان را در امتداد هر یال اشباع نشده از شکوفه تا راسی که هنوز به آن نرسیده ایم ادامه می دهیم. مثال مطرح شده در بالا چنین گسترشی را که بی درنگ به یک راس اشباع نشده می رسد و یک مسیر M- افزوده را کامل می کند، نشان می دهد. برعکس، نمی توانیم شکوفه را در امتداد یک یال اشباع شده ترک کنیم . اثر این دو مشاهده آن است که می توانیم تمام شکوفه را به عنوان یک « زبر راس» منفرد در نظر بگیریم که در امتداد یال اشباع شده سرانجام به ساقه می رسیم.می توانیم از همه راس‌های زبر راس شکوفه به طور همزمان در امتداد یال‌های اشباع نشده جستجو کنیم. این ادغام را با منقبض کردن یال‌های یک شکوفهٔ B هنگامی که آن را می یابیم به انجام می رسانیم. نتیجهٔ یک راس جدید از اشباع شده b است که متصل به آخرین یال (اشباع شده) ساقه می باشد. یال‌های متصل دیگر آن، یال‌های اشباع نشده هستند که راس‌های B را به راس‌های بیرون B می پیوندند. می توانیم از b به روش معمول جستجو کنیم تا جستجویمان را گسترش دهیم.می توانیم دیرتر شکوفه ای بیابیم که شامل b باشد؛ شکوفه‌ها می توانند شامل شکوفه‌های پیشین باشند.اگر یک مسیر M –متناوب را در گراف منقبض شده از u به یک راس اشباع نشده x بیابیم، آنگاه می توانیم انقباض‌ها را باز کنیم تا یک مسیر M- افزوده به x را دز گزاف اولیه به دست آوریم. به جز در مورد رفتار با شکوفه ها، این روش همان روش برای جستجوی مسیرهای M- متناوب است. به بیان متناظر ،T مجموعهٔ راس‌های گراف جاری است که در امتداد یال‌های اشباع نشده به آن‌ها می رسیم، و S مجموعه راس هایی است که در امتداد یال‌های اشباع شده به آن‌ها می رسیم. راس هایی که از منقبض کردن شکوفه‌ها پدید می آیند به S تعلق دارند.

یک مثال

گراف سمت چپ زیر یک جور سازی M را با یال‌های یک پارچه نشان می دهد. از راس اشباع نشده u برای یک مسیر M-افزوده جستجو می کنیم.نخست یال‌های اشبهع نشده متصل به u را جستجو می کنیم، که به b , a می رسند.چون b,a اشباع شده هستند، بی درنگ مسیرها را در امتداد یال‌های bd,ac گسترش می دهیم.اکنون {S={u,c,d . اگر در گام بعدی جستجو از c را انتخاب کنیم، همسایه‌های آن f,e را در امتداد یال‌های اشباع نشده خواهیم یافت.چون این‌ها اشباع شده هستند، مسیرها را در امتداد یال ef گسترش می دهیم، و شکوفه با مجموعهٔ راس‌های {c,e,f} را کشف می کنیم.شکوفه را منقبض می کنیم تا راس جدید C را به دست آوریم، و D را به {u,C,d} تبدیل می کنیم.که به گراف سمت راست می رسیم:

شکل 2

اینک فرض می کنیم از راس $C \in S$.جستجو می کنیم . یال‌های اشباع نشده ما را به g و به d می برند. چون g به وسیله یال gh اشباع می شود، h را در S قرار می دهیم.چون d از قبل در S است، شکوفه دیگری پیدا کرده ایم. مسیرهایی که به d می رسند d,C,a,u,d,b,u هستند. شکوفه را منقبض می کنیم، و راس جدید B و گراف سمت راست زیر را، با{S={U,h به دست می آوریم.سپس از h جستجو می کنیم، و چیز جدیدی پیدا نمی کنیم ( اگر S را تمام کنیم بدون آن که به یک راس اشباع نشده برسیم، آنگاه هیچ مسیر M- افزوده ای از u وجود ندارد) . سرانجام، از U جستجو می کنیم، و به راس اشباع نشدهٔ x می رسیم .

شکل 3

اگر یالی را که به هر راس می رسد ثبت کنیم، آنگاه می توانیم یک u,x-مسیر M- افزئده را از جستجو استخراج کنیم.ما از U به x رسیدیم، پس شکوفه را به صورت {u,a,C,d,b} گسترش می دهیم، و یادآوری می کنیم که x از U در امتداد bx در دسترس قرار می گیرد. مسیری در شکوفهٔ U که به b روی یال اشباع شده می رسد با b,d,C گسترش می دهیم و یادآوری می کنیم که d از C در امتداد یک یال اشباع شده به e می رسد عبارت از e,f,c.سرانجام c از a و a از u در دسترس قرار گرفته بود، پس مسیر کامل M- افزوده x,b,d,e,f,c,a,u را استخراج می کنیم.

صورت الگوریتمی شکوفه ادموندز-چکیده

• • ورودی:

یک گراف G، یک جورسازی M در G، یک راس M- اشباع نشده u .

• • حکم:

مسیرهای M- متناوب را از U جستجو کنید، با فرض اینکه S مجموعه راس هایی است که در امتداد یال‌های M در دسترس قرار می گیرند وT مجموعه راس هایی است که در امتداد یال هایی که در M نیستند در دسترس قرار می گیرند. راس هایی از S را که جستجو شده اند را علامتگذاری می کنیم، و برای هر راس S U T، راسی را که از آن به آن رسیده ایم، ثبت می کنیم.هنگامی که شکوفه‌ها پیدا می شوند، آن‌ها را منقبض کنید.

• • ارزش دهی آغازی: {t=$\varnothing$ s={u

• • تکرار:

اگر S دارای هیچ راس علامت گذاری شده ای نباشد، متوقف شوید و گزارش دهید که هیچ مسیری M- افزوده ای از u وجود ندارد. در غیر این صورت، یک v ∈ S علامت گذاری نشده را انتخاب کنید. برای جستجوی v، هر $y\in N(x)$ را طوری در نظر بگیرید که $xy\not\in M$. اگر y اشباع نشده باشد، متوقف شوید و از y به عقب بازگردید (شکوفه‌های مورد نظر را توسعه دهید ) تا یک u,y – مسیر M – افزوده را گزارش کنید. در غیر این صورت ، y به یک w ای به وسله M جور می شود.اگر $w\not\in S$ ، y را در T قرار دهید ( در دسترس از v) و w را در S قرار دهید ( در دسترس از y) . اگر w ∈ S(یا اگر w همسایه ای از v باشد )، آنگاه یک شکوفه پیدا شده است. شکوفه را منقبض کنید، راس‌های آن را در T,S به جای یک راس جدید منفرد در S جایگزین کنید تا جست جو را در گراف کوچک تر ادامه دهید . پس از جستجوی همه چنین یال هایی که متصل به v هستند ، v را علامتگذاری کنید و تکرار نمایید.

زمان اجرا

الگوریتم اولیه ادموندز در زمان $( O (n^4$ انجام می شود.

منابع

• intruduction to graph theory,Douglas B.west
• en:Edmonds's matching algorithm Edmonds's matching algorithm Edmonds's matching algorithm