موضوع مقاله: الگوریتم شکوفه ادموندز | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم شکوفه ادموندز | مقدمه: قضیه برژ بیان می‌کند که یک جورسازی بیشینه است اگر، و فقط اگر، هیچ مسیر M – افزوده وجود نداشته باشد. | ## بخش 1: الگوریتم شکوفه ادموندز | چون تنها n/2 بار افزایش می‌دهیم، یک الگوریتم خوب می یابیم اگر جستجو برای یک مسیر افزوده خیلی طولانی نباشد. جک ادموندز (۱۹۶۵) نخستین الگوریتم از این گونه را در مقاله معروفش "مسیر ها، درخت‌ها و گل‌ها" ارائه کرد. left صورت مسئله در گراف‌های دو بخشی، می‌توانیم به تندی مسیرهای افزوده را جستجو کنیمقضیه هال زیرا می‌توانیم مسیرها را محدد کنیم. هنگامی که از یک راس خاص u مسیرهای M – افزوده را جستجو می‌کنیم، راس‌هایی که در همان مجموعه بخشی هستند که uدر آن است، تنها از راه یال‌های در M (یال‌های اشباع شده) در دسترس قرار می‌گیرند، و رأس‌ها در مجموعهٔ بخشس متقابل تنها از راه یال‌هایی که در M نیستند در دسترس می‌باشند (یال‌های اشباع نشده). این ویژگی در گراف‌های با دورهای فرد دیده نمی‌شود، در این گراف‌ها مسیر متناوب از یک راس اشباع نشده ممکن است به یک راس x در امتداد یال‌های اشباع شده یا در امتداد یال‌ها اشباع نشده برسند. راه حل ادموندز در گراف زیر یک جورسازی M که با یال‌های یکپارچه نشان داده شده‌است، یک جستجو برای کوتاه‌ترین مسیرهای M – افزوده از u، از راه یال اشباع نشده ax به x می‌رسد. اگر همچنین مسیر طولانی تری را که از راه یک یال اشباع شده به x می‌رسد در نظر بگیریم، مسیر افزوده y,x،d,c،b,a،v,u را از دست خواهیم داد. مسیرهای متناوب از u را تنها هنگامی می‌توان برید که یال بعدی اشباع نشده باشد ( ترک‌کننده راس a در مثال فوق)؛ هنگامی که یال بعدی اشباع شده باشد تنها یک انتخاب برای آن وجود دارد. از راسی که مسیرها در آنجا واگرا می‌شوند، مسیری که روی یک یال اشباع نشده به x می‌رسد دارای طول فرد است، و مسیری که روی یک یال اشباع شده به آن می‌رسد دارای طول زوج است. تعریف فرض کنیم M یک جورسازی در گراف G باشد، و فرض کنیم u یک راس M – اشباع نشده باشد. یک گل اجتماع دو مسیر M- متناوب از u است که روی گام‌هایی با دو تایگی متقابل (که بیشتر استفاده نشده باشند) به x می‌رسند. شرح الگوریتم در مثال مطرح شده در بالا گل تمام گراف به جز y است، ساقه مسیر a,v،u است. این اصطلاحات مربوط به باغبانی است و اتگیزهٔ آن استفاده از درخت برای ساختارهای ایجاد شده با بیشترین فرایندهای جستجو است. | ## بخش 2: الگوریتم شکوفه ادموندز | برای هر راس z در یک شکوفه، یک u,z مسیر M –متناوب وجود دارد که روی یک یال اشباع شده به z می‌رسد، و با عبور روی جهت درست به دور شکوفه برای رسیدن به z از ساقه پیدا می‌شود. پس جستجویمان را در امتداد هر یال اشباع نشده از شکوفه تا راسی که هنوز به آن نرسیده ایم ادامه می‌دهیم. مثال مطرح شده در بالا چنین گسترشی را که بی‌درنگ به یک راس اشباع نشده می‌رسد و یک مسیر M- افزوده را کامل می‌کند، نشان می‌دهد. اثر این دو مشاهده آن است که می‌توانیم تمام شکوفه را به عنوان یک « زبر راس» منفرد در نظر بگیریم که در امتداد یال اشباع شده سرانجام به ساقه می‌رسیم. می توانیم از همه رأس‌های زبر راس شکوفه به‌طور هم‌زمان در امتداد یال‌های اشباع نشده جستجو کنیم. این ادغام را با منقبض کردن یال‌های یک شکوفهٔ B هنگامی که آن را می یابیم به انجام می‌رسانیم. نتیجهٔ یک راس جدید از اشباع شده b است که متصل به آخرین یال (اشباع شده) ساقه می‌باشد. یال‌های متصل دیگر آن، یال‌های اشباع نشده هستند که رأس‌های B را به رأس‌های بیرون B می پیوندند. می توانیم دیرتر شکوفه‌ای بیابیم که شامل b باشد؛ شکوفه‌ها می‌توانند شامل شکوفه‌های پیشین باشند. اگر یک مسیر M –متناوب را در گراف منقبض شده از u به یک راس اشباع نشده x بیابیم، آنگاه می‌توانیم انقباض‌ها را باز کنیم تا یک مسیر M- افزوده به x را دز گزاف اولیه به دست آوریم. به جز در مورد رفتار با شکوفه‌ها، این روش همان روشالگوریتم مسیر افزوده برای جستجوی مسیرهای M- متناوب است. به بیان متناظر ،T مجموعهٔ رأس‌های گراف جاری است که در امتداد یال‌های اشباع نشده به آن‌ها می‌رسیم، و S مجموعه راس‌هایی است که در امتداد یال‌های اشباع شده به آن‌ها می‌رسیم. چون b,a اشباع شده هستند، بی‌درنگ مسیرها را در امتداد یال‌های bd,ac گسترش می‌دهیم. | ## بخش 3: الگوریتم شکوفه ادموندز | اگر در گام بعدی جستجو از c را انتخاب کنیم، همسایه‌های آن f,e را در امتداد یال‌های اشباع نشده خواهیم یافت. چون این‌ها اشباع شده هستند، مسیرها را در امتداد یال ef گسترش می‌دهیم، و شکوفه با مجموعهٔ رأس‌های {c,e،f} را کشف می‌کنیم.شکوفه را منقبض می‌کنیم تا راس جدید C را به دست آوریم، و D را به {u,C،d} تبدیل می‌کنیم. شکوفه را منقبض می‌کنیم، و راس جدید B و گراف سمت راست زیر را، با{S={U,h به دست می آوریم. سپس از h جستجو می‌کنیم، و چیز جدیدی پیدا نمی‌کنیم ( اگر S را تمام کنیم بدون آن که به یک راس اشباع نشده برسیم، آنگاه هیچ مسیر M- افزوده‌ای از u وجود ندارد) . مسیری در شکوفهٔ U که به b روی یال اشباع شده می‌رسد با b,d،C گسترش می‌دهیم و یادآوری می‌کنیم که d از C در امتداد یک یال اشباع شده به e می‌رسد عبارت از e,f،c. صورت الگوریتمی شکوفه ادموندز-چکیده ورودی: یک گراف G، یک جورسازی M در G، یک راس M- اشباع نشده u . حکم: مسیرهای M- متناوب را از U جستجو کنید، با فرض اینکه S مجموعه راس‌هایی است که در امتداد یال‌های M در دسترس قرار می‌گیرند وT مجموعه راس‌هایی است که در امتداد یال‌هایی که در M نیستند در دسترس قرار می‌گیرند. راس‌هایی از S را که جستجو شده‌اند را علامتگذاری می‌کنیم، و برای هر راس S U T، راسی را که از آن به آن رسیده ایم، ثبت می‌کنیم. ارزش دهی آغازی: {t= s={u تکرار: اگر S دارای هیچ راس علامت‌گذاری شده‌ای نباشد، متوقف شوید و گزارش دهید که هیچ مسیری M- افزوده‌ای از u وجود ندارد. اگر y اشباع نشده باشد، متوقف شوید و از y به عقب بازگردید (شکوفه‌های مورد نظر را توسعه دهید ) تا یک u,y – مسیر M – افزوده را گزارش کنید. شکوفه را منقبض کنید، رأس‌های آن را در T,S به جای یک راس جدید منفرد در S جایگزین کنید تا جست جو را در گراف کوچک‌تر ادامه دهید . | ## جمع‌بندی | پس از جستجوی همه چنین یال‌هایی که متصل به v هستند، v را علامتگذاری کنید و تکرار نمایید.