مسئله تطابق سهبعدی
تطابق سهبعدی در نظریه گراف تعمیم تطابق دوبخشی (تطابق دوبعدی) به ۳ ابرگراف یکشکل است. پیدا کردن بزرگترین تطابق سهبعدی یک مسئلۀ انپی-سخت مشهور در نظریه پیچیدگی محاسباتی است.
تعریف
فرض کنید
مثال
شکل سمت چپ صفحه تطابقهای سهبعدی را نشان میدهد.
تطابق
مقایسه با مسئله تطابق دو بخشی
یک تطابق دوبعدی را میتوان بهطور کاملاً مشابه تعریف کرد. فرض کنید
در تطابق دوبعدی، مجموعۀ
از این رو تطابقهای سهبعدی را میتوان به صورت تعمیم تطابق به ابرگرافها تعبیر کرد: مجموعههای
مقایسه با مسئله بستهبندی مجموعه
یک تطابق سهبعدی حالت خاصی از یک بسته بندی مجموعه است: میتوانیم هر عضو (
مسئله تصمیم
در نظریه پیچیدگی محاسباتی، تطابق سهبعدی همچنین نام مسئله تصمیم زیر است:
با داشتن مجموعۀ
این مسئله حتی در حالت خاص |
مسئله بهینهسازی
یک تطابق سهبعدی بیشینه یک بزرگترین تطابق سهبعدی است. در نظریه پیچیدگی محاسباتی، تطابق سهبعدی همچنین نام مسئله بهینهسازی زیر است:
با داشتن مجموعۀ
از آنجا که مسئلۀ تصمیمی که در بالا آوردهشد انپی-سخت است، این مسئلۀ بهینهسازی انپی-کامل میباشد و به نظر میآید که الگوریتمی چندجملهای برای پیدا کردن یک تطابق سهبعدی بیشینه وجود ندارد. به هر حال، الگوریتمهای چندجملهای بهینهای برای پیداکردن یک تطابق دوبخشی بیشینه (تطابق دوبعدی بیشینه) وجود دارند، برای مثال، الگوریتم هاپکرافت-کارپ.
الگوریتمهای تقریبی
این مسئله APX-کامل است، یعنی به سختی میتوان آن را در حدود یک عدد ثابت تقریب زد. برای هر عدد مثبت ثابت ε>0، یک الگوریتم چندجملهای (ε + ۳/۲)-تقریب برای تطابق سهبعدی وجود دارد.
یک الگوریتم خیلی سادۀ چندجملهای ۳-تقریب برای تطابق سهبعدی وجود دارد: یک تطابق سهبعدی ماکسیمال بیابید. همانگونه که یک تطابق ماکسیمال در حدود عامل ۲ یک تطابق بیشینه است، یک تطابق سهبعدی ماکسیمال نیز در حدود عامل ۳ یک تطابق سهبعدی بیشینه است.