در مجموعه ای از افراد، هر فرد با برخی از افراد دیگر سازگار است، یافتن شرایطی که تحت آن بتوانیم افراد را به صورت جفت سازگار باهم دسته بندی کنیم. بسیاری از کاربردهای گراف ها تضمین کنندهٔ چنین جفت سازی هایی هستند.
یک جورسازی در یک گراف بی سوی G مجموعه ای از یال های دو به دو مجزا می باشد. رأس های متعلق به یال های یک جورسازی، اشباع شده و سایر رأس ها اشباع نشده هستند. اگر یک جورسازی هر راس از G را اشباع کند، آن گاه یک جورسازی تام یا جورسازی کامل است.
برای جستجوی یک جورسازی بزرگ، می توانیم به طور مکرر یالی مجزا شده از یال های بیشتر انتخاب شده، را، در نظر بگیریم. این روند یک جورسازی ماکسیمال را به دست می دهد، اما لزومی ندارد که یک جورسازی بیشینه رابدهد. یک جورسازی ماکسیمال را نمی توان بیشتر نمود، زیرا یال های آن با همهٔ یال های دیگر متلاقی می باشد ولی یک جورسازی بیشینه، یک جورسازی با حداکثر اندازه است. طبق قضیه برژ جورسازی های بیشینه هیچ مسیر افزوده ای ندارند.
• تعریف
اگر GوH گراف هایی با مجموعهٔ رأس های V باشند، آنگاه تفاضل متقارن GΔH، گرافی با مجموعهٔ رأس های Vاست که یال هایش همهٔ یال هایی هستند که دقیقادر G یا H ظاهر شوند. بنابراین اگر MوN جورسازی باشند آن گاه داریم:
اگر گراف X، گرافMرا اشباع کند، آن گاه برای هر S ⊆ X باید حداقل | S | راس وجود داشته باشند که دارای همسایه هایی در | S | باشند. قضیه هال ثابت می کند که این شرط لازم و کافی است.
مشخص سازی مسیر - افزوده برای جورسازی های بیشینه به الگوریتم تطابق بیشینه در گراف دوبخشی برای یافتن جورسازی های بیشینه می انجامد. جستجوی پیاپی مسیرهای افزوده و افزایش آن به اندازهٔ یک یال موجب یافتن این مسیر می شود که در صورت عدم پیدا کردن یک مسیر افزوده، پوشش راسی با اندازهٔ جورسازی جاری یافت می شود.
زمان اجرای الگوریتم جورسازی دو بخشی را می توان با ترتیبی ماهرانه در جستجوی مسیرهای افزوده بهبود بخشید. درصورتی که مسیرهای افزودهٔ کوتاه در دسترس باشند، نیاز به جستجوی یال های فراوان جهت یافتن یک یال نیست. بااستفاده از الگوریتم تطابق بیشینه در گراف دوبخشی به طور هم زمان از تمام رأس های اشباع نشدهٔ گراف X، می توانیم با یک بررسی مجموعهٔ یال ها مسیرهای فراونی با طول یکسان را بیابیم. هاپکرافت و کارپ ثابت کرده اند که افزوده های بعدی باید از مسیرهای طولانی تری استفاده کنند، بنابراین جستجوها را می توان در فازهایی که مسیرهای با طول یکسان را پیدا می کنند، گروه بندی کرد. به این شکل جورسازی بیشینه در گراف های دوبخشی را می توان در زمان ( O ( n2. 5 یافت.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفیک جورسازی در یک گراف بی سوی G مجموعه ای از یال های دو به دو مجزا می باشد. رأس های متعلق به یال های یک جورسازی، اشباع شده و سایر رأس ها اشباع نشده هستند. اگر یک جورسازی هر راس از G را اشباع کند، آن گاه یک جورسازی تام یا جورسازی کامل است.
برای جستجوی یک جورسازی بزرگ، می توانیم به طور مکرر یالی مجزا شده از یال های بیشتر انتخاب شده، را، در نظر بگیریم. این روند یک جورسازی ماکسیمال را به دست می دهد، اما لزومی ندارد که یک جورسازی بیشینه رابدهد. یک جورسازی ماکسیمال را نمی توان بیشتر نمود، زیرا یال های آن با همهٔ یال های دیگر متلاقی می باشد ولی یک جورسازی بیشینه، یک جورسازی با حداکثر اندازه است. طبق قضیه برژ جورسازی های بیشینه هیچ مسیر افزوده ای ندارند.
• تعریف
اگر GوH گراف هایی با مجموعهٔ رأس های V باشند، آنگاه تفاضل متقارن GΔH، گرافی با مجموعهٔ رأس های Vاست که یال هایش همهٔ یال هایی هستند که دقیقادر G یا H ظاهر شوند. بنابراین اگر MوN جورسازی باشند آن گاه داریم:
اگر گراف X، گرافMرا اشباع کند، آن گاه برای هر S ⊆ X باید حداقل | S | راس وجود داشته باشند که دارای همسایه هایی در | S | باشند. قضیه هال ثابت می کند که این شرط لازم و کافی است.
مشخص سازی مسیر - افزوده برای جورسازی های بیشینه به الگوریتم تطابق بیشینه در گراف دوبخشی برای یافتن جورسازی های بیشینه می انجامد. جستجوی پیاپی مسیرهای افزوده و افزایش آن به اندازهٔ یک یال موجب یافتن این مسیر می شود که در صورت عدم پیدا کردن یک مسیر افزوده، پوشش راسی با اندازهٔ جورسازی جاری یافت می شود.
زمان اجرای الگوریتم جورسازی دو بخشی را می توان با ترتیبی ماهرانه در جستجوی مسیرهای افزوده بهبود بخشید. درصورتی که مسیرهای افزودهٔ کوتاه در دسترس باشند، نیاز به جستجوی یال های فراوان جهت یافتن یک یال نیست. بااستفاده از الگوریتم تطابق بیشینه در گراف دوبخشی به طور هم زمان از تمام رأس های اشباع نشدهٔ گراف X، می توانیم با یک بررسی مجموعهٔ یال ها مسیرهای فراونی با طول یکسان را بیابیم. هاپکرافت و کارپ ثابت کرده اند که افزوده های بعدی باید از مسیرهای طولانی تری استفاده کنند، بنابراین جستجوها را می توان در فازهایی که مسیرهای با طول یکسان را پیدا می کنند، گروه بندی کرد. به این شکل جورسازی بیشینه در گراف های دوبخشی را می توان در زمان ( O ( n2. 5 یافت.
