تطابق (گراف)

درنظریه گراف، به مجموعه‌ای از یال‌های گراف که با هم گره‌ای هموند ندارند، تطابق یا مجموعه‌ی ناوابسته‌ی یال‌ها گفته می‌شود. تطابق دوبخشی حالتی ویژه از پرسمان شبکه شاره است.

تطابق بیشینه در گراف‌های دو بخشی

اغلب اوقات مسئلهٔ تطابق برای گراف دوبخشی مطرح می‌شود. شاید پیدا کردن یک تطابق دو بخشی بیشینه (که اغلب به آن تطابق دو بخشی با سایز بیشینه گفته می‌شود) در یک گراف دو بخشی(G = (V = (X,Y),E، ساده‌ترین مسئله در قسمت تطابق باشد. الگوریتم مسیر افزایشی، در صورتی که بین هر گره مانند x ∈ X به هر گره مانند y مسیر اقزایشی وجود داشته باشد، آن را پیدا می‌کند و به تطابق اضافه می‌کند. از آنجا که هر یک از این مسیرهای افزایش می‌تواند در زمان (O(E پیدا شود، زمان اجرا برای کل این الگوریتم از مرتبهٔ (O(VE می‌شود. این راه حل معادل این است که یک منبع مانند s که به همهٔ گره‌ها در X یال دارد و همچنین یک گودال مانند t که از همهٔ گره‌ها در Y به آن یال وجود دارد، به گراف اضافه کنیم و سپس شار بیشینه را از s به t حساب کنیم. با این کار، همهٔ یال‌هایی که از X به Y جریان دارند، تطابق بیشینه را تشکیل می‌دهند.
این الگوریتم، در الگوریتم هاپ کرافت-کارپ *)، بهبود داده شده‌است و می‌تواند در زمان

اجرا شود.
راه حل دیگر برای پیدا کردن تطابق بیشینه در گراف دو بخشی، بر پایهٔ الگوریتم ضرب سریع ماتریس هاست و دارای پیچیدگی زمانی  است که از نطر تئوری برای گراف‌هایی که تا حد امکان فشرده هستند، کارآمد تر است. اما در عمل این الگوریتم کندتر است.
در گراف دوبخشی وزن‌دار، هر یال دارای یک وزنی است که به آن نسبت داده شده‌است. تطابق بیشینهٔ وزن‌دار برای گراف‌های دو بخشی، تطابق کاملی است که در آن مجموع مقادیر (وزن‌ها) روی یال‌های تطابق، بیشترین مقدار را داشته باشد. اگر گراف دو بخشی کامل نباشد، یال‌هایی که برای دوبخشی کامل شدن لازم است را با وزن ۰ به گراف اضافه می‌کنیم. پیدا کردن این تطابق به پرسمان انتساب مشهور است. این مسئله را می‌توان با استفاده از روش اصلاح شدهٔ یافتن کوتاه‌ترین مسیر در الگوریتم مسیر افزایشی، حل کرد. اگر از الگوریتم بلمن فورد استفاده کنیم، زمان اجرا،  می‌شود. اما چنانچه از الگوریتم دیکسترا و هیپ فیبوناتچی استفاده کنیم، زمان اجرا به  کاهش می‌یابد.
یک الگوریتم قابل توجه بلغاری، برای حل پرسمان انتساب ارائه شده‌است که از نخستین الگوریتم‌های بهینه‌سازی ترکیبی بود. راه حل اصلی این الگوریتم، نیاز به زمان اجرای  دارد اما با استفاده از صف اولویت، می‌توان زمان اجرای آن را به  بهبود بخشید.

تطابق بیشینه

یک راه حل چندجمله‌ای برای پیدا کردن تطابق بیشینه یا تطابق با وزن بیشینه در یک گراف غیر دوبخشی وجود دارد. این روش با توجه به jack Edmonds که بنیانگذار آن بود، روش راهها، درخت‌ها و گل‌ها یا به‌طور مختصر الگوریتم Edmonds نامگذاری شد. این الگوریتم از یال‌های دو سویه استفاده می‌کند. این الگوریتم متعاقباً بهبود بخشیده شد تا در زمان O(√VE) اجرا شود که از مرتبهٔ زمان لازم برای پیدا کردن تطابق بیشینه در گراف‌های دو بخشی است. همچنین الگوریتم دیگری برای پیدا کردن تطابق ماکسیمال وجود دارد که بر پایهٔ ضرب سریع ماتریس‌هاست و به الگوریتم Mucha و Sankowski مشهور است. اجرای این الگوریتم از مرتبهٔ  زمان می‌برد.

تطابق ماکسیمال

تطابق ماکسیمال را می‌توان به سادگی و با استفاده از یک الگوریتم حریصانه بدست آورد. یک تطابق بیشینه، تطابقی ماکسیمال نیز هست؛ بنابراین می‌توان بزرگ‌ترین تطابق ماکسیمال را نیز در زمان چندجمله‌ای پیدا کرد.
با این وجود هنوز هیچ الگوریتم چندجمله‌ای برای پیدا کردن کوچکترین گراف تطابق ماکسیمال که بزرگ‌ترین تطابق بیشینه با کمترین تعداد یال ممکن است، وجود ندارد.
توجه کنید که تطابق ماکسیمال با kیال، یک مجموعهٔ غالب یال‌ها*) با k یال است. در مقابل، اگر کوچک‌ترین مجموعهٔ غالب یال‌ها با k یال را در اختیار داشته باشیم، می‌توان در زمان چندجمله‌ای تطابق ماکسیمال با k یال را ساخت؛ بنابراین پرسمان یافتن کوچکترین گراف تطابق ماکسیمال، معادل پرسمان یافتن کوچکترین مجموعهٔ غالب یال‌هاست. هر دوی این مسائل بهینه‌سازی ان‌پی-سخت است. نسخه‌های تصمیم گیری از این مسائل، از جمله مثال‌های کلاسیک مسائل ان پی (کامل) هستند. هر دوی این مسائل را می‌توان تا جملهٔ دوم در زمان چندجمله‌ای تقریب زد: پیدا کردن تطابق بیشینه دلخواه به سادگی.

پرسمان شمارش

پرسمان پیدا کردن تعداد تطابق‌های کامل برای بک گراف مسئله‌ای #پی-کامل است. هر چند که نظریهٔ قابل توجه Kasteleyn نشان می‌دهد که تعداد تطابق‌های بیشینه در یک گراف مسطح را می‌توان با استفاده از الگوریتم FKT دقیقاً در زمان چندجمله‌ای محاسبه کرد. همچنین یک تقریب تصادفی اما چندجمله‌ای برای شمارش تعداد تطابق‌های دوبخشی وجود دارد.
نطریهٔ کونیگ نشان می‌دهد که در گراف‌های دو بخشی، تطابق بیشینه از نطر اندازه برابر با کوچکترین پوشش گره است. با توجه به نتایج این نطریه، مسئلههٔ بزرگ‌ترین مجموعهٔ ناوابسته و بزرگترین پوشش گره‌ها ممکن است در زمان چندجمله‌ای برای گراف‌های دو بخشی حل شود.
قضیه هال، توصیفی از گراف‌های دو بخشی که تطابق کامل دارد را فراهم می‌کند و همچنین قضیهٔ tutte این خصوصیات را برای گراف دلخواه بیان می‌کند.