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

قضیه برژ بیان می‌کند که یک جورسازی بیشینه است اگر، و فقط اگر، هیچ مسیر M – افزوده وجود نداشته باشد. از این رو می‌توانیم یک جورسازی بیشینه را با یافتن مکرر مسیرهای افزوده بسازیم. چون تنها n/2 بار افزایش می‌دهیم، یک الگوریتم خوب می یابیم اگر جستجو برای یک مسیر افزوده خیلی طولانی نباشد. جک ادموندز (۱۹۶۵) نخستین الگوریتم از این گونه را در مقاله معروفش "مسیر ها، درخت‌ها و گل‌ها" ارائه کرد.

صورت مسئله

در گراف‌های دو بخشی، می‌توانیم به تندی مسیرهای افزوده را جستجو کنیم زیرا می‌توانیم مسیرها را محدد کنیم. هنگامی که از یک راس خاص 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