مسئله تطابق سه‌بعدی کیست؟ توضیح بده.
تطابق سه‌بعدی در نظریه گراف تعمیم تطابق دوبخشی (تطابق دوبعدی) به ۳ ابرگراف یک‌شکل است. پیدا کردن بزرگ‌ترین تطابق سه‌بعدی یک مسئلۀ ان‌پی-سخت مشهور در نظریه پیچیدگی محاسباتی است.تعریف.فرض کنید formula_1، formula_2 و formula_3 مجموعه‌های متناهی مجزا باشند و formula_4 یک زیرمجموعه ازformula_3 × formula_2 × formula_1باشد. یعنی formula_4 شامل ۳ تایی‌های formula_9 است به طوری که formula_1 ∋ formula_11، formula_2 ∋ formula_13 و formula_3 ∋ formula_15.formula_4 ⊇ formula_17 یک تطابق سه‌بعدی است در صورتی که به ازای هر دو سه‌تایی مجزاformula_17 ∋ (formula_19) و formula_17 ∋ (formula_21) داشته باشیم:formula_22≠formula_23formula_24≠formula_25 وformula_26≠formula_27مثال.شکل سمت چپ صفحه تطابق‌های سه‌بعدی را نشان می‌دهد. formula_1 با نقاط قرمز، formula_2 با نقاط آبی و formula_3 با نقاط سبز نشان داده شده‌است. شکل الف مجموعۀ formula_4 (نواحی خاکستری) را نشان می‌دهد. شکل ب یک تطابق سه‌بعدی formula_17 با ۲ = |formula_17| را نشان می‌دهد و شکل پ یک تطابق سه‌بعدی formula_17 با ۳ = |formula_17| را نشان می‌دهد.تطابق formula_17 که در شکل پ نشان داده‌شده‌است یک تطابق سه‌بعدی بیشینه است، یعنی |formula_17| را بیشینه می‌کند. تطابق‌های نشان داده‌شده در شکل‌های ب و پ تطابق‌های سه‌بعدی ماکسیمال هستند، یعنی نمی‌توان با افزودن عضوهای بیش‌تری از formula_4 آن‌ها را گسترش داد.مقایسه با مسئله تطابق دو بخشی.یک تطابق دوبعدی را می‌توان به‌طور کاملاً مشابه تعریف کرد. فرض کنید formula_1 و formula_2 مجموعه‌های متناهی مجزا باشند و formula_4 یک زیرمجموعه از formula_1 × formula_2 باشد. formula_4 ⊇ formula_17 یک تطابق دوبعدی است در صورتی که برای هر دو زوج مجزایformula_17 ∋ (formula_47) و formula_17 ∋ (formula_49) داشته باشیم: formula_22 ≠ formula_23 و formula_24 ≠ formula_25.در تطابق دوبعدی، مجموعۀ formula_4 را می‌توان به صورت مجموعۀ یال‌ها در یک گراف دوبخشی (formula_55) = formula_56 تعبیر کرد؛ هر یال formula_4 یک رأس از formula_1 را به یک رأس از formula_2 متصل می‌کند و یک تطابق دوبعدی یک تطابق در گراف formula_56 است، یعنی مجموعه‌ای از یال‌های دوبه‌دو غیرمجاور.از این رو تطابق‌های سه‌بعدی را می‌توان به صورت تعمیم تطابق به ابرگراف‌ها تعبیر کرد: مجموعه‌های formula_1، formula_2 و formula_3 شامل یال‌ها هستند، هر عضو formula_4 یک ابرگراف است و مجموعۀ formula_17 شامل یال‌های دوبه‌دو غیرمجاور است (یال‌هایی که رأس مشترک ندارند).مقایسه با مسئله بسته‌بندی مجموعه.یک تطابق سه‌بعدی حالت خاصی از یک بسته بندی مجموعه است: می‌توانیم هر عضو (formula_66) از formula_4 را به عنوان یک زیرمجموعۀ {formula_66} از formula_3 ∪ formula_2 ∪ formula_1 تعبیر کنیم؛ پس یک تطابق سه‌بعدی formula_17 شامل زیرمجموعه‌های دوبه‌دو مجزا است.مسئله تصمیم.در نظریه پیچیدگی محاسباتی، تطابق سه‌بعدی هم‌چنین نام مسئله تصمیم زیر است:با داشتن مجموعۀ formula_4 و عدد صحیح formula_74، آیا یک تطابق formula_4 ⊇ formula_17 با formula_74 ≤ |formula_17| وجود دارد؟ این مسئلۀ تصمیم ان‌پی-کامل است؛ یکی از ۲۱ مسئله ان‌پی-کامل کارپ است.این مسئله حتی در حالت خاص |formula_3| = |formula_2| = |formula_1| = formula_74 هم ان‌پی-کامل است. در این حالت یک تطابق سه‌بعدی نه تنها یک مسئله بسته‌بندی مجموعه است بلکه یک مسئله پوشش دقیق نیز هست: مجموعۀ formula_17 هر عضو formula_1، formula_2 و formula_3 را دقیقاً یک بار پوشش می‌دهد.مسئله بهینه‌سازی.یک تطابق سه‌بعدی بیشینه یک بزرگترین تطابق سه‌بعدی است. در نظریه پیچیدگی محاسباتی، تطابق سه‌بعدی هم‌چنین نام مسئله بهینه‌سازی زیر است:با داشتن مجموعۀ formula_4، یک تطابق سه‌بعدی formula_4 ⊇ formula_17 که |formula_17| را بیشینه می‌کند پیدا کنید.از آنجا که مسئلۀ تصمیمی که در بالا آورده‌شد ان‌پی-سخت است، این مسئلۀ بهینه‌سازی ان‌پی-کامل می‌باشد و به نظر می‌آید که الگوریتمی چندجمله‌ای برای پیدا کردن یک تطابق سه‌بعدی بیشینه وجود ندارد. به هر حال، الگوریتم‌های چندجمله‌ای بهینه‌ای برای پیداکردن یک تطابق دوبخشی بیشینه (تطابق دوبعدی بیشینه) وجود دارند، برای مثال، الگوریتم هاپکرافت-کارپ.الگوریتم‌های تقریبی.این مسئله APX-کامل است، یعنی به سختی می‌توان آن را در حدود یک عدد ثابت تقریب زد. برای هر عدد مثبت ثابت ε&gt;0، یک الگوریتم چندجمله‌ای (ε + ۳/۲)-تقریب برای تطابق سه‌بعدی وجود دارد.یک الگوریتم خیلی سادۀ چندجمله‌ای ۳-تقریب برای تطابق سه‌بعدی وجود دارد: یک تطابق سه‌بعدی ماکسیمال بیابید. همان‌گونه که یک تطابق ماکسیمال در حدود عامل ۲ یک تطابق بیشینه است، یک تطابق سه‌بعدی ماکسیمال نیز در حدود عامل ۳ یک تطابق سه‌بعدی بیشینه است.